Arrêter le problème sans autoréférence

10

Dans le problème de l'arrêt, nous sommes intéressés s'il existe une machine Turing qui peut dire si une machine Turing donnée s'arrête ou non sur une entrée donnée . Habituellement, la preuve commence à supposer qu'un tel existe. Ensuite, nous considérons un cas où nous restreignons à lui-même, puis dérivons une contradiction en utilisant une instance d'un argument diagonal. Je serais intéressé comment la preuve irait-elle si on nous promettait que ? Qu'en est-il de la promesse , où est fonctionnellement équivalent à ?M i T i M i M i M M MTMiTiMiMiMMM

bellpeace
la source
2
Astuce: même si est nécessaire pour ne pas répondre correctement à des questions sur lui - même ou même sur M ' est équivalent à elle, nous pouvons encore nourrir un équivalent M ' et de voir ce qu'il fait. Parce qu'il n'est pas calculable si M ' est équivalent à M , M ne pourra pas dire qu'il a obtenu quelque chose d'équivalent à lui-même. MMMMMM
Andrej Bauer
@AndrejBauer Était-ce juste un indice que vous m'avez donné et je devrais résoudre mon problème réel en utilisant cet indice? Je suis un peu confus, car vous relâchez le problème en disant "pas besoin", où dans mon contexte j'ai la promesse que ne sera pas nourri avec un équivalent M ' . Fondamentalement, je voudrais voir que toute sorte d '"auto-référence" est la chose qui rend les problèmes indécidables. On pensait que c'était le cas lorsque l'on parlait de logique et d'incomplétude. MM
bellpeace
Vous pouvez rompre la promesse et nourrir comme bon vous semble. De toute façon, il ne peut pas vous dire que vous avez rompu la promesse. Si vous pensez que c'est de la triche, alors je nourrirai M des choses qui ne sont pas équivalentes à M parce qu'elles sont comme M mais avec toutes les entrées décalées de 1 , ou quelques-unes. MMMM1
Andrej Bauer
En fait, vos questions ne sont pas bien formulées. Vous devez décrire la preuve réelle que vous avez en tête, puis spécifier précisément ce que vous voulez éviter. Je ne pense pas que tu veux dire , mais autre chose. iM
Andrej Bauer

Réponses:

7

Supposons que HALTS est une MT qui lit son entrée comme une paire et x , où M est un codage de MT et x est n'importe quelle entrée de cette MT.MxMx

Votre question est de savoir si ce qui se passerait si nous supposions HALTS a résolu le problème de l' arrêt pour toutes les entrées tel que x n'est pas un codage d'un TM qui est fonctionnellement équivalent à M .M,xxM

Je prétends que cela implique une contradiction. J'ai trouvé cela sur place, donc je salue toute critique de ma preuve. L'idée de la preuve est que plutôt que de diagonaliser quelque chose sur lui-même, nous faisons deux MT mutuellement récursives qui se comportent différemment sur certaines entrées (donc ne sont pas fonctionnellement équivalentes), mais provoquent autrement des contradictions.

Soit et D 2 deux MT mutuellement récursives (c'est-à-dire que nous pouvons simuler, imprimer, etc., la description de D 2 à l'intérieur du programme de D 1 et vice versa). Notez que nous pouvons créer des MT mutuellement récursives à partir du théorème de récursivité.D1D2D2D1

Définissez et D 2 comme suit: sur l'entrée x , si | x | < 10 (10 choisis arbitrairement), alors D 1 accepte et D 2 boucle. (Ainsi, ils ne sont pas fonctionnellement équivalents).D1D2x|x|<10D1D2

Étant donné l'entrée avec | x | 10 , définir D 1 pour simuler HALTS sur D 2 , x et arrêt si D 2 arrêts ou boucle si D 2 boucles.x|x|10D1D2,xD2D2

Étant donné l'entrée avec | x | 10 , définir D 2 pour simuler HALTS sur D 1 , x et boucle si D 1 arrêts ou arrêt si D 1 boucles.x|x|10D2D1,xD1D1

Notez ensuite que pour tout avec | x | 10 , D 1 (x) arrête ou boucle. Si D 1 s'arrête sur l'entrée x, alors nous savons que HALTS ( D 2 , x) a déterminé que D 2 s'arrête sur l'entrée x. Cependant, D 2 s'arrêtant sur l'entrée x implique que HALTS ( D 1 , x) boucle.x|x|10D1D1D2D2D2D1

Si sur l'entrée x boucle, la contradiction suit de la même manière.D1x

C'est une contradiction à moins que ne soit un codage pour une machine de turing fonctionnellement équivalente à D 1 ou D 2 , auquel cas HALTS a un comportement indéfini. Cependant, x a été choisi arbitrairement parmi toutes les chaînes de taille supérieure à 10 . Ainsi, il reste à montrer qu'il existe une machine de turing avec un codage de taille supérieure à 10 qui se comporte différemment de D 1 et D 2 . Nous pouvons construire une telle machine trivialement. QED.xD1D2x10D1D2

Pensées?

Kurt Mueller
la source
Pourquoi devez-vous vous assurer que et D 2 ne sont pas fonctionnellement équivalents? D1D2
bellpeace
Je pense que vous avez raison de dire que ce n'est pas nécessaire. Mon intention initiale était de diagonaliser sur HALTS ( )D1,D2
Kurt Mueller
Sans cela, la preuve est plus élégante, mais elle me semble de toute façon bonne et correspond exactement à ce dont j'avais besoin.
bellpeace
2

Vous n'êtes toujours pas sorti du bois. Vous rencontrez le même problème, seulement maintenant vous lui donnez une TM différente, en entrée, où vous avez choisi M ' pour être fonctionnellement équivalent à M (disons que vous ajoutez une nouvelle règle à M pour que les mouvements d'ouverture de M sont un pas à droite, un pas à gauche et sinon vous ne faites aucun changement). Vous rencontrerez toujours une contradiction. Vous pouvez essayer d'éliminer toutes les MT équivalentes à M , mais c'est un ensemble indécidable.MMMMMM


Mettre à jour . Correction d'un schéma d'encodage où Désigne la description sous ce schéma d'un TM M et supposons que vous aviez un TM, HMMH

  • n'est pas défini lorsque x est le codage d'une MT qui calcule la même fonction partielle que H (c'est-à-dire que x et H sont fonctionnellement équivalents).H(M,x)xHxH
  • Pour toutes les autres entrées, renvoie vrai si et seulement si M ( x ) s'arrête.H(M,x)M(x)

Maintenant, la construction de diagonalisation habituelle entraîne toujours une contradiction. Définissez un TM parQ

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

Clairement et H sont fonctionnellement inéquivalents, donc nous pouvons laisser x = QH Et trouvez que Q ( x=Q Arrête si et seulement si elle ne s'arrête pas, donc il peut y avoir aucune TM H .Q(Q)H

Rick Decker
la source
Et supposons que j'ai la promesse que ne suis pas un TM fonctionnellement équivalent à M ? Peut-être que je peux étendre ma question dans le PO? iM
bellpeace
1
Supposons que l'on vous donne une telle promesse; Je sais que ce n'est pas calculable. J'ai mis à jour l'OP.
bellpeace
@bellpeace: Comment définissez-vous cela?
Entrée: une paire de nombres entiers de telle sorte que i ne représente pas un TM fonctionnellement équivalent à TM représenté par M . Sortie: 1 si M s'arrête sur i , 0 sinon. Ce problème est-il décidable? (M,i)iM1Mi0
bellpeace
1
@RickyDemer Oui, deux MT sont considérées comme fonctionnellement équivalentes si elles calculent la même fonction partielle. Notez que, comme l'a souligné Andrey, bien que déterminer si et M ' sont équivalents est indécidable, nous pouvons toujours considérer le problème où l'on nous promet que deux TMS d'entrée ne sont pas équivalents, tout comme je l'ai illustré ci-dessus. MM
bellpeace