Turing reconhecível => enumerável

Eu tenho a prova de ir de um enumerador para uma Máquina de Turing (continue executando o enumerador e veja se ele corresponde à entrada), mas não vejo como a outra maneira funciona.

De acordo com minhas anotações e o livro (Introdução à Teoria da Computação - Sipser), para obter o enumerador de Turing de uma máquina de Turing, basicamente escrevemos todas as combinações do alfabeto. Em seguida, você executa a TM nesta entrada; se ela aceita imprimi-la, substitua por nova sequência de repetição ad infinitum.

O problema que estou tendo é certamente que isso requer que o idioma seja decidido. Caso contrário, ele poderá ficar preso na terceira palavra em algum loop infinito, condenado a nunca aceitar ou rejeitar e certamente nunca imprimirá o idioma inteiro.

o que estou perdendo?

O que está faltando é a maneira como você executa a Turing Machine em seqüências de caracteres para obter o Enumerador. Em vez de gerar cada string, execute M e, em seguida , produza essa string se o M aceitar - o que, como você identificou, não funcionará -, faça algo como o seguinte, que adota a estratégia de simular muitas instâncias do M em diferentes strings "em paralelo".$M$$M$$M$$M$

Suponha que a fita tem conteúdo , onde w i é alguma palavra em consideração e S i é o estado atual de M operacional em w i . Isso representa que n cópias de M estão sendo simuladas. w i é armazenado para que saibamos qual era a entrada original.$\langle w_1, S_1\rangle \# \cdots \# \langle w_n, S_n\rangle$$w_i$$S_i$$M$$w_i$$n$$M$$w_i$

Agora execute o seguinte loop

1. No final da gravação de fita a próxima seqüência de , juntamente com a configuração inicial S de M , ou seja, write # ⟨ w , S ⟩ .$w\in\Sigma^*$$S$$M$$\# \langle w, S\rangle$
2. Simule cada cópia do na fita por uma etapa. (Presumivelmente, use outra fita.)$M$
3. Se algum dos entrar em um estado de aceitação, coloque a sequência correspondente na fita de saída. Remova esta instância de M da fita.$M$$M$
4. Se algum dos entrar em um estado de rejeição, remova a instância de M da fita.$M$$M$
5. Vá para a etapa 1.

Não é difícil argumentar que todas as cadeias aceites pela M acabará por ser saída na fita.$w\in\Sigma^*$$M$