Théorie des nombres calculables, suivie d’une application au problème de la décision

Introduction

Turing, jeune fellow du King’s College de Cambridge, en vint au problème par les cours de Max Newman sur les fondements des mathématiques en 1935 : Hilbert avait demandé s’il existe une méthode mécanique pour décider, de toute formule de la logique, si elle est démontrable. La London Mathematical Society reçut l’article en mai 1936, et il parut dans ses Proceedings en 1936–37. Turing analyse ce que fait une personne qui calcule selon une règle et le réduit à une machine à un nombre fini d’états qui lit, écrit et se déplace le long d’un ruban illimité ; les « nombres calculables » sont les nombres réels dont une telle machine peut écrire les décimales. Il montre qu’une seule machine universelle peut imiter n’importe quelle autre si on lui en donne la description, et qu’aucune machine ne peut décider, pour toute machine, si elle imprimera jamais un symbole donné – d’où suit la réponse négative à la question de Hilbert. Alonzo Church avait publié la même réponse peu auparavant, au moyen de son λ-calcul ; dans un appendice, Turing prouva l’équivalence des deux notions de calculabilité, et à l’automne 1936 il partit pour Princeton, où il passa son doctorat sous la direction de Church en 1938.

Liens

S’appuie sur

• Sur des propositions formellement indécidables des Principia Mathematica et des systèmes apparentés I1931 · Kurt Gödel

Reprise dans

• Les ordinateurs et l’intelligence1950 · Alan Turing

Autres œuvres de Alan Turing

• 1950Les ordinateurs et l’intelligence