Duda con respecto a la indecibilidad

[based-on-what]

Hola a todos, estaba revisando los contenidos de la semana 3, concretamente este apartado me dejó algunas dudas: , ¿por qué la reducción es del tipo f(w) = w000w, si en el enunciado dice C(M1)0000C(M2)? ¿Acaso la codificación de las máquinas M1 y M2 son iguales? ¿O solamente es para simplificar?

Saludos y muchas gracias.

[juanreutter]

No entiendo mucho la pregunta, pero acá un intento: El lenguaje D se define como todas las palabras w que son de la forma C(M), para una máquina M, y tal que la máquina acepta a su propia codificación C(M). La función f está definida para todos los strings, y es así: f(w) = w0000w. Si w resulta ser la codificación C(M) de una máquina, entonces f(w) = C(M)0000C(M) y todo es como tu esperabas. Pero si w no es la codificación de una máquina (y por tanto, w no pertenece al lenguaje D), entonces f(w) va a ser w0000w donde w NO es C(M), y por tanto no va a pertenecer a DyD, asi que ese caso también está cubierto por la reducción.

[based-on-what]

No entiendo mucho la pregunta, pero acá un intento: El lenguaje D se define como todas las palabras w que son de la forma C(M), para una máquina M, y tal que la máquina acepta a su propia codificación C(M). La función f está definida para todos los strings, y es así: f(w) = w0000w. Si w resulta ser la codificación C(M) de una máquina, entonces f(w) = C(M)0000C(M) y todo es como tu esperabas. Pero si w no es la codificación de una máquina (y por tanto, w no pertenece al lenguaje D), entonces f(w) va a ser w0000w donde w NO es C(M), y por tanto no va a pertenecer a DyD, asi que ese caso también está cubierto por la reducción.

Hola profesor, sí, me quedó claro, muchas gracias.