MÁQUINA DE TURING
A noção de “máquina de Turing”, enquanto “máquina matemática, surgiu como uma tentativa de fornecer um equivalente formal adequado para o processo humano de computação ”mecânica“. A máquina matemática deveria funcionar como um débil mental a quem houvessem sido dadas instruções para a execução de uma certa tarefa, e que nesta execução cumprisse mecânica e rigorosamente as instruções dadas. Baseado nesta ideia, o matemático inglês Alan Turing propôs em 1936 a seguinte formulação como sendo um substitutivo formal adequado para a noção de “computabilidade”. Seja uma máquina. Esta máquina vai realizar os seus cálculos numa fita (potencialmente) infinita, e dividida transversalmente em quadrados sucessivos. Como serão feitos os cálculos? O cálculo de uma função (por exemplo, o valor de A dividido por B) deve poder ser analisado numa sucessão finita de etapas elementares (“separe tantas casas decimais do dividendo quantas houverem no divisor”; “veja qual o maior múltiplo do divisor nestas casas”, e assim por diante). Uma etapa consiste no exame de um certo Estado dos cálculos — um exame do símbolo escrito na fita —; uma decisão a respeito do que deve ser feito em seguida; e a execução do que foi decidido. Uma máquina de Turing poderá ser representada por um conjunto de instruções da seguinte forma: ci aj bk cl
Suponhamos que a máquina esteja no estado ci. Ela “observa”, na fita, o símbolo aj escrito. Sua tabela de instruções diz, no caso, que ela deve “tomar a atitude” bk (esta atitude pode ser: caminhar para a direita, caminhar para a esquerda, parar, apagar aj e escrever uma letra an). Ela toma essa atitude e passa para o estado cl. Em sua tabela de instruções haverá uma linha começando por cl, e a máquina começa outra etapa de sua computação.
Máquinas de Turing podem ser vistas como computadores eletrônicos possuindo uma memória (potencialmente) infinita, e tendo à sua disposição um tempo (potencialmente) infinito para efetuar os cálculos. Estes cálculos, no entanto, devem ser efetivados num número finito de etapas. O programa de um computador é equivalente à “tabela de instruções” da máquina de Turing.
Pode-se mostrar como todos os sistemas e modelos propostos para a representação de um processo mecânico de computação, até hoje, são equivalentes ao modelo da máquina Turing. (Francisco Doria - DCC).