máquina de Turing

É um tipo de computador digital hipotético, idealizado em 1936 por Alan Turing para comprovar teorias computacionais de forma matemática.
A máquina de Turing seria equipada com uma fita perfurada de comprimento infinito, preenchida em intervalos regulares com símbolos de um conjunto finito e um ponteiro que marcaria a posição real em que a máquina se encontrava, dentro de um conjunto limitado de "estados internos" possíveis.
Entretanto, em cada operação a máquina leria o símbolo inscrito na posição correspondente na fita, e para cada combinação de posição e símbolo lido um programa especificaria um novo símbolo para inscrever na mesma fita ou um movimento a ser efetuado pelo ponteiro, que poderia deslocar-se para a esquerda, para a direita, ou parar.
Com esta máquina abstrata, Turing pretendia conseguir definições matematicamente precisas para algoritmos, ou procedimentos mecânicos.
Ainda muito utilizada na abordagem a teorias como a da computação ou da complexidade, a máquina de Turing compreenderia então, e mais precisamente, quatro elementos:
- Uma fita dividida em células contíguas, cada qual contendo um símbolo de um alfabeto finito, que por sua vez contém, entre outros, um símbolo nulo especial. Esta fita seria infinitamente extensível para a esquerda e para a direita, e assumir-se-ia que as células que não tivessem sido preenchidas com um símbolo contivessem o carácter especial nulo.
- Um dispositivo de leitura e gravação que se movimentasse para a esquerda e para a direita nessa fita, e conseguisse interpretar e escrever os símbolos.
- Um outro dispositivo que registasse cada estado da máquina de Turing, sendo que o número de estados diferentes seria sempre finito e compreenderia um estado inicial de arranque, que iniciaria o dispositivo de registo.
- Uma tabela de ações que comandaria os movimentos da máquina, dizendo-lhe que símbolo escrever, para onde mover o dispositivo de leitura e gravação, e decidiria qual o seu novo estado, em função do símbolo acabado de ler e do estado em que a máquina se encontrasse no momento. Se porventura não existisse qualquer entrada na tabela de ações para uma dada combinação de símbolo e estado, então a máquina consideraria o programa concluído e pararia.