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

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 à ? $T$ $M$ $i$ $T$ $i$ $M$ $i \not = M$ $i \not = M^\prime$ $M^\prime$ $M$

computability undecidability halting-problem bellpeace
la source

Astuce: même si

est nécessaire pour ne pas répondre correctement à des questions sur lui - même ou même sur

est équivalent à elle, nous pouvons encore nourrir un équivalent

et de voir ce qu'il fait. Parce qu'il n'est pas calculable si

est équivalent à

ne pourra pas dire qu'il a obtenu quelque chose d'équivalent à lui-même.

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

M

$M$

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

. 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.

M

$M$

M^{'}

$M^\prime$

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

choses qui ne sont pas équivalentes à

parce qu'elles sont comme

mais avec toutes les entrées décalées de

, ou quelques-unes.

M

$M$

M

$M$

M

$M$

M

$M$

1

$1$

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.

i \neq M

$i \neq M$

Andrej Bauer

Réponses:

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

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 n'est pas un codage d'un TM qui est fonctionnellement équivalent à . $\langle M,x \rangle$ $x$ $M$

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 deux MT mutuellement récursives (c'est-à-dire que nous pouvons simuler, imprimer, etc., la description de à l'intérieur du programme de et vice versa). Notez que nous pouvons créer des MT mutuellement récursives à partir du théorème de récursivité. $D_1$ $D_2$ $D_2$ $D_1$

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

Étant donné l'entrée avec , définir pour simuler HALTS sur et arrêt si arrêts ou boucle si boucles. $x$ $|x| \ge 10$ $D_1$ $\langle D_2, x \rangle$ $D_2$ $D_2$

Étant donné l'entrée avec , définir pour simuler HALTS sur et boucle si arrêts ou arrêt si boucles. $x$ $|x| \ge 10$ $D_2$ $\langle D_1, x \rangle$ $D_1$ $D_1$

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

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

C'est une contradiction à moins que ne soit un codage pour une machine de turing fonctionnellement équivalente à ou , auquel cas HALTS a un comportement indéfini. Cependant, été choisi arbitrairement parmi toutes les chaînes de taille supérieure à . 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 et . Nous pouvons construire une telle machine trivialement. QED. $x$ $D_1$ $D_2$ $x$ $10$ $D_1$ $D_2$

Pensées?

Kurt Mueller
la source

Pourquoi devez-vous vous assurer que

ne sont pas fonctionnellement équivalents?

D_{1}

$D_1$

D_{2}

$D_2$

bellpeace

Je pense que vous avez raison de dire que ce n'est pas nécessaire. Mon intention initiale était de diagonaliser sur HALTS (

)

⟨ D_{1}, D_{2} ⟩

$\langle D_1, D_2 \rangle$

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

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 pour être fonctionnellement équivalent à (disons que vous ajoutez une nouvelle règle à pour que mouvements d'ouverture de 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 à , mais c'est un ensemble indécidable. $M'$ $M'$ $M$ $M$ $M'$ $M$

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

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

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

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

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

Rick Decker
la source

Et supposons que j'ai la promesse que

pas un TM fonctionnellement équivalent à

? Peut-être que je peux étendre ma question dans le PO?

i

$i$

M

$M$

bellpeace

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

ne représente pas un TM fonctionnellement équivalent à TM représenté par

. Sortie:

s'arrête sur

sinon. Ce problème est-il décidable?

(M, i)

$(M, i)$

i

$i$

M

$M$

1

$1$

M

$M$

i

$i$

0

$0$

bellpeace

@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

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.

M

$M$

M^{'}

$M^\prime$

bellpeace