Máquina de Turing

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