Como enumerar todas as máquinas de Turing?

Question

Por que isso é verdade: "Lásão contraguardas máquinas de Turing "

Na primeira resposta para esta pergunta Uma descrição de como enumerar todas as máquinas de Turing é dada.

Tudo é claro, exceto por uma parte: Como você sabe se uma string é uma codificação válida de uma máquina de Turing?Na etapa 3, o algoritmo precisa verificar se uma string é uma codificação válida de uma máquina de Turing.Como isso é feito?

Answer 1

Uma máquina de Turing tem uma representação como uma string.Mais especificamente, você escreve a função transição .Para fazer isso, simplesmente pense nisso como uma grande mesa, tendo em cada linha dois estados uma carta, e uma transição principal (l para a esquerda ou r para a direita).

Agora, codifique cada entrada da tabela de função de transição e espaço entre eles com 3 zeros (é como um "número mágico", então saberíamos onde as entradas começam e terminam).Cada entrada conterá dois números - cada número representando um estado, outro bit para a letra e outro bit para a transição da cabeça (digamos que 1 seria R e 0 é l).

Entre os dois números e os outros bits colocar mais 2 zeros, apenas você seria capaz de distinguir entre eles.

Agora, para enumerar em todas as máquinas de Turing, basta enumerar em todas as strings e verificar se eles estão no formato descrito acima