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?

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.

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

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 $\langle M\rangle$ les usages $H$ pour déterminer si $M(\langle M\rangle)$ s'arrête et, si oui, $Q$ boucles; autrement,$Q$ s'arrête. Maintenant,$Q(\langle Q\rangle)$ 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 $\langle H\rangle$ en entrée parce que la contradiction vient après que nous donnons une entrée $\langle Q\rangle, \langle Q\rangle$ à $H$.

Deuxièmement, si vous avez modifié $H$pour 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é et$H$ ne peut pas tous les détecter car il est indécidable que deux machines de Turing soient équivalentes.