Máquinas de Turing explicadas

Em 1936, antes de existirem computadores eletrónicos, o matemático Alan Turing, então com 24 anos, perguntou o que significa um cálculo ser mecânico. A sua resposta foi uma máquina imaginária tão simples que dificilmente poderia fazer menos: lê e escreve símbolos numa fita, uma célula de cada vez, segundo uma tabela fixa de regras. Essa máquina acabou por definir a própria computação, e mostrou que há perguntas a que nenhum computador alguma vez conseguirá responder.

Uma fita de células com uns e células vazias e uma cabeça de leitura e escrita sobre uma célula, identificada com o seu estado
Uma fita de células com uns e células vazias e uma cabeça de leitura e escrita sobre uma célula, identificada com o seu estado

A pergunta de Turing

Em 1928, David Hilbert perguntou se existe um procedimento mecânico que decida, para cada afirmação da matemática, se pode ser demonstrada: o Entscheidungsproblem. Para lhe responder, alguém tinha de dizer exatamente o que é um procedimento mecânico. No seu artigo de 1936, On Computable Numbers, Turing imaginou um escriturário a trabalhar com lápis e papel e reduziu o trabalho aos passos mais pequenos: olhar para um símbolo, alterá-lo, passar para um símbolo vizinho e lembrar-se um pouco do que estava a fazer. O resultado foi a máquina de Turing.

Uma máquina Bombe (à esquerda) e um retrato de Alan Turing (à direita)
Uma máquina Bombe (à esquerda) e um retrato de Alan Turing (à direita)

A máquina

Uma máquina de Turing tem uma fita dividida em células, infinita nos dois sentidos, cada uma com um símbolo, geralmente o vazio. Uma cabeça está sobre uma célula e a máquina encontra-se num de um número finito de estados. Uma tabela de regras indica, para cada estado e cada símbolo que a cabeça pode ler, o símbolo a escrever, a direção do movimento e o estado seguinte. A máquina aplica uma regra por passo. Quando entra num estado de paragem, para, e o que fica na fita é a sua resposta.

Programas como tabelas de regras

Cada tabela de regras é um programa. Para somar 1 a um número binário, a máquina vai até à extremidade direita do número e depois desloca-se para a esquerda, transformando os 1 em 0, até encontrar um 0 ou uma célula vazia, que transforma em 1. Para verificar se uma palavra é um palíndromo, apaga o primeiro símbolo, memoriza-o no seu estado, corre até à outra extremidade e verifica se o último símbolo corresponde, e depois repete. Os programas longos, como um que multiplica ou ordena, são construídos com os mesmos poucos tipos de regras.

A máquina universal

A ideia mais importante de Turing foi que a própria tabela de regras pode ser escrita na fita. Uma máquina de Turing universal lê a descrição de qualquer outra máquina e a respetiva entrada, e depois imita-a passo a passo. Uma única máquina fixa pode, portanto, executar todos os programas: é o princípio de todos os computadores de programa armazenado, em que o software é apenas dados na memória. Qualquer sistema capaz de imitar uma máquina de Turing universal diz-se Turing-completo, incluindo todas as linguagens de programação, o Jogo da Vida de Conway e o autómato celular Rule 110.

A tese de Church-Turing

No mesmo ano, Alonzo Church descreveu a computação com o seu cálculo lambda, e as duas definições revelaram-se capazes de calcular exatamente as mesmas funções. O mesmo aconteceu com todos os modelos posteriores, das máquinas de registos aos processadores modernos. A tese de Church-Turing afirma que tudo o que pode ser calculado por um procedimento passo a passo pode ser calculado por uma máquina de Turing. Não pode ser demonstrada, porque «procedimento passo a passo» é uma ideia informal, mas nunca foi encontrado um contraexemplo.

O problema da paragem

Turing mostrou depois que algumas perguntas não têm resposta mecânica. Suponha-se que uma máquina conseguia decidir, para todos os programas e entradas, se esse programa acaba por parar. Construa-se um novo programa que pergunta a esse decisor sobre si próprio e depois faz o contrário: se lhe disserem que para, fica em ciclo para sempre, e se lhe disserem que fica em ciclo, para. Qualquer das respostas está errada, por isso o decisor não pode existir. O problema da paragem é indecidível, e com ele o Entscheidungsproblem: nenhum algoritmo consegue resolver todas as questões matemáticas.

Castores atarefados

Em 1962, Tibor Radó transformou o problema da paragem num jogo: entre todas as máquinas com n estados e os símbolos 0 e 1 que param quando iniciadas numa fita vazia, qual escreve o maior número de uns e quantos passos pode dar uma máquina destas? Estes números, os valores do castor atarefado, crescem mais depressa do que qualquer função computável, porque uma forma de os calcular resolveria o problema da paragem. Os valores conhecidos são 6, 21 e 107 passos para dois, três e quatro estados; para cinco estados, a máquina campeã de Heiner Marxen e Jürgen Buntrock dá 47 176 870 passos, um valor provado em 2024 pela colaboração online bbchallenge com uma demonstração verificada por computador. Para seis estados, conhecem-se máquinas que funcionam durante mais passos do que é possível escrever em notação comum.

Explore

Abra o simulador de máquina de Turing para executar oito programas já prontos ou escrever os seus. Siga a cabeça passo a passo e veja que regra é aplicada, observe o contador que nunca para, verifique palíndromos e execute os castores atarefados: os 107 passos da campeã de quatro estados cabem no diagrama, e os 47 milhões de passos da campeã de cinco estados demoram poucos segundos na velocidade Muito rápida.

Perguntas frequentes

A máquina de Turing chegou a ser construída?

Não tal como Turing a descreveu, já que a sua fita é infinita, mas a ideia foi em breve seguida por verdadeiros computadores de programa armazenado, que o próprio Turing ajudou a conceber depois da Segunda Guerra Mundial. Desde então, entusiastas construíram modelos funcionais em madeira, em LEGO e até no Jogo da Vida, todos com uma fita finita, o que basta para qualquer cálculo que termine.

Qual é a diferença entre as contagens de 14 e 21 passos para três estados?

Há duas perguntas do castor atarefado: o maior número de uns escritos e o maior número de passos dados. Para três estados, a máquina do simulador escreve o máximo de seis uns em 14 passos, enquanto outra máquina de três estados dá o máximo de 21 passos mas deixa apenas cinco uns. Para dois, quatro e cinco estados, uma mesma máquina vence em ambas.

Turing-completo significa poderoso?

Significa capaz de calcular tudo o que é computável, com tempo e memória suficientes, o que nada diz sobre a velocidade. Uma máquina de Turing precisa de muitos passos para aritmética simples, e alguns sistemas são Turing-completos quase por acaso, como jogos de cartas, fórmulas de folhas de cálculo e a redstone do Minecraft.

Porque é que um computador não pode simplesmente executar um programa para ver se para?

Executá-lo mostra que um programa para, se parar, mas se ainda não parou não é possível saber se nunca vai parar ou se apenas precisa de mais tempo. A demonstração de Turing mostra que nenhum método mais engenhoso funciona para todos os programas, embora para muitos programas concretos a pergunta possa ser respondida.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir o simulador de máquina de Turing