Una pregunta relacionada con una máquina de Turing con un estado inútil

10

Bien, aquí hay una pregunta de una prueba anterior en mi clase de Teoría de la computación:

Un estado inútil en una TM es uno que nunca se ingresa en ninguna cadena de entrada. Deje que Demuestre que es indecidible.U S E L E S S T M

USELESSTM={M,qq is a useless state in M}.
USELESSTM

Creo que tengo una respuesta, pero no estoy seguro de si es correcta. Lo incluirá en la sección de respuestas.

HermanoJack
fuente
¡En el futuro, por favor incluya sus intentos en la pregunta!
Raphael
1
@Rapael lo hizo. Lo escribí cuando hice la pregunta, pero dada mi falta de reputación no pude publicarlo durante al menos 8 horas. Me interesaría saber si es una respuesta válida.
BrotherJack
No, solo quería incluirlo en la pregunta si hay puntos específicos en los que no está seguro.
Raphael

Respuestas:

12

Esto es claramente reducible del problema de detención. Si una máquina no se detiene en la entrada , cualquier estado final es "inútil". Dada una entrada para el problema de detención, es fácil construir que se detenga en cada entrada (por lo tanto, su estado final no es inútil) si y solo si detiene en . De esa forma, puede decidir detener el problema si puede decidir , lo que genera una contradicción.x M , x M x M x U S E L E S S T MMxM,xMxMxUSELESSTM

Sonó.
fuente
... y dado que el problema de detención es indecidible, este problema también es indecidible, ¿correcto?
BrotherJack
De hecho, esto es correcto.
Ran G.
2

A los fines de esta prueba, asumiremos que es decidible para mostrar una contradicción.USELESSTM

Cree TM que haga lo siguiente:R

  • Convierte TM en un autómata pushdown con una pila relajada (es decir, sin requisito de LIFO). Esto es equivalente a un gráfico dirigido que detalla la transición entre los estados deP MMPM
  • Marcar el estado de inicio de .P
  • Desde el estado inicial, comience una búsqueda de amplitud a lo largo de cada borde de salida que marca cada nodo sin marcar.
  • Cuando finaliza la búsqueda, si hay nodos no marcados que coinciden con , acepte ; de lo contrario rechazar .q

Luego cree TM = "En la entrada $$S

  1. Cree TM como se muestra arriba.R
  2. Ejecutar en .RqR
  3. Si devuelve aceptar, aceptar ; si rechaza, rechaza " RRR

Por lo tanto, si es un elemento decisivo para entonces es un elemento decisivo para (el problema de aceptación). Dado que se ha demostrado que es indecidible (ver Teoría de la teoría del cálculo de Michael Sipser 4.11 en la página 174), hemos llegado a una contradicción. Por lo tanto, la hipótesis original es incorrecta y es indecidible.U S E L E S S T M S A T M A T M U S E L E S S T MRUSELESSTMSATMATMUSELESSTM

HermanoJack
fuente
¿Cuál es el significado de convertir una TM en una PDA con una pila relajada?
Ran G.
1
¿Se supone que el decisor existe? si es así, no necesita describir su acción. De hecho, no puede describir su acción, ya que realmente no existe. Todo lo que sabe es que responde sí / no según si la entrada está en o no . LRL
Ran G.