Turing máquinas y máquinas esquemas

Question

Arthur Dent, utilizando la tecnología de la era espacial todavía no está disponible en la tierra desarrollado un algoritmo que determina si un detiene TM M1 o no cuando comenzaron en una cinta en blanco. Pero luego más tarde, se descubrió que el sentido de la vida, el universo, y todo es 42.

(a) [5] Dado un TM M2, demostrar que Arthur puede determinar si se detiene M2 o no en la entrada 42 mediante el programa que ya desarrollado que determina si un paradas TM M1 o no cuando comenzaron en una cinta en blanco. Si crea una nueva TM en su prueba, dará su esquema máquina.

(b) [5] Supongamos que hay un programa que es más rápido que Arthur pero responde a la pregunta de si una se detiene TM m2 en la entrada 42. Explicar cómo Arthur puede utilizar este algoritmo para determinar si algunas paradas TM M1 cuando se inicia en una cinta en blanco. Si crea una nueva TM en su prueba, dará su esquema máquina.

(c) [5] Hemos demostrado en la clase que que el problema de determinar si un paradas TM M cuando se inicia en una cinta en blanco no es decidible. ¿Es parte (a) o la parte (b) que puede ser utilizado para demostrar que también es indecidible para determinar si un TM M se detiene en la entrada 42?

Puede alguien ayudarme a descifrar lo que mi prof está hablando aquí?

Answer 1

Bienvenido a alguna teoría informática realmente complicado. Trate de comenzar aquí: http://en.wikipedia.org/wiki/Halting_problem

Google máquina de Turing también si usted no está familiarizado con eso.