La preuve de Turing - Turing's proof

La preuve de Turing est une preuve d' Alan Turing , publiée pour la première fois en janvier 1937 sous le titre " On Computable Numbers, with an Application to the Entscheidungsproblem ". C'était la deuxième preuve (après le théorème de Church ) de la conjecture selon laquelle certaines questions purement mathématiques oui–non ne peuvent jamais être répondues par le calcul ; plus techniquement, que certains problèmes de décision sont " indécidables " dans le sens où il n'y a pas d'algorithme unique qui donne infailliblement une réponse correcte " oui " ou " non " à chaque instance du problème. Selon les propres mots de Turing : "... ce que je vais prouver est tout à fait différent des résultats bien connus de Gödel... Je vais maintenant montrer qu'il n'y a pas de méthode générale qui indique si une formule U donnée est prouvable dans K [ Principia Mathematica ]..." ( Indécidable , p. 145).

Turing a suivi cette preuve avec deux autres. Le deuxième et le troisième reposent tous deux sur le premier. Tous reposent sur son développement de "machines informatiques" ressemblant à des machines à écrire qui obéissent à un ensemble de règles simples et sur son développement ultérieur d'une "machine informatique universelle".

Résumé des preuves

Dans sa preuve que le problème d'Entscheidungs ​​ne peut avoir de solution, Turing est parti de deux preuves qui devaient conduire à sa preuve finale. Son premier théorème est le plus pertinent pour le problème de l' arrêt , le second est plus pertinent pour le théorème de Rice .

Première preuve : qu'il n'existe pas de "machine à calculer" qui puisse décider si une "machine à calculer" arbitraire (représentée par un entier 1, 2, 3, . . .) est "sans cercle" (c'est-à-dire continue à imprimer son nombre en binaire à l'infini) : "...nous n'avons pas de processus général pour le faire en un nombre fini d'étapes" (p. 132, ibid .). La preuve de Turing, bien qu'elle semble utiliser le "processus diagonal", montre en fait que sa machine (appelée H) ne peut pas calculer son propre nombre, encore moins le nombre diagonal entier ( argument diagonal de Cantor ) : "Le sophisme de l'argument réside dans l'hypothèse que B [le nombre diagonal] est calculable" ( Undecidable , p. 132). La preuve ne nécessite pas beaucoup de mathématiques.

Deuxième preuve : Celle-ci est peut-être plus familière aux lecteurs que le théorème de Rice : "Nous pouvons montrer en outre qu'il ne peut y avoir de machine E qui, lorsqu'elle est alimentée par le ["programme"] SD d'une machine arbitraire M, déterminera si M jamais imprime un symbole donné (0 disons) " (ses italiques, Indécidable , p. 134).

Troisième preuve : " Correspondant à chaque machine de calcul M, nous construisons une formule Un(M) et nous montrons que, s'il existe une méthode générale pour déterminer si Un(M) est prouvable, alors il existe une méthode générale pour déterminer si M a jamais imprime 0" ( Indécidable , p. 145).

La troisième preuve nécessite l'utilisation de la logique formelle pour prouver un premier lemme, suivie d'une brève preuve verbale du second :

Lemme 1 : Si S1 [symbole "0"] apparaît sur la bande dans une configuration complète de M, alors Un(M) est prouvable. ( Indécidable , p. 147)
Lemme 2 : [L'inverse] Si Un(M) est prouvable alors S1 [symbole "0"] apparaît sur la bande dans une configuration complète de M. ( Indécidable , p. 148)

Enfin, en seulement 64 mots et symboles Turing prouve par reductio ad absurdum que « le problème Hilbert Entscheidungs ​​ne peut avoir aucune solution » ( Undecidable , p. 145).

Résumé de la première preuve

Turing a créé un fourré d'abréviations. Voir le glossaire à la fin de l'article pour les définitions.

Quelques précisions clés :

La machine H de Turing tente d'imprimer un nombre diagonal de 0 et de 1.
Ce nombre diagonal est créé lorsque H "simule" réellement chaque machine "réussie" en cours d'évaluation et imprime le R-ème "chiffre" (1 ou 0) de la R-ème machine "réussie".

Turing a passé une grande partie de son article à « construire » ses machines pour nous convaincre de leur vérité. Cela était requis par son utilisation de la forme de preuve reductio ad absurdum . Il faut souligner le caractère « constructif » de cette preuve. Turing décrit ce qui pourrait être une vraie machine, vraiment constructible. Le seul élément discutable est l'existence de la machine D, dont cette démonstration finira par montrer qu'elle est impossible.

Turing commence la preuve par l'affirmation de l'existence d'une machine de « décision/détermination » D. Lorsqu'elle est alimentée par n'importe quelle SD (chaîne de symboles A, C, D, L, R, N, point-virgule « ; »), elle déterminera si cette SD (chaîne de symboles) représente une "machine informatique" qui est soit "circulaire" - et donc "u insatisfaisant" - soit "sans cercle" - et donc "s satisfaisant".

Turing a déjà démontré dans son commentaire que toutes les "machines à calculer - des machines qui calculent un nombre comme des 1 et des 0 pour toujours - peuvent être écrites sous forme de SD sur la bande de la "machine universelle" U. La plupart de son travail menant à son premier la preuve est passée à démontrer qu'une machine universelle existe vraiment, c'est-à-dire
Il existe vraiment une machine universelle U
Pour chaque nombre N, il existe bien une SD unique,
Chaque machine de Turing a une SD
Chaque SD sur la bande de U peut être « exécutée » par U et produira la même « sortie » (figures 1, 0) que la machine d'origine.

Turing ne fait aucun commentaire sur la façon dont la machine D effectue son travail. Pour des raisons d'argument, nous supposons que D chercherait d'abord si la chaîne de symboles est "bien formée" (c'est-à-dire sous la forme d'un algorithme et pas seulement d'un mélange de symboles), et sinon, la rejettera. Ensuite, ça irait à la "chasse au cercle". Pour ce faire, il utiliserait peut-être des « heuristiques » (astuces : enseignées ou apprises). Aux fins de la preuve, ces détails ne sont pas importants.

Turing décrit alors (plutôt vaguement) l'algorithme (méthode) à suivre par une machine qu'il appelle H. La machine H contient en son sein la machine de décision D (donc D est un « sous-programme » de H). L'algorithme de la machine H est exprimé dans la table d'instructions de H, ou peut-être dans la description standard de H sur bande et uni à la machine universelle U ; Turing ne le précise pas.

Au cours de la description de la machine universelle U, Turing a démontré qu'une SD (chaîne de lettres similaire à un « programme ») d'une machine peut être convertie en un entier (base 8) et vice versa. Tout nombre N (en base 8) peut être converti en SD avec les remplacements suivants : 1 par A, 2 par C, 3 par D, 4 par L, 5 par R, 6 par N, 7 par point-virgule ";".

Il s'avère que le numéro unique (DN) de la machine H est le numéro "K". Nous pouvons en déduire que K est un nombre extrêmement long, peut-être des dizaines de milliers de chiffres. Mais ce n'est pas important pour ce qui suit.

La machine H est chargée de convertir n'importe quel nombre N en une chaîne de symboles SD équivalente pour la sous-machine D à tester. (En langage de programmation : H passe un "SD" arbitraire à D, et D renvoie "satisfaisant" ou "insatisfaisant".) le nombre de S.D « réussies », c'est-à-dire R, est bien inférieur au nombre de SD testés, c'est-à-dire N. Enfin, H imprime sur une section de sa bande un nombre diagonal « à amorçage bêta » B'. H crée ce B' en « simulant » (au sens informatique) les « mouvements » de chaque machine/nombre « satisfaisant » ; finalement cette machine/nombre à l'essai arrivera à son Rième « chiffre » (1 ou 0), et H H se charge alors de « faire le ménage » laissé par la simulation, en incrémentant N et en poursuivant ses tests, à l' infini .

Remarque : toutes ces machines que H recherche sont ce que Turing a appelé des "machines à calculer". Ceux-ci calculent des nombres décimaux binaires dans un flux sans fin de ce que Turing a appelé des « chiffres » : seuls les symboles 1 et 0.

Un exemple pour illustrer la première preuve

Un exemple : supposons que la machine H a testé 13472 nombres et produit 5 nombres satisfaisants, c'est-à-dire que H a converti les nombres 1 à 13472 en SD (chaînes de symboles) et les a transmis à D pour le test. En conséquence, H a compté 5 nombres satisfaisants et a conduit le premier à son 1er "chiffre", le deuxième à son 2ème chiffre, le troisième à son 3ème chiffre, le quatrième à son 4ème chiffre et le cinquième à son 5ème chiffre. Le nombre s'élève maintenant à N = 13472, R = 5 et B' = ".10011" (par exemple). H nettoie le désordre sur sa bande et procède :

H incrémente N = 13473 et convertit "13473" en chaîne de symboles ADRLD. Si la sous-machine D juge ADLRD insatisfaisant, alors H laisse l'enregistrement de pointage R à 5. H incrémentera le nombre N à 13474 et continuera. D'un autre côté, si D juge ADRLD satisfaisant alors H incrémentera R à 6. H convertira (à nouveau) N en ADLRD [ce n'est qu'un exemple, ADLRD est probablement inutile] et le « exécutera » en utilisant la machine universelle U jusqu'à ce que cette machine sous test (U "en cours" ADRLD) imprime son 6ème "chiffre" soit 1 ou 0. H imprimera ce 6ème nombre (ex "0") dans la zone "sortie" de sa bande (ex B' = ".100110").

H nettoie le désordre, puis incrémente le nombre N à 13474.

L'ensemble du processus se déroule lorsque H arrive à son propre nombre K. Nous allons continuer avec notre exemple. Supposons que le décompte/enregistrement de réussite R soit égal à 12. H arrive finalement à son propre nombre moins 1, c'est-à-dire N = K-1 = 4335...321 4 , et ce nombre est infructueux. Puis H incrémente N pour produire K = 4355...321 5 , c'est-à-dire son propre nombre. H convertit en « LDDR ... DCAR » et il passe à la décision machine D. machine de décision D doit retourner « satisfaisant » (qui est: H doit , par définition , aller sur et sur le test, ad infinitum , parce qu'il est " sans cercle"). Ainsi, H incrémente maintenant le décompte R de 12 à 13, puis reconvertit le nombre sous test K en son SD et utilise U pour le simuler. Mais cela signifie que H simulera ses propres mouvements. Quelle est la première chose que la simulation va faire ? Cette simulation K-aka-H crée soit un nouveau N, soit "réinitialise" l'"ancien" N à 1. Ce "K-aka-H" crée soit un nouveau R, soit "réinitialise" l'"ancien" R à 0. Ancien -H "exécute" le nouveau "K-aka-H" jusqu'à ce qu'il atteigne son 12ème chiffre.

Mais il n'atteint jamais le 13e chiffre ; K-aka-H arrive finalement à 4355...321 5 , encore une fois, et K-aka-H doit répéter le test. K-aka-H n'atteindra jamais le 13e chiffre. La machine H imprime probablement juste des copies d'elle-même à l' infini sur une bande vierge. Mais cela contredit la prémisse selon laquelle H est une machine informatique satisfaisante et non circulaire qui continue à imprimer les 1 et les 0 des nombres diagonaux pour toujours. (On verra la même chose si N est remis à 1 et R est remis à 0.)

Si le lecteur ne le croit pas, il peut écrire un "stub" pour la machine de décision D (stub "D" renverra "satisfaisant") et ensuite voir par lui-même ce qui se passe à l'instant où la machine H rencontre son propre numéro.

Résumé de la deuxième preuve

Long de moins d'une page, le passage des prémisses à la conclusion est obscur.

Turing procède par reductio ad absurdum . Il affirme l'existence d'une machine E qui, lorsqu'on lui donne la SD (Description Standard, c'est-à-dire "programme") d'une machine arbitraire M, déterminera si M imprime jamais un symbole donné (0 disons). Il n'affirme pas que ce M est une "machine à calculer".

Etant donné l'existence de la machine E, Turing procède comme suit :

1. Si la machine E existe alors une machine G existe qui détermine si M imprime 0 infiniment souvent, ET
2. Si E existe alors un autre processus existe [nous pouvons appeler le processus/machine G' pour référence] qui détermine si M imprime 1 infiniment souvent, DONC
3. Lorsque nous combinons G avec G', nous avons un processus qui détermine si M imprime une infinité de chiffres, ET
4. SI le processus "G avec G'" détermine que M imprime une infinité de chiffres, ALORS "G avec G'" a déterminé que M est sans cercle, MAIS
5. Ce processus "G avec G'" qui détermine si M est sans cercle, par preuve 1, ne peut pas exister, DONC
6. La machine E n'existe pas.

Détails de la deuxième preuve

La difficulté de la preuve est l'étape 1. Le lecteur sera aidé en réalisant que Turing n'explique pas son travail subtil. (En résumé : il utilise certaines équivalences entre les « opérateurs existentiels » et les « opérateurs universels » ainsi que leurs expressions équivalentes écrites avec des opérateurs logiques.)

Voici un exemple : supposons que nous voyions devant nous un parking rempli de centaines de voitures. Nous décidons de faire le tour du lot à la recherche de : « Voitures avec (mauvais) pneus crevés ». Après environ une heure, nous avons trouvé deux « voitures avec de mauvais pneus ». Nous pouvons maintenant dire avec certitude que « Certaines voitures ont de mauvais pneus ». Ou on pourrait dire : « Ce n'est pas vrai que 'Toutes les voitures ont de bons pneus' ». Ou : « C'est vrai que : « toutes les voitures n'ont pas de bons pneus ». Passons à un autre lot. On découvre ici que « Toutes les voitures ont de bons pneus ». Nous pourrions dire : « Il n'y a pas un seul cas où une voiture a un mauvais pneu. » Ainsi, nous voyons que, si nous pouvons dire quelque chose sur chaque voiture séparément, nous pouvons dire quelque chose sur TOUTES collectivement.

C'est ce que fait Turing : A partir de M il crée une collection de machines { M 1, M 2, M 3, M 4, ..., Mn } et à propos de chacune il écrit une phrase : " X imprime au moins un 0 " et n'autorise que deux « valeurs de vérité », True = vide ou False = :0:. Un par un, il détermine la valeur de vérité de la phrase pour chaque machine et crée une chaîne de blancs ou :0:, ou une combinaison de ceux-ci. Nous pourrions obtenir quelque chose comme ceci : « M 1 imprime un 0 » = vrai ET « M 2 imprime un 0 » = vrai ET « M 3 imprime un 0 » = vrai ET « M 4 imprime un 0 » = faux, ... ET « Mn imprime un 0 » = Faux. Il obtient la ficelle

BBB:0::0::0: ... :0: ... à l'infini

s'il existe une infinité de machines Mn . Si, d'un autre côté, si chaque machine avait produit un « vrai », alors l'expression sur la bande serait

BBBBB....BBBB ... à l'infini

Ainsi, Turing a converti les déclarations sur chaque machine considérée séparément en une seule "déclaration" (chaîne) sur chacune d'entre elles. Étant donné la machine (il l'appelle G) qui a créé cette expression, il peut la tester avec sa machine E et déterminer si elle produit jamais un 0. Dans notre premier exemple ci-dessus, nous voyons que c'est effectivement le cas, nous savons donc que tous les Les M dans notre séquence impriment des 0. Mais le deuxième exemple montre que, puisque la chaîne est vide, alors chaque Mn de notre séquence a produit un 0.

Tout ce qui reste à Turing à faire est de créer un processus pour créer la séquence de Mn à partir d'un seul M.

Supposons que M imprime ce motif :

M => ...AB01AB0010AB…

Turing crée une autre machine F qui prend M et calcule une séquence de Mn qui convertit successivement les premiers n 0 en "0-bar" ( 0 ):

Il affirme, sans montrer de détails, que cette machine F est vraiment constructible. Nous pouvons voir que l'une des deux choses pourrait arriver. F peut manquer de machines qui ont des 0, ou il peut devoir continuer à créer des machines à l' infini pour « annuler les zéros ».

Turing combine maintenant les machines E et F en une machine composite G. G commence par le M original, puis utilise F pour créer toutes les machines successeurs M1, M2. . ., Mn. Ensuite, G utilise E pour tester chaque machine en commençant par M. Si E détecte qu'une machine n'imprime jamais de zéro, G imprime :0: pour cette machine. Si E détecte qu'une machine imprime un 0 (nous supposons que Turing ne le dit pas), alors G imprime :: ou saute simplement cette entrée, laissant les carrés vides. Nous pouvons voir que plusieurs choses peuvent arriver.

G n'imprimera jamais de 0, si tous les Mn impriment des 0, OR,
G imprimera des 0 à l'infini si tous les M n'imprimeront aucun 0, OR,
G imprimera des 0 pendant un moment puis s'arrêtera.

Maintenant, que se passe-t-il lorsque nous appliquons E à G lui-même ?

Si E(G) détermine que G n'imprime jamais de 0, alors nous savons que tous les Mn ont imprimé des 0. Et cela signifie que, parce que tous les Mn proviennent de M, M lui-même imprime des 0 à l' infini , OU
Si E(G) détermine que G imprime un 0, alors nous savons que tous les Mn n'affichent pas des 0 ; donc M n'imprime pas les 0 à l' infini .

Comme nous pouvons appliquer le même processus pour déterminer si M imprime 1 infiniment souvent. Lorsque nous combinons ces processus, nous pouvons déterminer que M continue ou non à imprimer des 1 et des 0 à l' infini . Ainsi, nous avons une méthode pour déterminer si M est sans cercle. D'après la preuve 1, c'est impossible. Donc la première affirmation que E existe est fausse : E n'existe pas.

Résumé de la troisième preuve

Ici Turing prouve « que le problème de Hilbert Entscheidungs ne peut avoir aucune solution » ( Undecidable , p. 145). Ici il

…montrent qu'il ne peut y avoir de processus général pour déterminer si une formule donnée U du calcul fonctionnel K est prouvable. ( ibid .)

Les deux lemmes #1 et #2 sont requis pour former le "SI ET SEULEMENT SI" (c'est-à-dire l'équivalence logique ) requis par la preuve :

Un ensemble E est calculable décidable si et seulement si à la fois E et son complément sont calculables énumérables (Franzén, p. 67)

Turing démontre l'existence d'une formule Un (M) qui dit, en effet, que « dans une configuration complète de M, 0 apparaît sur la bande » (p. 146). Cette formule est VRAIE, c'est-à-dire qu'elle est "constructible", et il montre comment s'y prendre.

Ensuite, Turing prouve deux lemmes, le premier nécessitant tout le travail acharné. (Le second est l'inverse du premier.) Puis il utilise reductio ad absurdum pour prouver son résultat final :

1. Il existe une formule Un (M). Cette formule est VRAIE ET
2. Si le problème Entscheidungs peut être résolu ALORS un processus mécanique existe pour déterminer si Un (M) est prouvable (dérivable), ET
3. Par lemmes 1 et 2 : Un (M) est prouvable SI ET SEULEMENT SI 0 apparaît dans une "configuration complète" de M, ET
4. SI 0 apparaît dans une "configuration complète" de M ALORS un processus mécanique existe qui déterminera si M arbitraire imprime jamais 0 , ET
5. D'après la preuve 2, il n'existe aucun processus mécanique qui déterminera si M arbitraire imprime jamais 0 , DONC
6. Un (M) n'est pas prouvable (c'est VRAI, mais pas prouvable ) ce qui signifie que le problème Entscheidungs est insoluble.

Détails de la troisième preuve

[Si les lecteurs ont l'intention d'étudier la preuve en détail, ils doivent corriger leurs copies des pages de la troisième preuve avec les corrections fournies par Turing. Les lecteurs doivent également être munis d'une solide formation en (i) logique (ii) l'article de Kurt Gödel : " On Formally Undecidable Propositions of Principia Mathematica and Related Systems " (reproduit dans Undecidable , p. 5). Pour obtenir de l'aide sur l'article de Gödel, ils devraient consulter par exemple Ernest Nagel et James R. Newman , Gödel's Proof , New York University Press, 1958.]

Pour suivre les détails techniques, le lecteur devra comprendre la définition de « prouvable » et connaître les « indices » importants.

"Prouvable" signifie, au sens de Gödel, que (i) le système d'axiome lui-même est suffisamment puissant pour produire (exprimer) la phrase "Cette phrase est prouvable", et (ii) que dans toute preuve arbitraire "bien formée" les symboles conduisent par axiomes, définitions et substitutions aux symboles de la conclusion.

Premier indice : « Mettons la description de M dans la première forme standard du §6 ». La section 6 décrit le "codage" très spécifique de la machine M sur la bande d'une "machine universelle" U. Cela nécessite que le lecteur connaisse certaines particularités de la machine universelle U de Turing et du schéma de codage.

(i) La machine universelle est un ensemble d'instructions "universelles" qui résident dans une "table d'instructions". Séparément de cela, sur la bande de U, une "machine informatique" M résidera en tant que "code M". La table universelle d'instructions peut imprimer sur la bande les symboles A, C, D, 0, 1, u, v, w, x, y, z, : . Les différentes machines M ne peuvent imprimer ces symboles qu'indirectement en ordonnant à U de les imprimer.

(ii) Le "code machine" de M ne comprend que quelques lettres et le point-virgule, c'est-à-dire D, C, A, R, L, N, ; . Nulle part dans le "code" de M les "chiffres" numériques (symboles) 1 et 0 n'apparaîtront jamais. Si M veut que U imprime un symbole à partir du blanc de collection , 0, 1, alors il utilise l'un des codes suivants pour dire à U de les imprimer. Pour rendre les choses plus confuses, Turing appelle ces symboles S0, S1 et S2, c'est-à-dire

blanc = S0 = D

0 = S1 = CC

1 = S2 = DCC

(iii) Une "machine à calculer", qu'elle soit intégrée directement dans une table (comme le montrent ses premiers exemples), ou comme code machine M sur la bande de la machine universelle U, imprime son numéro sur une bande vierge (à droite de M -code, s'il y en a un) comme 1 s et 0 s en continuant toujours vers la droite.

(iv) Si une « machine informatique » est U+ « M-code », alors « M-code » apparaît en premier sur la bande ; la bande a une extrémité gauche et le "code M" commence là et se poursuit vers la droite sur des carrés alternés. Lorsque le code M prendra fin (et il le doit, en raison de l'hypothèse que ces codes M sont des algorithmes finis), les "chiffres" commenceront par 1 s et 0 s sur des carrés alternés, en continuant vers la droite pour toujours. Turing utilise les carrés alternatifs (vides) (appelés "E" - "effaçables" - carrés) pour aider U+"M-code" à garder une trace de l'emplacement des calculs, à la fois dans le M-code et dans les "chiffres" que le la machine imprime.

(v) Une "configuration complète" est une impression de tous les symboles sur la bande, y compris le code M et les "chiffres" jusqu'à ce point, ainsi que le chiffre en cours de numérisation (avec un caractère pointeur imprimé à gauche de la symbole scanné ?). Si nous avons correctement interprété le sens de Turing, ce sera un ensemble de symboles extrêmement long. Mais si l'ensemble du code M doit être répété n'est pas clair ; seule une impression de l'instruction M-code actuelle est nécessaire plus l'impression de tous les chiffres avec un marqueur de chiffre).

(vi) Turing a réduit le grand nombre possible d'instructions dans le « M-code » (encore une fois : le code de M devant apparaître sur la bande) à un petit ensemble canonique, l'un des trois similaires à celui-ci : {qi Sj Sk R ql} Par exemple, si la machine exécute l'instruction #qi et que le symbole Sj se trouve sur le carré en cours de balayage, alors imprimez le symbole Sk et allez à droite puis allez à l'instruction ql : les autres instructions sont similaires, encodant pour "Gauche" L et "Pas de mouvement" N C'est cet ensemble qui est codé par la chaîne de symboles qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA....A. Chaque instruction est séparée d'une autre par le point-virgule. Par exemple, {q5, S1 S0 L q3} signifie : Instruction n°5 : Si le symbole scanné est 0, imprimez en blanc , allez à gauche, puis passez à l'instruction n°3. Il est codé comme suit

; DAAAAADCDLDAAA

Deuxième indice : Turing utilise des idées introduites dans l'article de Gödel, c'est-à-dire la « Gödelisation » de (au moins une partie de) la formule pour Un (M). Cet indice n'apparaît que sous forme de note de bas de page à la page 138 ( Indécidable ) : "Une séquence de r nombres premiers est notée ^ (r)" ( ibid .) [Ici, r entre parenthèses est "élevé".] Cette "séquence de nombres premiers" apparaît dans une formule appelée F^(n).

Troisième indice : Cela renforce le deuxième indice. La tentative originale de Turing pour la preuve utilise l'expression :

(Eu)N(u) & (x)(... etc. ...) ( Indécidable , p. 146)

Plus tôt dans l'article, Turing avait déjà utilisé cette expression (p. 138) et défini N(u) comme signifiant "u est un entier non négatif" ( ibid .) (c'est-à-dire un nombre de Gödel). Mais, avec les corrections de Bernays, Turing a abandonné cette approche (c'est-à-dire l'utilisation de N(u)) et le seul endroit où "le nombre de Gödel" apparaît explicitement est celui où il utilise F^(n).

Qu'est-ce que cela signifie pour la preuve? Le premier indice signifie qu'un simple examen du code M sur la bande ne révélera pas si un symbole 0 est jamais imprimé par U + "code M". Une machine de test peut rechercher l'apparition de DC dans l'une des chaînes de symboles qui représentent une instruction. Mais cette instruction sera-t-elle un jour « exécutée ? » Quelque chose doit "exécuter le code" pour le savoir. Ce quelque chose peut être une machine, ou ce peut être des lignes dans une preuve formelle, c'est-à-dire le lemme #1.

Les deuxième et troisième indices signifient que, comme son fondement est l'article de Gödel, la preuve est difficile.

Dans l'exemple ci-dessous, nous allons en fait construire un simple "théorème" - un petit programme de machine Post-Turing "l'exécuter". Nous verrons à quel point un théorème bien conçu peut être mécanique. Une preuve, nous le verrons, n'est que cela, un "test" du théorème que nous faisons en insérant un "exemple de preuve" au début et voir ce qui ressort à la fin.

Les deux lemmes #1 et #2 sont requis pour former le "SI ET SEULEMENT SI" (c'est-à-dire l'équivalence logique) requis par la preuve :

Un ensemble E est décidable par calcul si et seulement si à la fois E et son complément sont dénombrables par calcul. (Franzén, p. 67)

Pour citer Franzén :

Une phrase A est dite décidable dans un système formel S si A ou sa négation est prouvable dans S. (Franzén, p. 65)

Franzén a défini "prouvable" plus tôt dans son livre :

Un système formel est un système d' axiomes (exprimés dans un langage formellement défini) et de règles de raisonnement (également appelées règles d'inférence), utilisés pour dériver les théorèmes du système. Un théorème est tout énoncé dans le langage du système obtenu par une série d'applications des règles de raisonnement, à partir des axiomes. Une preuve est une suite finie de telles applications, conduisant à un théorème comme conclusion. ( ibid. p. 17)

Ainsi, une "phrase" est une chaîne de symboles, et un théorème est une chaîne de chaînes de symboles.

Turing est confronté à la tâche suivante :

convertir un "programme" de machine de Turing universel et les symboles numériques sur la bande (les "chiffres" de Turing, les symboles "1" et "0"), en un "théorème", c'est-à-dire une chaîne (monstrueusement longue) de phrases qui définissent les actions successives de la machine, (toutes) les figures de la bande, et l'emplacement de la "tête de bande".

Ainsi, la "chaîne de phrases" sera des chaînes de chaînes de symboles. Les seuls symboles individuels autorisés proviendront des symboles de Gödel définis dans son article. (Dans l'exemple suivant, nous utilisons le "<" et le ">" autour d'un "chiffre" pour indiquer que le "chiffre" est le symbole scanné par la machine ).

Un exemple pour illustrer la troisième preuve

Dans ce qui suit, nous devons nous rappeler que chacune des « machines à calculer » de Turing est un générateur/créateur de nombres binaires qui commence à travailler sur une « bande vierge ». Correctement construit, il tourne toujours à l'infini, mais ses instructions sont toujours finies. Dans les épreuves de Turing, la bande de Turing avait une « extrémité gauche » mais s'étendait à droite à l'infini. À titre d'exemple ci-dessous, nous supposerons que la « machine » n'est pas une machine universelle, mais plutôt la « machine dédiée » plus simple avec les instructions du tableau.

Notre exemple est basé sur un modèle de machine Post-Turing modifié d' une machine de Turing. Ce modèle n'imprime que les symboles 0 et 1. La bande vierge est considérée comme n'étant que des b. Notre modèle modifié nous oblige à ajouter deux instructions supplémentaires aux 7 instructions Post-Turing. Les abréviations que nous utiliserons sont :

R, DROITE : regarder vers la droite et déplacer la bande vers la gauche, ou déplacer la tête de bande vers la droite
L, GAUCHE : regarder vers la gauche et déplacer la bande vers la droite, ou déplacer la tête de bande vers la gauche
E, EFFACER le carré scanné (par exemple, faire un carré vierge)
P0 ,: PRINT 0 dans le carré scanné
P1,: PRINT 1 dans le carré scanné
Jb_n, JUMP-IF-blank-to-instruction_#n,
J0_n, JUMP-IF-0-to-instruction_#n,
J1_n, JUMP-IF-1 -à-instruction_#n,
ARRÊTER.

Dans les cas de R, L, E, P0 et P1 après avoir effectué sa tâche, la machine passe à l'instruction suivante dans la séquence numérique ; idem pour les sauts si leurs tests échouent.

Mais, par souci de concision, nos exemples n'utiliseront que trois carrés. Et ceux-ci commenceront toujours par des blancs avec le carré scanné à gauche : c'est-à-dire bbb. Avec deux symboles 1, 0 et blanc on peut avoir 27 configurations distinctes :

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

Nous devons être prudents ici, car il est tout à fait possible qu'un algorithme laisse (temporairement) des blancs entre les chiffres, puis revienne et remplisse quelque chose. Plus probablement, un algorithme peut le faire intentionnellement. En fait, la machine de Turing fait cela : elle imprime sur des carrés alternés, laissant des blancs entre les chiffres afin qu'elle puisse imprimer des symboles de localisation.

Turing laissait toujours des carrés alternatifs vides afin que sa machine puisse placer un symbole à gauche d'un chiffre (ou une lettre si la machine est la machine universelle et que le carré scanné est en fait dans le « programme »). Dans notre petit exemple, nous y renoncerons et placerons simplement des symboles ( ) autour du symbole scanné, comme suit :

b(b)0, cela signifie : « La bande est vide à gauche du vide laissé mais le vide laissé est « en jeu », le carré scanné est vide, « 0 », les blancs à droite »
1 (0)1 cela signifie, "La bande est vide vers la gauche, puis 1, le carré scanné est '0'"

Écrivons un programme simple :

départ : P1, R, P1, R, P1, H

N'oubliez pas que nous commençons toujours avec une bande vierge. La configuration complète imprime les symboles sur la bande suivis de l'instruction suivante :

démarrer la config : (b) P1,
config #1 : (1) R,
config #2 : 1(b) P1,
config #3 : 1(1) R,
config #4 : 11(b) P1,
config #5 : 11(1) H

Ajoutons « saut » dans la formule. Lorsque nous faisons cela, nous découvrons pourquoi la configuration complète doit inclure les symboles de bande. (En fait, nous le voyons mieux, ci-dessous.) Ce petit programme imprime trois "1" vers la droite, inverse la direction et se déplace vers la gauche en imprimant des 0 jusqu'à ce qu'il atteigne un blanc. Nous imprimerons tous les symboles que notre machine utilise :

départ : P1, R, P1, R, P1, P0, L, J1_7, H
(b)bb P1,
(1)bb R,
1(b)b P1,
1(1)b R,
11(b) P1 ,
11(1) P0,
11(0) L,
1(1)0 J1_7
1(1)0 L
(1)10 J0_7
(1)10 L
(b)110 J0_7
(b)110 H

Ici, à la fin, nous constatons qu'un blanc à gauche est « entre en jeu », nous le laissons donc dans le cadre de la configuration totale.

Étant donné que nous avons fait notre travail correctement, nous ajoutons les conditions de départ et voyons « où va le théorème ». La configuration résultante—le nombre 110—est la PREUVE.

• La première tâche de Turing consistait à écrire une expression généralisée utilisant des symboles logiques pour exprimer exactement ce que ferait son Un(M).
• La deuxième tâche de Turing consiste à « Gödeliser » cette chaîne de symboles extrêmement longue en utilisant la technique de Gödel consistant à attribuer des nombres premiers aux symboles et à élever les nombres premiers à des puissances premières, selon la méthode de Gödel.

Complications

La preuve de Turing est compliquée par un grand nombre de définitions, et confondue avec ce que Martin Davis a appelé des « petits détails techniques » et « ... des détails techniques [qui] sont incorrects tels qu'ils sont donnés » (le commentaire de Davis dans Undecidable , p. 115). Turing publia lui-même « Une correction » en 1938 : « L'auteur est redevable à P. Bernays d' avoir signalé ces erreurs » ( Undecidable , p. 152).

Plus précisément, dans sa forme originale, la troisième preuve est gravement entachée d'erreurs techniques. Et même après les suggestions de Bernays et les corrections de Turing, des erreurs subsistaient dans la description de la machine universelle . Et de manière confuse, puisque Turing n'a pas pu corriger son article original, certains textes dans le corps rappellent le premier effort défectueux de Turing.

Les corrections de Bernays peuvent être trouvées dans Undecidable , pp. 152-154; l'original se trouve sous le titre "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction," Proceedings of the London Mathematical Society (2), 43 (1938), 544-546.

La version en ligne de l'article de Turing contient ces corrections dans un addendum ; cependant, les corrections apportées à la Machine universelle doivent être trouvées dans une analyse fournie par Emil Post .

Au début, le seul mathématicien à prêter une attention particulière aux détails de la preuve était Post (cf. Hodges p. 125) - principalement parce qu'il était arrivé simultanément à une réduction similaire de "l'algorithme" aux actions primitives de type machine, donc il s'intéressa personnellement à la preuve. Curieusement (peut-être la Seconde Guerre mondiale est-elle intervenue), il a fallu à Post une dizaine d'années pour le disséquer dans l' annexe de son article Recursive Unsolvability of a Problem of Thue , 1947 (reproduit dans Undecidable , p. 293).

D'autres problèmes se présentent : dans son annexe Post a commenté indirectement la difficulté de l'article et directement sa « nature schématique » (Post in Undecidable , p. 299) et la « forme intuitive » des preuves ( ibid .). Post a dû déduire plusieurs points :

Si notre critique est correcte, une machine est dite sans cercle si c'est une machine de calcul de Turing... qui imprime un nombre infini de 0 et de 1. Et les deux théorèmes de Turing en question sont en réalité les suivants. Il n'y a pas de machine de Turing... qui, lorsqu'elle est fournie avec un entier positif arbitraire n, déterminera si n est le DN d'une machine de calcul de Turing... sans cercle. [Deuxièmement], il n'y a pas de machine à convention de Turing qui, lorsqu'elle est fournie avec un entier positif arbitraire n, déterminera si n est le DN d'une machine informatique de Turing qui imprime un symbole donné (0 disons). (Publier dans Indécidable , p. 300)

Quiconque a déjà essayé de lire le journal comprendra la plainte de Hodges :

Le journal a commencé de manière attrayante, mais a rapidement plongé (à la manière typique de Turing) dans un bosquet d'obscurs caractères gothiques allemands afin de développer sa table d'instructions pour la machine universelle. Les derniers à y jeter un coup d'œil seraient les mathématiciens appliqués qui ont dû recourir au calcul pratique... (Hodges p. 124)

Glossaire des termes utilisés par Turing

1 nombre calculable - un nombre dont la décimale est calculable par une machine (c'est-à-dire par des moyens finis tels qu'un algorithme)

2 M — une machine avec une table d'instructions finie et une tête de balayage/impression. M déplace une bande infinie divisée en carrés chacun "capable de porter un symbole". Les instructions machine sont uniquement les suivantes : déplacer d'un carré à gauche, déplacer d'un carré à droite, sur le carré scanné imprimer le symbole p, effacer le carré scanné, si le symbole est p alors faire l'instruction aaa, si le symbole scanné n'est pas p alors faire l'instruction aaa, si le symbole scanné n'est aucun alors faire l'instruction aaa, si le symbole scanné est tout faire l'instruction aaa [où "aaa" est un identifiant d'instruction].

3 machine informatique - un M qui imprime deux types de symboles, les symboles du premier type sont appelés « chiffres » et ne sont que des symboles binaires 1 et 0 ; les symboles du second type sont tous les autres symboles.

4 chiffres — symboles 1 et 0 , alias "symboles de la première sorte"

5 m-configuration — l'identifiant d'instruction, soit un symbole dans la table d'instructions, soit une chaîne de symboles représentant le numéro d'instruction sur la bande de la machine universelle (par exemple "DAAAAA = #5")

6 symboles du deuxième type — tous les symboles autres que 1 et 0

7 circulaire — une machine informatique qui échoue. Il n'imprime pas, à l'infini, les chiffres 0 ou 1 qui représentent en binaire le nombre qu'il calcule

8 sans cercle — une machine informatique à succès. Il imprime, à l'infini, les chiffres 0 ou 1 qui représentent en binaire le nombre qu'il calcule

9 séquence — comme dans « séquence calculée par la machine » : symboles du premier type aka chiffres aka symboles 0 et 1.

10 séquences calculables - peuvent être calculées par une machine sans cercle

11 SD – Description standard : une séquence de symboles A, C, D, L, R, N, « ; » sur une bande de machine de Turing

12 DN — Description Number : une SD convertie en un nombre : 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7= ;

13 M(n) — une machine dont le DN est le nombre « n »

14 satisfaisant — un SD ou DN qui représente une machine sans cercle

15 U — une machine équipée d'une table d'instructions « universelle ». Si U est "fourni avec une bande au début de laquelle est inscrit le SD d'une machine informatique M, U calculera la même séquence que M".

16 β' —« bêta-primé » : Un soi-disant « nombre diagonal » composé du n-ième chiffre (c'est-à-dire 0 ou 1) de la n-ième séquence calculable [aussi : le nombre calculable de H, voir ci-dessous ]

17 u - un SD insatisfaisant, c'est-à-dire circulaire

18 s — satisfaisant, c'est-à-dire SD sans cercle

19 D — une machine contenue dans H (voir ci-dessous). Lorsqu'il est fourni avec le SD de n'importe quelle machine informatique M, D testera le SD de M et s'il est circulaire, marquez-le avec "u" et s'il n'y a pas de cercle, marquez-le avec "s"

20 H — une machine informatique. H calcule B', maintient R et N. H contient D et U et une machine (ou processus) quelconque qui maintient N et R et fournit à D l'équivalent SD de N. E calcule également les chiffres de B' et assemble les chiffres de B'.

21 R - un enregistrement, ou un décompte, de la quantité de SD réussis (sans cercle) testés par D

22 N — un nombre, commençant par 1, à convertir en SD par la machine E. E maintient N.

23 K — un nombre. Le DN de H.

Requis pour la preuve #3

5 m-configuration — l'identifiant de l'instruction, soit un symbole dans la table d'instructions, soit une chaîne de symboles représentant le numéro de l'instruction sur la bande de la machine universelle (par exemple "DAAAAA = instruction #5"). Dans la SD de Turing, la m-configuration apparaît deux fois dans chaque instruction, la chaîne la plus à gauche est l'"instruction actuelle" ; la chaîne la plus à droite est l'instruction suivante.

24 configuration complète — le numéro (chiffre 1 ou 0 ) du carré scanné, la séquence complète de tous les symboles sur la bande et la m-configuration (l'identifiant d'instruction, soit un symbole soit une chaîne de symboles représentant un nombre, par exemple "instruction DAAAA = #5")

25 RSi(x, y) — "dans la configuration complète x de M, le symbole sur le carré y est Si ; "configuration complète" est la définition #5

26 I(x, y) — "dans la configuration complète x de M le carré y est scanné"

27 Kqm(x) — "dans la configuration complète x de M, la configuration de la machine (numéro d'instruction) est qm"

28 F(x,y) — "y est le successeur immédiat de x" (suivant l'utilisation par Gödel de "f" comme fonction successeur).

29 G(x,y) — "x précède y", pas nécessairement immédiatement

30 Inst{qi, Sj Sk L ql} est une abréviation, tout comme Inst{qi, Sj Sk R ql} et Inst{qi, Sj Sk N ql} . Voir ci-dessous.

Turing réduit son jeu d'instructions à trois "formes canoniques" - une pour la gauche, la droite et l'immobilité. Si et Sk sont des symboles sur la bande.

ruban		Final
m-config	symbole	Opérations	m-config
qi	Si	PSk, L	qm
qi	Si	PSk, R	qm
qi	Si	PSk, N	qm

Par exemple, les opérations de la première ligne sont PSk = PRINT symbole Sk de la collection A, C, D, 0, 1, u, v, w, x, y, z, : , puis déplacez la bande vers la GAUCHE.

Il les a ensuite abrégés en : (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

Dans la preuve #3, il appelle le premier de ces "Inst{qi Sj Sk L ql}", et il montre comment écrire la machine entière SD comme la conjonction logique (OU logique) : cette chaîne est appelée "Des(M)" , comme dans "Description-de-M". c'est-à-dire que si la machine imprime 0 puis 1 et 0 sur des carrés alternés vers la droite à l'infini, elle peut avoir le tableau (un exemple similaire apparaît à la page 119) :

q1, blanc, P0, R, q2
q2, blanc, P-blanc, R, q3
q3, blanc, P1, R, q4
q4, blanc, P-blanc, R, q1

(Ceci a été réduit à une forme canonique avec les instructions "p-blank" donc cela diffère un peu de l'exemple de Turing.) S1 = 0, S2 = 1) :

Inst {q1 S0 S1 R q2}
Inst {q2 S0 S0 R q3}
Inst {q3 S0 S2 R q4}
Inst {q4 S0 S0 R q1}

La réduction à la description standard (SD) sera :

; DADDCRDAA ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA ;

Cela correspond à son exemple dans le livre (il y aura un blanc entre chaque lettre et chiffre). La machine universelle U utilise les carrés blancs alternatifs comme emplacements pour placer des "pointeurs".

Les références

• Turing, AM (1937), "On Computable Numbers, with an Application to the Entscheidungsproblem", Actes de la London Mathematical Society , 2, 42 (1), pp. 230-65, doi : 10.1112/plms/s2-42.1. 230
• Turing, AM (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction", Actes de la London Mathematical Society , 2, 43 (6), pp. 544–6, doi : 10.1112/plms/s2 -43.6.544). ( Version en ligne .) C'est l'article d'époque où Turing définit les machines de Turing , montre que le problème Entscheidungs est insoluble.
• Hans Reichenbach (1947), Éléments de logique symbolique , Dover Publications, Inc., New York.
• Martin Davis (1965), The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, New York. Les deux articles de Post mentionnés ci-dessus sont inclus dans ce volume. D'autres articles incluent ceux de Gödel, Church, Rosser et Kleene.
• Andrew Hodges (1983), Alan Turing : L'énigme , Simon et Schuster , New York. Cf. Chapitre "L'Esprit de Vérité" pour une histoire menant à, et une discussion de, sa preuve.
• Torkel Franzén (2005), Le théorème de Gödel : un guide incomplet de son utilisation et de son abus . AK Peters.