Durante a Segunda Guerra Mundial, o matemático britânico Alan Turing fez parte de uma equipe dedicada a decifrar o principal código militar alemão, o chamado código Enigma. Para decifrá-lo, Turing usou, em parte, um conceito que criara pouco antes da guerra, em 1936. Chamava-se “máquina de Turing”, mas não era nada mecânico nem elétrico. Em vez disso, era uma “experiência de pensamento”, um modelo idealizado. Turing imaginou uma máquina que consistia em um tira infinita de papel na qual um tipo de “cabeça de gravação” podia ler e escrever informações. A cabeça tinha um mecanismo de controle passível de modificações que podia armazenar ordens de um conjunto finito de instruções – ou seja, um “programa”. Segundo a concepção de Turing, a tira era dividida em quadrados, cada um dos quais estava vazio ou trazia um dos símbolos de um conjunto finito. A cabeça de gravação podia mover-se até um dos quadrados e lê-lo, escrever nele ou apagá-lo, e no mesmo instante mudar de um “estado interno” a outro, dependendo do estado interno da máquina e das condições do quadrado sob exame num momento dado. Quando a máquina interrompia o processo de examinar, escrever e apagar, o resultado seria a solução à pergunta matemática que tinha lhe sido apresentada.
A tecnologia para concretizar uma versão prática da máquina de Turing não existia em 1936, mas Turing deixou instruções para isso quando se tornasse disponível. o que ele fez foi tão somente delinear a base teórica da informática.
Representação artística de uma máquina de Turing
Não é difícil simular uma máquina de Turing num computador moderno (exceptuando pela quantidade de memória limitada existente nos computadores actuais).
É também possível construir uma máquina de Turing com base puramente mecânica. O matemático Karl Scherer construiu essa máquina em 1986 usando conjuntos de contrução de metal, plástico e alguma madeira. A máquina, com 1,5 m de altura, usa puxões de fios para ler, movimentar e escrever informação, a qual é, por sua vez, representada por rolamentos.
A máquina encontra-se atualmente em exibição na entrada do Departamento de Ciência de Computadores da Universidade de Heidelberg, na Alemanha.
É também possível, usando algumas centenas de espelhos, construir uma máquina de Turing óptica na sua própria casa usando o mapa da ferradura de Smale. Este é baseado num trabalho do matemático estado-unidense Stephen Smale.
Fontes: Livro Ciência a Jato, de Alan Axelrod, e Wikipédia