Decidibilidad de la máquina de Turing

Question

He estado trabajando en este problema durante varias horas, pero no he sido capaz de encontrar una solución: ¿Es decidible el siguiente problema? Dado un TM M, si existe un w tal que M entra en cada uno de sus estados durante el cálculo sobre w.

Intenté usar la reducción para demostrar que no lo es, pero no se me ocurrió nada. También pensé en la dirección de que es decidible, pero no había ningún número finito de configuración de la que podría dar el límite de tiempo.

Agradeceremos cualquier ayuda.

Answer 1

Creo que se puede reducir el problema de halting a esto sin usar resultados elaborados. Digamos que usted comienza a partir de cualquier TM $M$ con un estado $q_{stop}$ . Los otros estados son $q_0,q_1,\dots,q_n$ . Puedes construir la máquina de Turing $M'$ que simula $M$ pero tiene un símbolo más $X$ en el alfabeto. En $q_{stop}$ la máquina $M'$ va a la derecha de la banda, llega al primer símbolo en blanco y escribe su nuevo símbolo $X$ . Lo hace con un nuevo estado $q'$ . Entonces, $M'$ tiene transiciones etiquetadas por $X$ : $q'\to q_0\to q_1\to\dots\to q_n\to q_{stop}'$ donde $q_{stop}'$ es un nuevo estado, y el estado de parada de $q'$ . En total, $M'$ tiene los estados de $M$ más dos nuevos estados: $q'$ y $q_{stop}'$ y $M'$ visita todos los estados el $w$ si $M$ se detiene en $w$ . Por lo tanto, su problema es indecidible.

Answer 2

No, no es decidible. Creo que probablemente se deduce del teorema de Rice, pero es posible construir una prueba sin él.

Shannon demuestra que para cada máquina de Turing existe una máquina de Turing de dos estados que la simula. Añadiendo un par de caracteres al alfabeto y un par de estados de configuración que garanticen que estarán en la cinta, podemos asegurarnos de que los dos estados "centrales" son visitados antes de que comience el cálculo propiamente dicho. A continuación, podemos añadir un estado "Parada" y sustituir las transiciones de parada en la máquina de dos estados "central" por transiciones al estado "Parada". Así, nuestra máquina construida visita cada uno de sus estados si la máquina original se detiene.

Supongamos que podemos decidir si existe una entrada $w$ en la que un TM $M$ se detiene. Entonces podemos decidir el problema de detención: dado TM $M'$ y entrada $w'$ y preguntó si $M'$ se detiene en la entrada $w'$ podemos construir una máquina $M$ que descarta su entrada, establece $w'$ en la cinta, y simula $M'$ .