Est-il possible que le problème d'arrêt soit résolu pour toutes les entrées à l'exception du code de la machine?

9

Cette question m'est venue à propos du problème d'arrêt et je n'ai pas pu trouver une bonne réponse en ligne, me demandant si quelqu'un pouvait m'aider.

Est-il possible que le problème d'arrêt soit décidable pour n'importe quelle MT sur n'importe quelle entrée tant que l'entrée n'est pas la MT elle-même? Fondamentalement:

Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

Cela résout apparemment la contradiction. Lorsque nous appelons les arrêts paradoxaux (Halts), nous ne pouvons pas nous attendre à un comportement cohérent, mais tous les autres appels à Halts (et Halts) sont légitimes et résolubles.

Je comprends que ce n'est pas intuitif. Si un motif dans les bits pouvait révéler le comportement de tous les programmes possibles, pourquoi se désagrégerait-il soudainement lorsque la MT et l'entrée correspondent? Mais pouvons-nous mathématiquement éliminer cela comme une possibilité?

Et ce problème d'arrêt réduit ne serait pas du tout inintéressant. Même s'il existait un programme significatif qui prenait son propre code en entrée, il pouvait être réécrit de manière triviale pour fonctionner sur une entrée légèrement différente. Bien sûr, cette suggestion rend encore moins compréhensible pourquoi une solution d'arrêt pourrait exister avec cette seule mise en garde, mais encore une fois, pouvons-nous vraiment éliminer mathématiquement cette possibilité?

Merci pour toute aide.

CS101
la source
7
La décidabilité n'est pas affectée par des changements finis.
il existe un nombre infini de MT équivalentes et il n'y a aucun moyen (décidable) de détecter des TM équivalentes (c'est-à-dire qu'il est essentiellement le même que le problème d'arrêt lui-même). cependant, il existe des «failles» complexes; essayez Informatique Chatter pour une analyse approfondie du problème de l' arrêt lié à thm automatisé prouver etc ... pourrait essayer de faire cuire cela dans une réponse ...
VZN
Retouche ma question pour être un peu plus claire, désolé si je trompe quelqu'un.
CS101
La réponse est non, comme dans cette réponse cstheory.stackexchange.com/questions/2853/…
Mohammad Alaggan

Réponses:

4

Mais nous pouvons facilement contourner votre restriction. Supposons un programmeG qui inverse les bits de l'entrée et appelle votre H sur le résultat, puis définissez !Havec tous les bits inversés (ie 0 pour 1s, 1s pour 0s). Ensuite, nous pouvons appeler votreH avec G(!H) et nous revenons au problème d'origine.

Jack Aidley
la source
Je vous remercie. Après avoir lu la réponse de @David Richerby, j'ai commencé à penser que c'était la réponse. Si nous pouvons construire un Q 'fonctionnellement équivalent pour tous les programmes Q, alors nous pouvons à nouveau décider de l'arrêt de tous les problèmes, pas seulement ceux de la diagonale. Je vois que c'est ce que vous dites.
CS101
12

Rappelons la preuve standard de l'indécidabilité du problème d'arrêt. Supposons qu'une machine H décide du problème d'arrêt et laissez Q être la machine qui, en entrée M les usages H pour déterminer si M(M) s'arrête et, si oui, Q boucles; autrement,Q s'arrête. Maintenant,Q(Q) s'arrête si, et seulement si, il ne s'arrête pas.

Est-il possible que le problème d'arrêt soit décidable pour n'importe quelle MT sur n'importe quelle entrée tant que l'entrée n'est pas la MT elle-même?

Non. Si vous modifiez la définition du problème d'arrêt de cette manière, la preuve fonctionne toujours. Peu nous importe ce qui se passe quand H reçoit H en entrée parce que la contradiction vient après que nous donnons une entrée Q,Q à H.

Deuxièmement, si vous avez modifié Hpour détecter cette entrée, nous pourrions obtenir la même contradiction en utilisant une autre machine Q cela équivaut à Q en ce sens que, pour toute entrée w, Q(w) s'arrête si, et seulement si, Q(w) s'arrête. Il y en a une infinité etH ne peut pas tous les détecter car il est indécidable que deux machines de Turing soient équivalentes.

David Richerby
la source
3
Le dernier paragraphe à lui seul peut suffire à répondre à la question: vous ne pouvez pas coder en dur tous les encodages de machines équivalentes, quelle que soit l'adaptation finie (basée sur la sémantique) que vous souhaitez effectuer. (Cela ne veut pas dire que le reste de votre article ne vaut pas la peine d'être lu!)
Raphael
Merci pour la réponse. L'indécidabilité de savoir si les programmes sont fonctionnellement équivalents n'est-elle pas elle-même dérivée de l'indécidabilité du problème d'arrêt? Pourquoi ne s'agirait-il pas d'un raisonnement circulaire?
CS101
1
@ CS101: l'indécidabilité de HALTest un théorème une fois pour toutes, on ne "triche" pas quand on l'utilise pour montrer qu'il est impossible de résoudre un autre problèmeHALTqui essaie de contourner la restriction. Par ailleurs, nous savons de façon pragmatique comment prouver la fin ou la non-fin de nombreux programmes pratiques (mais pas tous les programmes). Cependant, prouver l'équivalence des programmes s'avère beaucoup plus difficile dans la pratique (même s'ils sont tous deux indécidables).
cody
Confus moi-même, j'ai oublié que le problème d'arrêt complet est toujours le même selon ma conjecture. Merci.
CS101