Y at-il relation concrète entre le théorème d'incomplétude de Gödel, le problème et les machines universelles arrêt Turing?
https://cs.stackexchange.com/questions/419
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai toujours pensé vaguement que la réponse à la question ci-dessus était positive sur les lignes suivantes. Le théorème d'incomplétude de Gödel et l'indécidabilité du problème de l'arrêt des deux étant des résultats négatifs sur des décidabilité et établis par des arguments en diagonale (et dans les années 1930), ils doivent en quelque sorte deux façons de voir les mêmes questions. Et je pensais que Turing a utilisé une machine de Turing universelle pour montrer que le problème est insoluble arrêt. (Voir aussi question de ce math.SE.)
Mais maintenant que (l'enseignement d'un cours de calculabilité) Je regarde de plus près sur ces questions, je suis plutôt déconcerté par ce que je trouve. Je voudrais donc une aide à redresser mes pensées. Je me rends compte que, d'une part argument de la diagonale de Gödel est très subtile: il faut beaucoup de travail pour construire une déclaration arithmétique qui peut être interprété comme dire quelque chose au sujet de son propre dérivabilité. D'autre part, la preuve de l'indécidabilité du problème de l'arrêt que j'ai trouvé est extrêmement simple , et ne mentionne même pas explicitement les machines de Turing, et encore moins l'existence de machines de Turing universelle.
Une question pratique sur les machines de Turing universelles est de savoir s'il est d'une importance que l'alphabet d'une machine de Turing universelle soit identique à celle des machines de Turing qu'il simule. Je pensais que ce serait nécessaire pour concocter un argument de la diagonale appropriée (ayant la simulation de la machine elle-même), mais je ne l'ai pas trouvé aucune attention à cette question dans la collection ahurissante des descriptions de machines universelles que je trouve sur le net. Sinon pour le problème de l'arrêt, sont des machines de Turing universelle utile dans tout argument diagonale?
Enfin, je suis confus par cette autre section du même article WP, qui dit qu'une forme plus faible de incomplétude de Gödel résulte du problème de l'arrêt: « une axiomatisation complète, cohérente et son de toutes les déclarations au sujet des nombres naturels est inatteignable » où « son » est censé être l'affaiblissement. Je sais une théorie est cohérente si l'on ne peut pas tirer une contradiction, et une théorie sur des nombres naturels semble vouloir dire que tous les vrais déclarations sur des nombres naturels peuvent être obtenus en elle; Je sais que Gödel dit la théorie de telle n'existe pas, mais je ne vois pas comment une telle bête hypothétique pourrait manquer d'être son, par exemple, également des déclarations Derive qui sont faux pour les nombres naturels: la négation d'une telle déclaration serait vrai , et donc par l'exhaustivité également dérivable, ce qui serait en contradiction avec la cohérence.
J'apprécierait des éclaircissements sur l'un de ces points.
La solution
Je vous recommande de vérifier blog Scott Aaronson sur une démonstration du théorème d'incomplétude via des machines de Turing et théorème de Rosser. Sa preuve du théorème incomplétude est extrêmement simple et facile à suivre.
Autres conseils
(Ceci est censé être un commentaire à la réponse de Suresh, mais il est tout simplement trop long pour là-bas. Je présente mes excuses à l'avance qu'il ne répond pas vraiment à la question de Marc.)
Je trouve la réponse de Neel problème Enrayer , ensembles: non calculable? preuve mathématique commune sur CSTheory et blog de Andrej Bauer insatisfaisante pour deux raisons.
D'abord, nous ne sont généralement pas besoin de tout le jargon catégorie théorétique pour expliquer la connexion. L'existence d'une langue indécidable est sous-entendu par théorème de Cantor , qui a une diagonale très élémentaire preuve. La raison en est que l'ensemble des programmes est equinumerous à $ \ mathbb {N} $. D'autre part, étant donné que chaque langue peut être considérée comme un sous-ensemble de $ \ mathbb {N} $, et donc l'ensemble de toutes les langues est equinumerous à $ \ mathcal {P} (\ mathbb {N}) $. D'après le théorème de Cantor, il n'y a pas de surjection $ \ mathbb {N} $ sur $ \ mathcal {P} (\ mathbb {N}) $, et nous savons donc il doit exister un langage indécidable.
En second lieu, la preuve ci-dessus est peu satisfaisante, car nous voulons aussi « voir » par exemple d'une langue indécidable raisonnable. La preuve ci-dessus peut être considérée comme un argument de comptage et donc pas vraiment « constructive » dans ce sens. Turation a découvert le problème de l'arrêt comme un exemple.
Machines universelles de Turing sont utiles pour certains arguments en diagonale, par exemple dans la séparation de certaines classes dans le hiérarchies de temps ou complexité : la machine universelle est utilisée pour prouver qu'il ya un problème de décision dans $ \ mbox {} DTIME (f (n ) ^ 3) $, mais pas $ \ mbox {} DTIME (f (n / 2)) $. (Limites de meilleures se trouvent dans l'article WP)
Cependant, pour être parfaitement honnête, si vous regardez attentivement, la machine universelle n'est pas utilisé dans la partie `Negative »: les le suppose la preuve il y a une machine $ K $ qui résoudrait une version limitée dans le temps du problème de l'arrêt et procède ensuite à la construction $ ¬KK $. (Aucune machine universelle ici) La machine universelle est utilisée pour résoudre la version limitée dans le temps du problème de l'arrêt dans une plus grande quantité de temps.
« Sinon pour le problème de l'arrêt, sont des machines de Turing universelle utiles dans tout argument diagonale? »
Le théorème de riz est essentiellement la généralisation de diagonalisation contre les machines de Turing. Il montre qu'il n'y a absolument aucune propriété sur les machines de Turing que vous pouvez décider pour toutes les machines de Turing avec un seul algorithme, à moins que la propriété est valable pour toutes les machines de Turing ou aucune machine de Turing. Notez le fait que la tenue de la propriété pour toutes les machines de Turing ou aucune machine de Turing empêche l'objet de diagonalisation d'être une machine de Turing, donc il ne peut pas être sur la liste en premier lieu en contradiction avec la décision au sujet de la propriété. En effet, c'est le que chose qui empêche l'objet diagonalisation d'être sur la liste et contredisant la décision au sujet de la propriété, qui est toutes les propriétés des machines de Turing sont indécidables. Ce modèle de l'objet diagonalisation besoin d'être membre de la liste des choses que vous essayez de prendre une décision au sujet, et réduire à néant encore la décision, est l'abstraction critique que le théorème de Lawvere (référencé dans le lien dans la réponse de Suresh) capture afin de généraliser pleinement la notion de diagonalisation. Maintenant, puisque nous savons par expérience que presque tous les diagonalisation semble avoir la propriété commune de conduire à un résultat extrêmement important dans la logique mathématique, qui fait le théorème de Lawvere tout à fait l'outil intéressant.
