Definições formais da Máquina de Turing Determinística

Comumente, Máquinas de Turing Determinísticas são formalizadas com uma sétupla. Uma das principais formalizações é: M = (Q, Σ, Γ, δ, q₀, q_aceitação, q_rejeição), onde: Q é o conjunto de estados; Σ é o alfabeto de entrada da fita sobre a qual a máquina opera; Γ é o alfabeto da fita sobre a qual a máquina opera; δ é a função de transição, obedecendo a δ: Q×Γ → Q×Γ×{e, d}; q₀ é o estado inicial; q_aceitação é o estado de aceitação; q_rejeição é o estado de rejeição; Os estados de aceitação e rejeição são nulos quando se usa a Máquina de Turing para processamentos de funções e procedimentos. Afinal de contas, a máquina está sendo usada como um processador e não como um reconhecedor.

Gráficamente, isso pode ser representado por:

Esta imagem mostra a notação gráfica do JFLAP para o formalismo acima. A seta de q0 para q1, rotulada com "a ; b , R" significa que, estando em q0:

• Lê-se 'a';

• Escreve-se 'b';

• Movimenta-se para a direita (R, pois, em inglês, right).

Outra possível formalização proposta por (H,M,U,2001) é: M = (Q, Σ, Γ, δ, q₀, β, F), onde: Q é o conjunto de estados; Σ é o alfabeto de entrada da fita sobre a qual a máquina opera; Γ é o alfabeto da fita sobre a qual a máquina opera; δ é a função de transição, obedecendo a δ: Q×Γ → Q×Γ×{e, d}; q₀ é o estado inicial; β é o símbolo que marca o "espaço em branco" na fita; F é o conjunto de estados de aceitação; Quando a Máquina de Turing é usada para processamento de funções e procedimentos, F será um conjunto vazio, pela mesma razão deste propósito na sétupla anterior.

Outro conceito que deve ser formalizado é o de configuração: Configuração é uma tripla que descreve o que está acontecendo com a máquina em um determinado instante, como se fosse uma fotografia da máquina. Essa tripla é formalizada como: C = (q, α, i), onde: q é o estado atual; α é o conteúdo atual da fita; i é a distância da posição atual da cabeça de leitura em relação ao símbolo inicial, ou seja, é a posição (baseada em 0) atual da cabeça de leitura.