La preuve de l’indécidabilité du problème d’arrêt triche-t-elle en inversant les résultats?

J'ai du mal à comprendre le problème de l'arrêt de Turing.

Sa preuve suppose qu'il existe une machine magique qui pourrait déterminer si un ordinateur s'arrêterait ou ferait une boucle pour toujours pour une entrée donnée. Ensuite, nous attachons une autre machine qui inverse la sortie et nous avons une contradiction et donc H ne peut pas exister.$H$$H$

Ce qui m'inquiète, c'est qu'il semble que nous disions qu'une réponse est fausse parce que nous l'avons renversée. Par analogie, s'il existe une machine appelée telle qu'elle génère une réponse correcte sur certaines entrées et une réponse incorrecte sur d'autres. Ensuite, nous attachons une autre machine qui inverse le résultat de A, de sorte que la combinaison des deux machines est en contradiction avec la façon dont A est défini. Les deux machines génèrent désormais des réponses incorrectes pour les entrées A définies pour générer des réponses correctes et des réponses correctes pour les entrées A définies pour générer des réponses incorrectes. Serait-ce appelé une contradiction, et donc il n'existe pas de machine qui génère une réponse correcte sur certaines entrées et des réponses incorrectes sur d'autres?$A$$A$$A$$A$$A$

Version courte: les sorties des machines ne sont pas correctes ou incorrectes, elles sont juste contradictoires, ce qui prouve que la machine initiale qui décide si la machine d'entrée s'arrête ou non sur la chaîne donnée ne peut pas exister.

Version longue : nous allons d'abord esquisser la preuve (ou au moins une version de celle-ci - il y en a beaucoup).

1. Supposons que nous avons une machine de Turing qui décide si la machine de Turing M arrêts sur l' entrée x ou non.$\mathrm{HALT}(\langle M\rangle, x)$$M$$x$
2. Utilisation on construit une machine F L I P ( ⟨ M ⟩ , x ) qui utilise H A L T pour vérifier si M arrêts sur x ou non, fait alors l'inverse, à savoir si M arrêts sur x , F L I P boucle, si M ne s'arrête pas sur x , F L I P s'arrête.$\mathrm{HALT}$$\mathrm{FLIP}(\langle M\rangle, x)$$HALT$$M$$x$$M$$x$$\mathrm{FLIP}$$M$$x$$\mathrm{FLIP}$
3. Enfin , nous créons un TM (j'ai manqué de bons noms), qui prend la description d'un TM et exécute F L I P avec entrée ( ⟨ M ⟩ , ⟨ M ⟩ ) , à afficher ce F L I Sorties $\mathrm{C}(\langle M \rangle)$$\mathrm{FLIP}$$(\langle M \rangle, \langle M \rangle)$$\mathrm{FLIP}$

Il est important de noter que tant que le décideur existe, chacune de ces étapes est simple à mettre en œuvre; F L I P doit simplement utiliser H A L T pour vérifier que faire, et C seulement dupliquer son entrée pour passer à F L I P .$\mathrm{HALT}$$\mathrm{FLIP}$$\mathrm{HALT}$$\mathrm{C}$$\mathrm{FLIP}$

La contradiction se pose quand on regarde ce qui se passe quand nous courons . Soit C s'arrête lorsqu'il est donné en entrée ou non. H A L T décidera ceci:$\mathrm{C}(\langle\mathrm{C}\rangle)$$\mathrm{C}$$\mathrm{HALT}$

• Si arrêts sur l' entrée ⟨ C ⟩ , H A L T dira Y e s , mais alors F L I P en boucle, de sorte que C fera une boucle, en contradiction avec H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{Yes}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$
• Si boucles sur l' entrée ⟨ C ⟩ , H A L T dira N o , mais alors F L I P arrêtera, si C est également arrêté, ce qui contredit H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{No}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$

Comme chacune des étapes de la construction est clairement valable, nous ne pouvons que conclure que ne peut pas exister; nous avons construit un cas où, quoi qu'il dise, H A L T ne peut pas décider quoi produire, c'est-à-dire que le problème est indécidable. Juste pour vraiment marteler un peu le point, H A L T ne peut pas exister - c'est-à-dire qu'il ne peut pas y avoir de MT qui décide du problème de l'arrêt - parce qu'il y a au moins un cas que nous avons explicitement construit là où il n'y en a pas logiquement réponse possible. N'oubliez pas qu'un décideur n'est pas autorisé à produire la mauvaise réponse et doit produire quelque chose, mais dans le cas que nous avons construit, les deux réponses possibles sont fausses.$\mathrm{HALT}$$\mathrm{HALT}$$\mathrm{HALT}$

Vous discutez de deux significations différentes de «contredire».

Dans votre analogie, la machine A et sa modification inversée se contredisent juste en ce sens que leurs sorties sont toujours différentes. (Par exemple, ils pourraient implémenter deux fonctions de test sur des nombres entiers, " x ≤ 5?" Et " x > 5?"). preuves.

Dans les preuves logiques, cela signifie quelque chose de plus fort: quelque chose qui est tout simplement impossible. Par exemple, une fonction qui renvoie «vrai» sur toutes les entrées de plus de 5, et «faux» sur toutes les entrées de moins de 10 - ce qui est contradictoire dans ce sens plus fort, car pour, disons, 7, sa sortie devrait être à la fois «vraie» et "faux", mais ce ne sont pas les mêmes. L'argument de Turing montre que le programme d'arrêt est contradictoire au sens fort: en supposant qu'il mène à quelque chose qui est impossible, ou déjà connu pour être faux.

$x$$x$$f(n)$$n$

$f(m)$

$m$$m$

$m$$P_m$$f(m)+1$$P_m$$P_m$$m$$m$$|m|$$|m|$$m$$|m| \approx \log_{10} m$$T$$P_m$$T + \log_{10} m$$m$$m=2T$$T + \log_{10} m \leq m$$f(m)$$P_m$$f(m) \geq f(m) + 1$. Nous avons atteint une contradiction.