Máquina de Turing

A Máquina de Turing é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.

Uma máquina de Turing consiste em:
1. 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.
2. Um cabeçote, que pode ler e escrever símbolos na fita e mover-se para a esquerda e para a direita.
3. 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.
4. Uma tabela de ação (ou função de transição) que diz à máquina que símbolo escrever, como mover o cabeçote ( para esquerda e 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 para.

Turing consiguiu êxito na construção de sua máquina e provou que para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imitá-lo. Era este sistema formal genérico, com a habilidade de imitar qualquer outro sistema formal, o que Turing procurava essencialmente. Tais sistemas chamam-se Máquinas de Turing Universais.
Em abril de 1936, Turing mostrou seus resultados para John Von Neumann em Princeton, quando os computadores no sentido moderno, ainda não existiam. Turing criou os conceitos e a