Reducción de $HALT$ a $A_{TM}$

Question

Conozco la reducción a desde $A_{TM}$ a $ DETENER $.Pero es la siguiente reducción de $ DETENER $ a $A_{TM}$ ¿correcto?

Buscamos una función computable total. $f$ mapeo de $ DETENER $ a $A_{TM}$.La siguiente MT $f$ calcula la reducción $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

creo que la linea if T accepts or rejects, *accept* es correcto, pero sería fantástico si alguien pudiera comprobarlo.

Editar:Encontré las siguientes diapositivas, pero no creo que la construcción sea correcta: http://slideplayer.com/slide/13791105/

Answer 1

Hay múltiples nociones de "reducción". Has descrito correctamente un reducción de muchos uno de $ DETENER $ a $A_{TM}$.La reducción a la que te has vinculado (enlace más específico aquí) es en cambio un reducción de la tabla de verdad.Estos son objetos más generales (por lo que su resultado es más fuerte).Cada uno de ellos, a su vez, está subsumido por la noción mucho más amplia de reducción de turing.

Si bien las reducciones de muchos uno son generalmente la noción predeterminada en la teoría de la complejidad, las reducciones de Turing y las consecuencias resultantes estructura de grados son los predeterminados en la teoría de la computabilidad.Tenga en cuenta que si todo lo que quiero hacer es demostrar la indecidibilidad de algún conjunto, una reducción de Turing a partir de algún conjunto que se sabe que es indecidible es suficiente.

---

Primero, recordemos explícitamente las definiciones de los lenguajes involucrados:

• $A_{TM}=\{\langle M,w angle:M$ se detiene y acepta la entrada $w\}$.

• $HALT=\{\langle M,w angle:M$ se detiene en la entrada $w\}$.

Su propuesta de reducción de $ DETENER $ a $A_{TM}$ es correcto:dado $M$, podemos computablemente construir una nueva máquina $\sombrero{M}$ que acepta precisamente aquellas cadenas en las que $M$ se detiene.(Básicamente, simplemente reemplace todos los estados de "rechazo" en $M$ por estados "aceptar".)

---

Ahora veamos la otra reducción a la que vinculó (enlace más específico aquí).

Básicamente, en lugar de decir "todos los estados detenidos aceptan", el argumento vinculado considera por separado:

• la máquina original, y

• la máquina "contraria" que acepta exactamente cuando la original rechaza y viceversa.

Una respuesta afirmativa para cualquiera de los casos en $A_{TM}$ garantiza una respuesta afirmativa para la máquina original en $ DETENER $.

Desde el principio, no veo ninguna razón para hacer esto en lugar de seguir su argumento, especialmente porque produce un resultado más débil, pero es correcto y suficiente para probar la afirmación más amplia de las diapositivas, es decir, que $A_{TM}$ es indecidible.