Recibo la prueba de pasar de un enumerador a una máquina de Turing (sigo ejecutando el enumerador y ver si coincide con la entrada) pero no veo cómo funciona la otra manera.
Según mis notas y el libro (Introducción a la teoría de la computación - Sipser), para obtener el enumerador de Turing de una máquina de Turing, básicamente escribimos todas las combinaciones del alfabeto. Luego ejecuta la TM en esta entrada, si acepta imprimirla, reemplácela con una nueva secuencia de repetición hasta el infinito.
El problema que tengo es que seguramente esto requiere que el lenguaje sea decidible. De lo contrario, podría atascarse en la tercera palabra en un bucle infinito condenado a nunca aceptar o rechazar y, ciertamente, nunca imprimir todo el lenguaje.
¿Qué me estoy perdiendo?
fuente