Indecidibilidad del problema detener

Question

Uno puede demostrar por reducción de la especial detener el problema de $H_S$ el undecidability de la (general) detener el problema de $H$. Es a la inversa también es posible? Es decir, es posible demostrar la undecidability de la especial detener el problema de $H_S$ por la reducción de la (general) detener el problema de $H$?

El lenguaje de $H_S$ de la especial detener problema:

$H_S := \{w: w \mbox{ encodes a Turing machine }M_w \mbox{ and } M_w \mbox{ accepts } w \}$

El lenguaje de $H$ el (general) detener problema:

$H:=\{\langle w,x\rangle\;:\;w \mbox{ encodes a Turing machine }M_w \mbox{ and } M_w \mbox{ accepts } x\}$

En ambas definiciones se $w,x\in \Sigma^*$ para algunos alfabeto $\Sigma$.

Answer 1

Aquí es cómo reducir el problema general a la especial. Dada una máquina $w$ y entrada $x$, aplicar el teorema de s-m s-m-n para obtener un % de máquina $w'$que, independientemente de su entrada, simula la ejecución de la máquina $w$ % entrada $x$. Entonces $w' \in H_S$ si y sólo si $\langle w,x\rangle \in H$.

La reducción del contraria es trivial: $w \in H_S$ si y sólo si $\langle w,w\rangle \in H$.

Answer 2

En resumen, sí. En el especial de detener problema, desea determinar si una máquina de Turing arbitraria con el valor de entrada se detendrá o no, mientras que con la detención de problema que se quiere saber si una máquina de Turing arbitraria con entrada arbitrarios detendrá o no. Claramente, ya que el problema es un caso particular de la general, demostrando el general es suficiente prueba de la especial.

Sin embargo, es mucho más difícil demostrar el general detener el problema de la especial, por lo cual se tiende a probar el especial, y desde que demostrar la general.