Supongamos que un algoritmo mágico puede resolver el problema de detención ... Úselo para hacer cosas.

Question

Estoy estudiando para un examen final que hasta la próxima semana, y todavía estoy claro en algunos de estos detener la reducción de las preguntas. La lectura a través de mayores exámenes finales (no soluciones), tienen una pregunta bastante común en ellos. Puedo obtener algunos comentarios sobre la lógica utilizada en mi de la solución? Tengo una muy ligera idea de cómo funciona esto y no estoy 100% cómodo con este tipo de problemas, sin embargo.

Supongo que hay algo de mágico algoritmo que determina si una Máquina de Turing M1 detiene cuando se inició en blanco de la cinta.

a) Dada una mt M2, demostrar que se puede determinar si M2 se detiene en la entrada de "42" utilizando el programa desarrollado que determina si M1, se detiene o no en blanco de la cinta.

Para esto, la mejor respuesta que puedo ofrecer es el dibujo de un generalizada de la máquina de esquema para una nueva TM Mx, que se lleva a la entrada en blanco, sobrescribe la entrada con 42, y se ejecuta M2. Alimentación Mx en este mágico algoritmo, a continuación, puede decidir si Mx se detiene en una entrada en blanco, que nos dice si o no cualquier M2 se detiene en una entrada de "42".

Me siento como que me estoy perdiendo algo aquí, ya que este parece demasiado fácil para un 5% del total de la calificación de la prueba final.

b) Suponga que un más rápido mágico algoritmo que puede responder si o no M2 se detiene en la entrada "42". Explique cómo esto puede ser usado para determinar si algunos de los M3 se detiene en una entrada en blanco.

Por esto la teoría de una máquina a Mi que tiene una entrada de "42", borra la entrada, y se ejecuta nuestra M3. Si este algoritmo más rápido puede decidir si Mi detiene con "42" como una entrada, puede decidir si M3 se detiene en una entrada en blanco.

La misma incertidumbre pasa por esta parte.

Siento que esta es una pregunta muy buena para ayudar a mi comprensión de este tema, pero no estoy seguro de si tengo una idea de cómo responder a él. Tenemos una absoluta falta de soluciones para esta clase y el profe proporciona incompleta y scribbly comentarios. Su ayuda es muy apreciada. Saludos!

Answer 1

Las preguntas están escritas un poco de confusión, ya que el uso de $M1$, $M2$, y $M3$ lo hace parecer como si todos estos son específicos de las máquinas ... pero estoy bastante seguro de que quiere decir que se supone que todas son algoritmos que se puede determinar para cualquier máquina si se detiene en una cinta en blanco o no, o con la entrada de "42" o no. De hecho, de lo contrario no sería capaz de resolver estos problemas.

Así, reformular la primera pregunta: Probar que si existe una máquina de $H_B$ que se puede determinar para cualquier descripción de la máquina $M$ si no $M$ se detiene en una cinta en blanco, entonces hay una máquina de $H_{42}$ que se puede determinar para cualquier descripción de la máquina $M$ si $M$ se detiene con la entrada de "42" o no.

Por lo que su intuición básica es correcto en que construimos $H_{42}$$H_B$, pero, como era de esperar, es un poco más complicado para hacer este trabajo:

En primer lugar, dado que cualquier máquina $M$, vamos a $M_{42}$ será el equipo que, cuando se da un vacío de cinta, primero pone "42" en la entrada y, a continuación, ejecuta la máquina de $M$. Ahora vamos a $Create_{M42}$ ser una máquina que, cuando se administra cualquier máquina $M$, se crea la máquina de $M_{42}$. Finalmente, îf estamos dada la existencia de $H_B$, entonces podemos construir la máquina de $H_{42}$ de que anexando la máquina de $Create_{M42}$$H_B$:

Dado cualquier máquina $M$, cuando se presentó a la $H_{42}$, $H_{42}$ primero se ejecutará la rutina de $Create_{M42}$, y así escribir la descripción de la máquina de $M_{42}$ en la cinta. De esta forma, se obtiene de la fed en $H_B$ que, como recordamos, se comprueba si la máquina en la entrada se detendrá o no se les da un espacio en blanco de la cinta. Así, como parte de $H_{42}$, $H_B$ va a decir "sí, se detiene!" si y sólo si $M_{42}$ se detiene en una cinta vacía que es si y sólo si la máquina no $M$ se detiene cuando se da entrada "42". Por lo tanto, como un todo, $H_{42}$ va a decir "Sí, se detiene!" Si y sólo si la máquina no $M$ se detiene cuando se da entrada "42". ... que es exactamente el comportamiento deseado.

Ahora que puede ver cómo realmente construcción$H_{42}$$H_B$, estoy seguro de que usted puede averiguar cómo hacerlo de la otra manera, así como para la pregunta b)