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
Creo que tengo una respuesta, pero no estoy seguro de si es correcta. Lo incluirá en la sección de respuestas.
computability
undecidability
formal-methods
turing-machines
HermanoJack
fuente
fuente
Respuestas:
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 MM x M,x Mx M x USELESSTM
fuente
A los fines de esta prueba, asumiremos que es decidible para mostrar una contradicción.USELESSTM
Cree TM que haga lo siguiente:R
Luego cree TM = "En la entrada $$S
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 MR USELESSTM S ATM ATM USELESSTM
fuente