Montre que l'ensemble des mémoires de traduction qui visite l'état de départ deux fois sur l'entrée vide est indécidable

Question

Je suis en train de prouver que

$ L_1 = \ {\ langle M \ rangle \ mid M texte {est une machine de Turing et visites} Q_0 \ texte {au moins deux fois sur} \ varepsilon \} \ Notin R $.

Je ne suis pas sûr que de réduire le problème de l'arrêt à ou non. J'ai essayé de construire une nouvelle machine $ M '$ pour $ (\ langle M \ rangle, w) $, de sorte que $ M' visits $ Q_0 $ $ deux fois, IFF $ M $ arrêts sur $ w $. Ceci est $ spécifique Q_0 $ donnée à moi, mais je ne est pas venu à une construction intelligente, qui donnerait l'a demandé. Peut-être qu'il est plus facile de montrer que de $ RE $ et $ Coré $? Il est évident qu'il est en $ RE $, et je dois montrer que L_2 $ ^ {c} $ est pas $ RE $.

Que dois-je faire?

Answer 1

Ne pas rendre plus compliquée qu'elle ne l'est. Au lieu de vous donner une solution complète, je vais vous donner une solution partielle, qui devrait vous permettre de travailler les détails par vous-même:

Chaque TM être transformé en un TM que les visites de son état initial exactement une fois. Pour ce faire, d'introduire un nouvel état $ q ^ '_ 0 $, qui sera le nouvel état de départ. Ensuite, ajoutez un $ \ varepsilon -transition $ de $ q ^ '_ 0 $ à $ Q_0 $. Ceci est le seul moyen de « congé » de l'état q'_0 $ $.

Pour cette machine modifiée, l'acceptation d'exécuter des visites de l'état initial une fois, et se termine dans l'état d'accepter. Ce qui reste à faire est de modifier la machine plus loin, de telle sorte qu'il saute à $ q ^ '_ 0 $, après que la machine était à l'état d'accepter. Mais vous devez assurer que lorsque $ q ^ '_ 0 $ est visité la deuxième fois, vous passer à un nouvel état d'accepter. Mais il est difficile de ne pas enregistrer la fréquence que vous avez visité un état.

Si vous voulez qu'un autre État est visité deux fois, alors vous pouvez toujours fait un détour au début que les visites de cet état (vous enregistrez que la machine est en mode « detour » être en train d'écrire un drapeau sur une bande spéciale). Que vous réacheminer le calcul normale, de sorte que si elle doit visiter l'Etat requis, il visite une copie de cet état. Enfin, lors de l'acceptation, vous sautez à l'état demandé. Conceptuellement, ce n'est pas très différent de réétiquetage les états.