juanreutter
commented
3 years ago La verdad nunca pensé en una reducción. Claramente ambos lenguajes son decidibles asi que existe una reducción de cualquier lado pa cualquier otro, pero no te garantiza que se mantengan los cambios.
Pero estoy de acuerdo que sigue un poco el espíritu: "aprovechar" la máquina para a) y así resolver la b). Lo nuevo acá es que tienes que hacer un poco de magia no-deterministica para que eso pase de una forma que no te exploten los cambios (o al menos así lo vi, quizás hay una manera más simple de resolverlo que yo no he pensado, si es así, obvio que puedes escribir esa forma).
Hola, la idea de la parte b) dice lo siguiente:
Frente a esto me está surgiendo la duda de si lo que se propone es una reducción del lenguaje de la máquina B al lenguaje de la máquina A. Vale la pena mencionar esto en mi respuesta? O al mencionar una reducción tendría que demostrar que es computable y que w pertenece a L_b ssi f(w) pertenece a L_a?