Lenguajes indecidibles y reducibilidad de mapeo

Question

Estoy usando la terminología de Sipser aquí.

¿Puede alguien dar ejemplos de lenguajes A y B tales que podamos demostrar que B es indecidible usando A en una prueba por contradicción pero A no es $\leq_m$ B?

Un ejemplo de esto es $E_{TM}$ como se define en la página 89 de Introducción a la Teoría de la Computación 2a ed de Sipser. Usamos $A_{TM}$ en la prueba por contradicción pero $A_{TM}$ no es redcucible por mapeo a $E_{TM}$.

Gracias de antemano.

Answer 1

Hay muchas de ellas, por ejemplo, toma dos lenguajes A y B tal que A no es recursivo (es decir, indecidible), $A \leq_{T} B$ (donde $\leq_{T}$ denota la reducibilidad de Turing) pero no $A \leq_{m} B$.

Para un ejemplo bastante trivial (ya que se puede resolver considerablemente más fácil), toma $A=HALT$ y $B=\overline{HALT}$. Entonces, claramente $A \leq_{T} B$ (para calcular si $x \in B$, simplemente ejecuta el oráculo para preguntar si $x \in A$ y di que sí si la respuesta del oráculo es no, y di que no si la respuesta del oráculo es sí). Pero si $A \leq_{m} B$, tenemos una función recursiva f tal que $x \in A \iff f(x) \in B$, y luego podemos mostrar que B es recursivamente enumerable: para verificar si $x \in B$ simplemente calcula f(x) y genera HALT, cuando (si sucede) f(x) aparece en la generación de HALT, detente. Este procedimiento es un procedimiento de semidecisión para $B=\overline{HALT}$, por lo tanto, B es recursivamente enumerable. Dado que sabemos que HALT en sí mismo es recursivamente enumerable, tendríamos HALT recursivo, lo cual es una contradicción. Por lo tanto, A no se reduce en sentido m a B, pero no obstante, dado que A se reduce en sentido T a B, y sabemos que A es indecidible, podemos concluir inmediatamente que B es indecidible.

Answer 2

ATM es reducible en mapeo al complemento de ETM. Demostrar la indecidibilidad se puede hacer con el lenguaje original o su complemento. Sin embargo, esto no es el caso para demostrar la no reconocibilidad.