Mostrando que el conjunto de memorias de traducción, que visitan el estado de partida dos veces en la entrada vacía es indecidible

Question

Estoy tratando de demostrar que

$ L_1 = \ {\ langle M \ rangle \ mediados M \ text {es una máquina de Turing y visitas} q_0 \ text {al menos dos veces en} \ varepsilon \} \ notin R $.

No estoy seguro de si se debe reducir el problema de la parada a la misma o no. Traté de construir una nueva máquina $ M '$ por $ (\ langle M \ rangle, w) $, de manera que $ M' $ $ visitas q_0 $ dos veces, IFF $ M $ se detiene en $ W $. Esta es específica $ $ q_0 dado a mí, pero no llegó a ninguna construcción inteligente, lo cual produciría la solicitó. Tal vez sea más fácil de demostrar que de $ $ RE y no Core $ $? Es obvio que es de $ $ RE, y tengo que demostrar que L_2 $ ^ {c} $ no está en $ $ RE.

¿Qué debo hacer?

Answer 1

No hacer esto más complicado de lo que es. En vez de darle una solución íntegra, voy a darle una solución parcial, que debería permitirle trabajar en los detalles en solitario:

Cada TM puede convertir en una TM que las visitas a su estado inicial exactamente una vez. Para ello, introducir un nuevo estado $ ^ q '_ $ 0, que será el nuevo estado de inicio. A continuación, añadir un $ \ varepsilon $ -Transición de $ ^ q '_ $ 0 a $ q_0 $. Esta es la única forma de "licencia" del estado q'_0 $ $.

En esta máquina modificada, un aceptando ejecutar visitas el estado inicial una vez, y termina en el estado de aceptación. Lo que queda por hacer es modificar la máquina aún más, de manera que salta de nuevo a $ ^ q '_ $ 0, después de que la máquina estaba en el estado de aceptación. Pero hay que asegurar que cuando q $ ^ '_ $ 0 es visitado por segunda vez, va a saltar a un nuevo estado de aceptación. Pero no es difícil registrar la frecuencia con la que ha visitado un estado.

Si desea que otro estado es visitado dos veces, entonces siempre se puede hecho un desvío en el principio de que las visitas este estado (que registran que la máquina está en el modo de "desvío" estar escribiendo una bandera en una cinta especial). Lo que redireccionar el cálculo normal, de tal manera que si se debe visitar el estado solicitado que visita una copia de este estado. Por último, cuando se acepta, se salta de nuevo al estado solicitado. Conceptualmente, esto no es muy diferente a volver a etiquetar los estados.