Máquina De Turin

Descrição informal

Uma máquina de Turing consiste em:

Uma fita que é dividida em células, uma adjacente à outra. Cada célula contém um símbolo de algum alfabeto finito. O alfabeto contém um símbolo especial branco (aqui escrito como ¬) e um ou mais símbolos adicionais. Assume-se que a fita é arbitrariamente extensível para a esquerda e para a direita, isto é, a máquina de Turing possui tanta fita quanto é necessário para a computação. Assume-se também que células que ainda não foram escritas estão preenchidas com o símbolo branco.

Um cabeçote, que pode ler e escrever símbolos na fita e mover-se para a esquerda e para a direita.

Um registrador de estados, que armazena o estado da máquina de Turing. O número de estados diferentes é sempre finito e há um estado especial denominado estado inicial com o qual o registrador de estado é inicializado.

Uma tabela de ação (ou função de transição) que diz à máquina que símbolo escrever, como mover o cabeçote (\leftarrow para esquerda e \rightarrow para direita) e qual será seu novo estado, dados o símbolo que ele acabou de ler na fita e o estado em que se encontra. Se não houver entrada alguma na tabela para a combinação atual de símbolo e estado então a máquina pára.

Note que cada parte da máquina é finita; é sua quantidade de fita potencialmente ilimitada que dá uma quantidade ilimitada de espaço de armazenamento.

Definição formal

Máquina de Turing com uma fita

Mais formalmente, uma máquina de Turing (com uma fita) é usualmente definida como uma Tupla M=(Q,\Sigma, \Gamma, s, b, F, \delta), onde

Q é um conjunto finito de estados

\Sigma é um alfabeto finito de símbolos

\Gamma é o alfabeto da fita (conjunto finito de símbolos)

s \in Q é o estado inicial

b \in \Gamma é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação)

F \subseteq Q é o conjunto dos estados finais

\delta: Q \times \Gamma ⇒ Q \times \Gamma \times \{\leftarrow,\rightarrow\} é uma função parcial chamada função de transição, onde \leftarrow é o movimento para a esquerda e \rightarrow é o movimento para a direita.

Definições na literatura às vezes diferem um pouco, para tornar argumentos ou provas mais fáceis ou mais claras, mas isto é sempre feito de maneira que a máquina resultante tem o mesmo poder computacional. Por exemplo, mudar o conjunto \{\leftarrow,\rightarrow\} para \{\leftarrow,\rightarrow,P\}, onde P permite ao cabeçote permanecer na mesma célula da fita em vez de mover-se para a esquerda ou direita, não aumenta o poder computacional da máquina (Fonte - Michael Sipser - Int Teoria da Computação).

Máquina de Turing com k fitas

Uma máquina de Turing com k fitas também pode ser descrita como uma 7-upla M=(Q,\Sigma, \Gamma^1, \Gamma^2, ..., \Gamma^k, s, b, F, \delta), onde

Q é um conjunto finito de estados

\Sigma é um alfabeto finito de símbolos

\Gamma^i, i = 1,...,k é o alfabeto da fita i (conjunto finito de símbolos)

k é o número de fitas

s \in Q é o estado inicial

b \in \Gamma é o símbolo branco

F \subseteq Q é o conjunto dos estados finais

\delta: Q \times \Gamma ⇒ Q \times \Gamma \times \{\leftarrow,\rightarrow\} é uma função parcial chamada função de transição, onde \leftarrow é o movimento para a esquerda e \rightarrow é o movimento para a direita.

Note que uma máquina de turing com "k" fitas não é mais poderosa que uma máquina de Turing tradicional.

Detalhes adicionais requeridos para visualizar ou implementar máquinas de Turing

Nas palavras de Van Emde Boas (1990), p. 6: "O objeto do conjunto teórico [sua descrição formal sete-tupla similar ao acima] fornece apenas informação parcial sobre como a máquina agirá e com o que suas computações se parecerão."

Por exemplo,

Serão necessárias muitas decisões sobre com o que os símbolos realmente se parecem, e uma forma de contra-prova de símbolos de escrita e leitura indefinidamente.

As operações shift left e shift right podem deslocar a cabeça da fita sobre a fita, mas quando realmente construir uma máquina de Turing, isso é mais prático para fazer a fita deslizar para frente e para trás sob a cabeça em vez disso.

A fita pode ser finita, e automaticamente estendida com espaços em branco, conforme necessário (o qual é o mais próximo da definição matemática), mas isso é mais comum para pensar sobre isso como infinitamente alongado em ambos os lados e sendo preenchida com espaços em branco, exceto sobre o fragmento finito dado explicitamente onde a cabeça da fita está. (Isto não é, claro, implementável na prática.) A fita não pode ser fixada em comprimento, desde que não corresponderia à definição dada e limitaria seriamente o alcance das computações que a máquina pode realizar àquelas do autômato linearmente limitado.

Definições alternativas

Para tornar as provas e argumentos mais fáceis ou mais claras, encontramos na literatura definições levemente diferentes, mas isso sempre é feito de tal maneira que a máquina resultante tenha o mesmo poder computacional. Por exemplo, modificando o conjunto \{L,R\} para \{L,R,N\}, onde N ("Nada" ou "Sem operação") permitiria a máquina ficar sobre a mesma célula da fita em vez de mover para a esquerda ou para direita, não aumenta o poder computacional das máquinas.

A convenção mais comum representa cada "instrução de Turing" na "tabela de Turing" por uma de nove 5-uplas, pela convenção de Turing/Davis (Turing (1936) em Undecidable, p. 126-127 e Davis (2000) p. 152):

(definição 1): (qi,