Duda materia: reducciones

[jtcaraball]

Hola! En la clase de ayer vimos una reducción de la forma:

def f(M, w):
  def M'(e):
    if e cumple con a:
      return M(w)
    else:
      Loop
  return M'

Donde M es una máquina cuyo lenguaje son todas las palabras C(M)0000w tal que M acepta a w.

Uno no podría reducir de esta forma este lenguaje a casi cualquier otro de la forma: C(M)0000e donde M acepta a e, mientras que la condición e cumple con a sea fácil de computar? En particular si la condición sobre e es algo de formato.

Creo que mi duda viene de lo poderosa que se ve esta reducción 😅

[juanreutter]

Claro, esta reduccion te sirve para reducir desde el lenguaje de todas las palabras de la forma C(M)0000w tal que M acepta a w, a cualquier lenguaje de palabras de la forma C(M') tal que M' acepte a cosas que se puedan verificar de forma computable: solo tienes que cambiar el if.

Eso esta bien. De hecho, uno puede demostrar lo siguiente casi igual. Considera un subconjunto estricto y no vacio P del conjunto de todas las palabras que son codificaciones de una maquina de turing (por ejemplo, P puede ser las codificaciones de todas las maquinas que aceptan epsilon). Luego, el lenguaje de todas las palabras P es indecidible.