Pourquoi le problème de l'arrêt est-il indécidable sur les machines de Turing ?

Réponse publiée sur Quora

C’est plus grave que ça.

Turing lui-même a démontré que le Problème de l’arrêt était indécidable, mais pas que pour “sa” machine.

C’est valable pour tous les systèmes de calcul envisageables selon la Théorie de la calculabilité !

Ce n’est donc pas une limitation de l’architecture des ordinateurs et langages “de Turing”, mais quelque chose de plus fondamental résultant des axiomes utilisés pour la définition même de l’ensemble de ce qui est calculable.

La démonstration de Turing date de 1936, peu après les Théorèmes d’incomplétude de Gödel de 1931 dont elle est une application (presque) directe.