Máquinas de Turing

Uma máquina de Turing é uma 7-upla: controle finito mais uma fita ilimitada que a cabeça lê, escreve e percorre. A transição δ, dado o estado e o símbolo sob a cabeça, devolve o próximo estado, o símbolo escrito e o movimento L ou R.

Configurações, variantes e as classes recursiva e RE deste tópico — e gramática irrestrita, μ-recursivas e P versus NP nos seguintes — partem dessa 7-upla e de αqβ.

As páginas se agrupam em quatro blocos. O primeiro monta a máquina de uma fita e lê o destino: aceita, rejeita ou não para.

O segundo compara arranjos com extra — várias fitas, não determinismo, duas pilhas — e prova equivalência de classe.

O terceiro identifica procedimento efetivo com essa máquina e recorta decisor, reconhecedor e o que nenhuma máquina reconhece.

O quarto produz problemas sem decisor: um por diagonal, os demais por redução.

A 7-upla, αqβ e o programa aceitador ou transdutor estão em Modelo de Máquina de Turing. k fitas em trilhas, NTM em largura e duas pilhas como os dois lados da fita estão em Modificação de Máquinas de Turing.

Aceitar, rejeitar e não parar como destinos de uma máquina estão em Modelo de Máquina de Turing. Recursiva, RE e co-RE como classes estão em Tese de Church-Turing.

HALT RE e não recursiva, e HALT̄ fora de RE, estão em Tese de Church-Turing. A máquina D que inverte o veredito de H em ⟨D⟩ está em Indecidibilidade.

HALT ≤ NE e HALT ≤ PCP estão em Indecidibilidade. Testar P(L(M)) quando P só olha a linguagem e não é constante nas RE está em Teorema de Rice.