Je comprends la preuve de l'indécidabilité du problème d'arrêt (donnée par exemple dans le manuel de Papadimitriou), basée sur la diagonalisation.

Bien que la preuve soit convaincante (j'en comprends chaque étape), elle n'est pas intuitive pour moi en ce sens que je ne vois pas comment quelqu'un la dériverait, à partir du seul problème.

Dans le livre, la preuve est la suivante: "supposons que résout le problème d'arrêt sur une entrée , c'est-à-dire décide si la machine de Turing s'arrête pour l'entrée . Construire une machine de Turing qui prend une machine de Turing comme entrée , exécute et inverse la sortie. " Il montre ensuite que ne peut pas produire une sortie satisfaisante. M ; x M x D M M H ( M ; M ) D ( D $M_H$$M;x$$M$$x$$D$$M$$M_H(M;M)$$D(D)$

C'est la construction apparemment arbitraire de , en particulier l'idée de nourrir à lui-même, puis à lui-même, pour laquelle j'aimerais avoir une intuition. Qu'est-ce qui a amené les gens à définir ces constructions et étapes en premier lieu?M $D$$M$$D$

Quelqu'un a-t-il une explication sur la façon dont quelqu'un raisonnerait son chemin dans l'argument de la diagonalisation (ou une autre preuve), s'il ne connaissait pas ce type d'argument pour commencer?

Addendum au premier tour de réponses:

Ainsi, les premières réponses indiquent que la preuve de l'indécidabilité du problème d'arrêt était quelque chose basé sur les travaux antérieurs de Cantor et Russell et le développement du problème de diagonalisation, et que partir "à partir de zéro" signifierait simplement devoir redécouvrir cet argument.

C'est suffisant. Cependant, même si nous acceptons l'argument de la diagonalisation comme une donnée bien comprise, je trouve toujours qu'il y a un "écart d'intuition" entre le problème et l'arrêt. La preuve de Cantor de l'indénombrabilité des nombres réels que je trouve en fait assez intuitive; Le paradoxe de Russell l'est encore plus.

Ce que je ne vois toujours pas ce qui est de motiver quelqu'un à définir $D(M)$ sur la base $M$ « auto-application » de $M;M$ , puis appliquez à nouveau $D$ sur lui-même. Cela semble moins lié à la diagonalisation (dans le sens où l'argument de Cantor n'avait pas quelque chose comme ça), bien que cela fonctionne bien avec la diagonalisation une fois que vous les avez définis.

PS

@babou a résumé ce qui me dérangeait mieux que moi: "Le problème avec de nombreuses versions de la preuve est que les constructions semblent être tirées d'un chapeau magique."

Dans votre montage, vous écrivez:

Ce que je ne vois toujours pas ce qui est de motiver quelqu'un à définir sur la base M « auto-application » de M ; M , puis appliquez à nouveau D sur lui-même. Cela semble moins lié à la diagonalisation (dans le sens où l'argument de Cantor n'avait pas quelque chose comme ça), bien que cela fonctionne bien avec la diagonalisation une fois que vous les avez définis.$D(M)$$M$$M;M$$D$

Un résumé «populaire» commun de la preuve de Turing se présente comme suit:

"Si nous avions une machine qui pourrait décider si une autre machine Turing s'arrête ou non, nous pourrions l'utiliser pour construire une autre machine D qui, étant donné une machine Turing M , s'arrêterait si et seulement si M ne s'arrêtait pas . Mais alors nous pourrait passer D en entrée, et ainsi obtenir un paradoxe: cette machine s'arrêterait si et seulement si elle ne s'arrêtait pas! "$M_H$$D$$M$$M$$D$

Maintenant, il est facile de voir que le résumé ci-dessus passe sous silence un détail important - l'arrêt de la machine Turing dépend également de son entrée, que nous n'avons pas spécifiée! Mais ce problème peut être résolu assez facilement: nous avons juste besoin d'avoir D choisir une entrée appropriée x M pour chaque machine d' entrée M , avant de les transmettre à la fois à M H .$M$$D$$x_M$$M$$M_H$

Quel est un choix approprié pour , étant donné que nous voulons finalement dériver une contradiction? Eh bien, un choix naturel est suggéré directement par la preuve "handwavy" ci-dessus, où l'on obtient finalement la contradiction en faisant tourner la machine D sur elle-même.$x_M$$D$

Ainsi, pour que le comportement de soit vraiment paradoxal dans ce cas, c'est-à-dire lorsqu'il est invoqué comme D ( D ) , ce que nous voulons, c'est que l'arrêt de D ( M ) dépende du comportement de M lorsqu'il est invoqué comme M ( M ) . De cette façon, nous allons obtenir la contradiction que nous voulons en fixant M = D .$D$$D(D)$$D(M)$$M$ $M(M)$$M = D$

Attention, ce n'est pas le seul choix; on aurait pu aussi dériver la même contradiction, disons, en construisant une machine telle que D ' ( M ) s'arrête si et seulement si M ( D ' ) (plutôt que M ( M ) ) ne s'arrête pas. Mais, alors qu'il est clair que la machine D peut facilement dupliquer son entrée avant de la passer à M H , il n'est pas si évident de savoir comment construire une machine D ' qui invoquerait M H avec son propre code comme entrée. Ainsi, en utilisant ce$D'$$D'(M)$$M(D')$$M(M)$$D$$M_H$$D'$$M_H$ au lieu de D compliquerait inutilement la preuve et la rendrait moins intuitive.$D'$$D$

Il se peut simplement qu'il soit erroné de penser que quelqu'un raisonnerait à cet argument sans faire un argument similaire à un moment donné auparavant, dans un contexte "plus simple".

Rappelez-vous que Turing connaissait la diagonalisation de Cantor comme preuve de l'indénombrabilité des réels. De plus, son travail fait partie d'une histoire des mathématiques qui inclut le paradoxe de Russell (qui utilise un argument de diagonalisation) et le premier théorème d'incomplétude de Gödel (qui utilise un argument de diagonalisation). En fait, le résultat de Gödel est profondément lié à la preuve de l'indécidabilité du problème de l'arrêt (et donc à la réponse négative au Entscheidungsproblem de Hilbert).

Donc, je soutiens que votre question est dans un sens mal fondée et que vous ne pouvez pas atteindre le problème de l'arrêt sans passer par le reste (ou quelque chose de remarquablement similaire) en premier. Bien que nous montrions ces choses aux étudiants sans passer par l'histoire, si vous étiez un mathématicien travaillant, il semble peu probable que vous passiez de rien à Turing Machines sans rien entre les deux - le but était de formaliser le calcul, un problème que beaucoup de gens avaient travaille depuis des décennies à ce moment-là.

Cantor n'a même pas utilisé la diagonalisation dans sa première preuve de l'indénombrabilité des réels, si nous prenons les dates de publication comme une approximation du moment où il a pensé à l'idée (pas toujours une chose fiable), il lui a fallu environ 17 ans pour savoir déjà que les réels étaient indénombrables, à travailler sur l'argument de la diagonalisation.

En référence à "l'auto-application" dans la preuve que vous mentionnez, cela fait également partie intégrante du paradoxe de Russell (qui dépend entièrement de l'auto-référence), et le premier théorème d'incomplétude de Gödel est comme la version puissante du paradoxe de Russell . La preuve de l'indécidabilité du problème de l'arrêt est si fortement informée par le travail de Gödel qu'il est difficile d'imaginer y arriver sans elle, par conséquent l'idée de "l'auto-application" fait déjà partie des connaissances de base dont vous avez besoin pour arriver au problème de l'arrêt . De même, le travail de Gödel est une refonte du paradoxe de Russell, donc vous n'y arrivez pas sans l'autre (notez que Russell n'était pas le premier à observer un paradoxe comme celui-ci, donc les prototypes de l'argument de la diagonalisation existent dans la logique formelle depuis environ 600BCE). Les travaux de Turing et de Gödel (les morceaux dont nous parlons ici) peuvent être considérés comme des démonstrations de plus en plus puissantes des problèmes d'auto-référence et de la façon dont ils s'intègrent dans les mathématiques. Donc, encore une fois, il est très difficile de suggérer que ces idées au niveau où Turing les traitait sont venuesa priori , ils étaient le point culminant du travail de millénaires dans des domaines de la philosophie, des mathématiques et de la logique.

Cette référence à soi fait également partie de l'argument de Cantor, elle n'est tout simplement pas présentée dans un langage aussi peu naturel que le travail plus fondamentalement logique de Turing. La diagonalisation de Cantor peut être reformulée comme une sélection d'éléments de l'ensemble de puissance d'un ensemble (essentiellement une partie du théorème de Cantor). Si nous considérons l'ensemble des réels (positifs) comme des sous-ensembles des naturels (notez que nous n'avons pas vraiment besoin des chiffres à ordonner pour que cela fonctionne, cela fait simplement une présentation plus simple) et affirmons qu'il y a une surjection des naturels à les réels, alors nous pouvons produire un élément de l'ensemble de pouvoir (c'est-à-dire un réel) qui n'est pas à l'image de la surjection (et donc dériver une contradiction) en prenant cet élément pour être l'ensemble des naturels qui ne sont pas dans leur propre l'image sous la surjection. Une fois que nous l'avons formulé de cette façon, c'est '

L'auto-application n'est pas un ingrédient nécessaire de la preuve

En un mot

S'il existe une machine de Turing qui résout le problème d'arrêt, alors à partir de cette machine, nous pouvons construire une autre machine de Turing L avec un comportement d'arrêt (fonction caractéristique d'arrêt) qui ne peut être le comportement d'arrêt d'une machine de Turing.$H$$L$

Le paradoxe construit sur la fonction auto-appliquée (appelé L dans cette réponse - désolé des incohérences de notation) n'est pas un ingrédient nécessaire de la preuve, mais un dispositif utilisable avec la construction d'une contradiction spécifique, cachant ce qui semble être le "réel". but "de la construction. C'est probablement pourquoi ce n'est pas intuitif.$D$$L$

Il semble plus direct de montrer qu'il n'y a qu'un nombre dénombrable de comportements d'arrêt (pas plus que les machines de Turing), qui peuvent être définis comme des fonctions d'arrêt caractéristiques associées à chaque machine de Turing. On peut définir de manière constructive une fonction d'arrêt caractéristique ne figurant pas dans la liste, et construire à partir de celle-ci, et à partir d'une machine qui résout le problème d'arrêt, une machine L qui a cette nouvelle fonction d'arrêt caractéristique. Mais comme, par construction, ce n'est pas la fonction d'arrêt caractéristique d'une machine de Turing, L ne peut pas en être une. Puisque L est construit à partir de H en utilisant des techniques de construction de machines de Turing, H ne peut pas être une machine de Turing.$H$$L$$L$$L$$H$$H$

L'auto-application de à lui-même, utilisée dans de nombreuses preuves, est un moyen de montrer la contradiction. Mais cela ne fonctionne que lorsque la fonction d'arrêt de caractéristique impossible est construite à partir de la diagonale de la liste des fonctions d'arrêt de caractéristique autorisées de Turing, en inversant cette diagonale (échange de 0 et 1 ). Mais il existe une infinité d'autres façons de construire une nouvelle fonction d'arrêt caractéristique. Ensuite, la non-Turing-ness ne peut plus être mise en évidence avec un paradoxe menteur (du moins pas simplement). La construction de l'auto-application n'est pas intuitive car elle n'est pas essentielle, mais elle semble lisse lorsqu'elle est retirée du chapeau magique.$L$$0$$1$

Fondamentalement, n'est pas une machine de Turing car il est conçu dès le départ pour avoir un comportement d'arrêt qui n'est pas celui d'une machine de Turing, et qui peut être montré plus directement, donc plus intuitivement.$L$

Remarque : Il se peut que, pour tout choix constructif de la fonction d'arrêt de caractéristique impossible, il y ait une réorganisation calculable de l'énumération de la machine de Turing de telle sorte qu'elle devienne la diagonale (je ne sais pas). Mais, à mon humble avis, cela ne change pas le fait que l'auto-application est une technique de preuve indirecte qui cache un fait plus intuitif et intéressant.

Analyse détaillée des preuves

Je ne vais pas être historique (mais grâce à ceux qui le sont, j'aime ça), mais j'essaie seulement de travailler le côté intuitif.

Je pense que la présentation donnée à @vzn , que j'ai rencontrée il y a longtemps (j'avais oublié), est en fait plutôt intuitive, et explique même la diagonalisation du nom. Je le répète en détail uniquement parce que j'estime que @vzn n'a pas suffisamment souligné sa simplicité.

Mon but est d'avoir un moyen intuitif de récupérer la preuve, sachant celle de Cantor. Le problème avec de nombreuses versions de la preuve est que les constructions semblent être tirées d'un chapeau magique.

La preuve que je donne n'est pas exactement la même que dans la question, mais elle est correcte, pour autant que je puisse voir. Si je n'ai pas fait d'erreur, c'est assez intuitif car je pourrais le récupérer après plus d'années que je ne compte, en travaillant sur des sujets très différents.

Le cas des sous-ensembles de (Cantor)$\mathbb N$

La preuve de Cantor suppose (ce n'est qu'une hypothèse) qu'il y a une énumération des sous-ensembles des entiers, de sorte que tous ces sous-ensembles peuvent être décrits par sa fonction caractéristique C j ( i ) qui est 1 si i ∈ S j et vaut 0 sinon.$S_j$$C_j(i)$$1$$i\in S_j$$0$

Cela peut être vu comme un tableau , tel que T [ i , j ] = C j ( i $T$$T[i,j]=C_j(i)$

Ensuite, en considérant la diagonale, nous construisons une fonction caractéristique telle que D ( i ) = ¯ T [ i , i ] , c'est-à-dire qu'elle est identique à la diagonale du tableau avec chaque bit retourné à l'autre valeur.$D$$D(i)=\overline{T[i,i]}$

La diagonale n'a rien de spécial, sauf que c'est un moyen facile d'obtenir une fonction caractéristique différente de toutes les autres, et c'est tout ce dont nous avons besoin.$D$

Par conséquent, le sous-ensemble caractérisé par ne peut pas être dans l'énumération. Puisque ce serait vrai de toute énumération, il ne peut pas être une énumération qui énumère tous les sous - ensembles de N .$D$$\mathbb N$

Certes, selon la question initiale, c'est assez intuitif. Pouvons-nous rendre la preuve du problème d'arrêt aussi intuitive?

Le cas du problème d'arrêt (Turing)

Nous supposons que nous avons une énumération de machines de Turing (que nous savons possible). Le comportement d'arrêt d'une machine de Turing peut être décrit par sa fonction d'arrêt caractéristique H j ( i ) qui est 1 si M j s'arrête sur l'entrée i et 0 sinon.$M_j$$H_j(i)$$1$$M_j$$i$$0$

Cela peut être vu comme un tableau , tel que T [ i , j ] = H j ( i $T$$T[i,j]=H_j(i)$

Ensuite, en considérant la diagonale, nous construisons une fonction d'arrêt caractéristique telle que D ( i ) = ¯ T [ i , i ] , c'est-à-dire qu'elle est identique à la diagonale du tableau avec chaque bit inversé à l'autre valeur.$D$$D(i)=\overline{T[i,i]}$

La diagonale n'a rien de spécial, sauf que c'est un moyen facile d'obtenir une fonction d'arrêt caractéristique qui est différente de toutes les autres, et c'est tout ce dont nous avons besoin (voir note en bas).$D$

Par conséquent, le comportement d'arrêt caractérisé par ne peut pas être celui d'une machine de Turing dans l'énumération. Puisque nous les avons tous énumérés, nous concluons qu'il n'y a pas de machine Turing avec ce comportement.$D$

Pas d'oracle d'arrêt jusqu'à présent, et pas d'hypothèse de calculabilité : Nous ne savons rien du calculable de et des fonctions H j .$T$$H_j$

Supposons maintenant que nous ayons une machine de Turing qui peut résoudre le problème d'arrêt, de telle sorte que H ( i , j ) s'arrête toujours avec H j ( i ) comme résultat.$H$$H(i,j)$$H_j(i)$

Nous voulons prouver que, compte tenu de , nous pouvons construire une machine L qui a la fonction caractéristique arrêt D . La machine L est presque identique à H , de sorte que L ( i ) imite H ( i , i ) , sauf que chaque fois que H ( i , i ) est sur le point de se terminer avec la valeur 1 , L ( i ) entre dans une boucle infinie et ne se termine pas.$H$$L$$D$$L$$H$$L(i)$$H(i,i)$$H(i,i)$$1$$L(i)$

Il est bien clair que l'on peut construire une telle machine si H existe. Par conséquent, cette machine devrait être dans notre énumération initiale de toutes les machines (ce que nous savons possible). Mais cela ne peut pas l'être puisque son comportement d'arrêt D ne correspond à aucune des machines énumérées. La machine L ne peut pas exister, ce qui implique que H ne peut exister.$L$$H$$D$$L$$H$

_{J'ai délibérément imité la première preuve et suis entré dans les moindres détails}

Mon sentiment est que les étapes viennent naturellement de cette façon, surtout quand on considère la preuve de Cantor comme raisonnablement intuitive.

On énumère d'abord les constructions litigieuses. Ensuite, on prend et modifie la diagonale comme un moyen pratique de les toucher tous pour obtenir un comportement inexpliqué, puis obtient une contradiction en exposant un objet qui a le comportement inexpliqué ... si une hypothèse était vraie: existence de l'énumération pour Cantor, et l'existence d'un oracle d'arrêt calculable pour Turing.

Remarque: Pour définir la fonction , nous pourrions remplacer la diagonale inversée par toute autre fonction d'arrêt caractéristique, différente de toutes celles répertoriées en T , qui est calculable (à partir de celles répertoriées en T , par exemple) à condition qu'un oracle d'arrêt soit disponible . Ensuite, la machine L devrait être construite en conséquence, pour avoir D comme fonction d'arrêt caractéristique, et L ( i ) utiliserait la machine H , mais ne reproduirait pas aussi directement H ( i , i ) . Le choix de la diagonale le rend beaucoup plus simple.$D$$T$$T$$L$$D$$L(i)$$H$$H(i,i)$

Comparaison avec la "autre" preuve

La fonction définie ici est apparemment l'analogue de la fonction D dans la preuve décrite dans la question.$L$$D$

Nous le construisons uniquement de manière à ce qu'il ait une fonction d'arrêt caractéristique qui ne correspond à aucune machine de Turing, et en obtenons directement une contradiction. Cela nous donne la liberté de ne pas utiliser la diagonale (pour ce qu'elle vaut).

L'idée de la preuve "habituelle" semble essayer de tuer ce que je considère comme un poisson mort. Il dit: supposons que est l'une des machines répertoriées (c'est-à-dire toutes). Ensuite , il a un indice j L en ce que l' énumération: L = M j L . Alors si L ( j L ) s'arrête, nous avons T [ j L , j L ] = H ( j L , j L ) = 1 , de sorte que L ( j L$L$$j_L$$L=M_{j_L}$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=1$$L(j_L)$bouclera par construction. Inversement, si ne s'arrête pas, alors T [ j L , j L ] = H ( j L , j L ) = 0 pour que L ( j L ) s'arrête par construction. Nous avons donc une contradiction. Mais la contradiction résulte de la façon dont la fonction d'arrêt caractéristique de L a été construite, et il semble beaucoup plus simple de dire que $L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=0$$L(j_L)$$L$$L$ ne peut pas être une machine de Turing car elle est conçue pour avoir une fonction d'arrêt caractéristique qui n'est pas celle d'une machine de Turing.

Un inconvénient est que cette preuve habituelle serait beaucoup plus douloureuse si nous ne choisissions pas la diagonale, alors que l'approche directe utilisée ci-dessus n'a aucun problème avec elle. Si cela peut être utile, je ne sais pas.

Il y a aussi une preuve de ce fait qui utilise un paradoxe différent, le paradoxe de Berry, que j'ai entendu de Ran Raz.

Supposons que le problème d'arrêt était calculable. Soit le plus petit nombre naturel qui ne peut pas être calculé par un programme C de longueur n . Autrement dit, si S ( n ) est l'ensemble des nombres naturels calculés par C programmes de longueur n , alors B ( n ) est le plus petit nombre naturel qui n'est pas dans S ( n ) .$B(n)$$n$$S(n)$$n$$B(n)$$S(n)$

Considérez le programme suivant:

1. Passez en revue tous les programmes C de longueur au plus .$n$

2. Pour chacun de ces programmes, vérifiez s'il s'arrête; si elle le fait, l' ajouter à une liste .$L$

3. Sortie le premier nombre naturel non .$L$

Ceci est un programme pour calculer $B(n)$ . Quelle est la taille de ce programme? Le codage prend O ( log n ) caractères, et le reste du programme ne dépend pas de n , donc au total la longueur est O ( log n ) , disons au plus C log n . Choisissez N pour que C log N ≤ N . Ensuite, notre programme, dont la longueur est au plus N , calcule B ( N ) , contredisant la définition de$n$$O(\log n)$$n$$O(\log n)$$C\log n$$N$$C\log N \leq N$$N$$B(N)$ .$B(N)$

La même idée peut être utilisée pour prouver les théorèmes d'incomplétude de Gödel, comme l'ont montré Kritchman et Raz .

Il y a une idée plus générale impliquée ici appelée le "théorème de récursivité" qui peut être plus intuitive: les machines de Turing peuvent utiliser leur propre description (et ainsi s'exécuter elles-mêmes). Plus précisément, il existe un théorème:

Pour toute machine de Turing T, il existe une machine de Turing Rqui calcule R(x) = T(R;x).

Si nous avions une machine de Turing qui pourrait résoudre le problème d'arrêt, alors en utilisant l'idée décrite ci-dessus, nous pouvons facilement construire une variété de machines de turing "menteuses": par exemple en notation de type python,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

L'argument le plus compliqué consiste essentiellement à essayer de le faire directement sans faire appel au théorème de récursivité. C'est-à-dire qu'il répète une recette pour construire des fonctions "autoréférentielles". par exemple, étant donné une machine de Turing T, voici une telle recette pour construire un Rsatisfaisant

R(x) = T(R; x)

Tout d'abord, définissez

S(M; x) = T(M(M; -); x)

où par M(M; -), ce que je veux vraiment dire, c'est que nous calculons (en utilisant la description de M) et que nous branchons une description d'une machine de Turing qui, en entrée y, évalue M(M; y).

Maintenant, nous observons que si nous nous branchons Ssur lui-même

S(S; x) = T(S(S; -); x)

nous obtenons la duplication que nous voulons. Donc, si nous définissons

R = S(S; -)

ensuite nous avons

R(x) = T(R; x)

comme voulu.

la preuve de Turing est assez similaire à la preuve de Cantors que la cardinalité des réels ("uncountable") est plus grande que la cardinalité des rationnels ("countable") parce qu'ils ne peuvent pas être mis en correspondance 1-1 mais cela n'est pas noté / souligné dans très nombreuses références (quelqu'un en connaît-il?). (iirc) un prof CS a montré une fois il y a quelques années en classe (je ne sais pas où il l'a obtenu lui-même). dans l'épreuve des Cantors, on peut imaginer une grille de dimension horizontale le n ^ème chiffre du nombre et la dimension verticale le n ^ème chiffre de l'ensemble.

la construction de preuve d'arrêt de Turing est assez similaire, sauf que le contenu du tableau est Halt / Nonhalt pour 1/0 à la place, et l'axe horizontal est la n ^ème entrée, et l'axe vertical est le n ^ème programme informatique. en d'autres termes, la combinaison de programmes informatiques et d'entrées est dénombrable, mais la table / le tableau infini est indénombrable sur la base d'une construction de simulateur de machine universelle qui peut "basculer" un arrêt vers un boîtier non asphalté en supposant qu'il existe une machine de détection d'arrêt (d'où reductio ad absurdam ) .

certaines preuves que Turing avait la construction de Cantors en partie à l'esprit est que son même article avec la preuve d'arrêt parle de nombres calculables comme (le long de) de nombres réels avec des chiffres calculables.

À ce stade, il convient de noter le travail d' Emil Post qui est (à juste titre) crédité d'être un co-découvreur des résultats de base de la calculabilité, bien qu'il ait malheureusement été publié trop tard pour être considéré comme un co-découvreur de la solution du problème Entscheidungsproblem . Il a certainement participé à l'élaboration de la thèse dite Church-Turing .

Le message était motivé par des considérations très philosophiques, à savoir les limites théoriques de la capacité humaine à calculer, ou même à obtenir des réponses précises de manière cohérente . Il a conçu un système, maintenant appelé systèmes post-canoniques , dont les détails sont sans importance, qui, selon lui, pourrait être utilisé pour résoudre tout problème qui peut être résolu de manière soignée par la manipulation de symboles . Fait intéressant, il considérait explicitement les états mentaux comme faisant explicitement partie de la «mémoire», il est donc probable qu'il considérait au moins son modèle de calcul comme un modèle de la pensée humaine dans son intégralité.

Le Entscheidungsproblem considère la possibilité d'utiliser un tel moyen de calcul pour dire, déterminer la théorème de toute proposition exprimable dans le système des Principia Mathematica . Mais le PM était un système explicitement conçu pour pouvoir représenter tout le raisonnement mathématique et, par extension (du moins à l'époque, quand le Logicisme était encore en vogue) tout le raisonnement humain!

Il n'est donc pas très surprenant alors de porter l'attention d'un tel système sur les systèmes canoniques de la poste eux-mêmes, tout comme l'esprit humain, via les œuvres de Frege, Russel et des logiciens du début du siècle, avait tourné son attention vers la faculté de raisonnement. de l'esprit humain lui-même.

Il est donc clair à ce stade que l'auto-référence, ou la capacité des systèmes à se décrire, était un sujet plutôt naturel au début des années 1930. En fait, David Hilbert espérait "bootstrap" le raisonnement mathématique lui-même, en fournissant une description formelle de toutes les mathématiques humaines, qui pourraient ensuite être mathématiquement prouvées cohérentes!

Une fois obtenue l'utilisation d'un système formel pour raisonner sur lui-même, c'est un saut et un saut des paradoxes autoréférentiels habituels (qui ont une histoire assez ancienne ).

Puisque toutes les déclarations en Principia sont présumées être "vraies" dans un certain sens métaphysique, et les Principia peuvent exprimer

le programme prenvoie le résultat trueen entréen

si un programme existe pour décider de tous les théorèmes de ce système, il est assez simple d'exprimer directement le paradoxe du menteur:

ce programme ment toujours.

peut être exprimé par

Le programme pretourne toujours le contraire de ce que les principes mathématiques disent p.

La difficulté est de construire le programme p. Mais à ce stade, il est plutôt naturel de considérer la phrase plus générale

Le programme prenvoie toujours le contraire de ce que le PM dira q.

pour certains arbitraires q. Mais c'est facile à construire p(q)pour n'importe quelle donnée q! Calculez simplement ce que PM prédit qu'il produira et retournez la réponse opposée. Cependant, nous ne pouvons pas simplement remplacer qpar pà ce stade, car pprend qen entrée et qne le fait pas (il ne prend aucune entrée). Changeons notre phrase pour quep cela prenne en compte:

Le programme prenvoie le contraire de ce que dit PMq(r) retournera.

Arg! Mais maintenant, il pfaut 2 éléments d'entrée: qet r, alors qu'il qne faut que 1. Mais attendez: nous voulons pdans les deux endroits de toute façon, ce rn'est pas un nouveau pièce d'information, mais tout de même morceau de données à nouveau, à savoir q! Telle est l'observation critique.

Nous obtenons enfin

Le programme pretourne le contraire de ce que PM ditq(q) retournera.

Oublions cette stupide affaire de "PM dit", et nous obtenons

Le programme p(q)renvoie l'opposé de ce qui q(q)va revenir.

Il s'agit d'un programme légitime à condition que nous ayons un programme qui nous indique toujours ce qui q(q)revient . Mais maintenant que nous avons notre programme p(q), nous pouvons remplacer qpar pet obtenir le paradoxe de notre menteur.