Turing reconhecível => enumerável

10

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?

T. Kiley
fonte

Respostas:

9

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".MMMM

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.w1,S1##wn,SnwiSiMwinMwi

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ΣSM#w,S
  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.MM
  4. Se algum dos entrar em um estado de rejeição, remova a instância de M da fita.MM
  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ΣM

Dave Clarke
fonte
4
também conhecido como "cauda de pomba".
precisa