¿Es L Turing decidible?

Question

Por favor, ayúdenme a hacerlo bien, La pregunta es: ¿Es L Turing decidible? donde L ={<M> : M is a TM, which accepts some palindrome

Mis ideas sobre el puf para demostrar que es indecidible son las siguientes. Supongamos que L es decidible y que R es un decididor para ese lenguaje. Construiré un decididor S para A_tm usando R como subrutina.

S = on input <M,w>
1. constructs TM M_w = on input x
           if x != (some palindrome ex 1^n 0 1^n) reject
           else run M on w if M accepts => accept; if M rejects => reject.
2. Run R on M_w
3. If R accepts => accept, if R rejects => reject.

Nota: Supongamos que M acepta w entonces L(M_w) = algún palíndromo, Entonces R(M_w) lo acepta => S acepta. Supongamos que M rechaza o bucles entonces L(M_w) = conjunto vacío. Entonces R(M_w) lo rechaza => S lo rechaza.

Ahora bien, como sabemos que A_tm es indecidible, la suposición era errónea => L es indecidible.

Answer 1

Sí, esta reducción parece correcta. Si $M$ rechaza $w$ , entonces el lenguaje de $M_w$ está vacía. Si $M$ acepta $w$ , entonces el lenguaje de $M_w$ es $\{\mathtt{abcdcba}\}$ (o lo que sea el palíndromo codificado).

Por lo tanto, $M_w$ acepta un palíndromo si y sólo si $M$ acepta $w$ . Hemos reducido el problema de aceptación de la TM al problema de decidir si el lenguaje de una máquina de Turing contiene un palíndromo. Dado $M$ y $w$ creamos la máquina $M_w$ y ejecutar el decidor de palíndromos en él. El decidor de palíndromos devuelve verdadero si $M$ acepta $w$ y falso si no lo hace. Pero el problema de la aceptación de la TM es indecidible; por tanto, también lo es el problema del palíndromo.