90 anos da máquina de Turing: o artigo de 1936 que fundou a ciência da computação

Antes de existir qualquer computador eletrônico, um matemático inglês de 23 anos descreveu, apenas com papel e lógica, uma máquina capaz de executar qualquer procedimento de cálculo que possa ser escrito como uma sequência de regras. O artigo de Alan Turing, intitulado On Computable Numbers, with an Application to the Entscheidungsproblem, foi enviado à Sociedade Matemática de Londres em maio de 1936 e completa 90 anos em 2026. A máquina de Turing que ele descreve nunca foi pensada para ser fabricada. Era um instrumento de raciocínio, e ainda assim se tornou a definição de referência do que um computador pode e do que não pode fazer.

Uma pergunta deixada por Hilbert

No fim da década de 1920, o matemático alemão David Hilbert propôs um desafio que ficou conhecido pelo nome em alemão, Entscheidungsproblem, o "problema da decisão". A pergunta era se existiria um método mecânico e definido capaz de decidir, para qualquer afirmação matemática formulada em linguagem lógica, se ela pode ou não ser demonstrada.

Responder exigia algo que ninguém tinha formalizado: uma definição precisa de "método mecânico". Turing, então fellow do King's College, na Universidade de Cambridge, conheceu o problema em 1935, nas aulas do matemático Max Newman sobre fundamentos da matemática. A solução que encontrou foi imaginar, com o máximo de rigor, o que faz uma pessoa quando calcula seguindo regras, e transformar isso em uma máquina abstrata.

A máquina de Turing em linguagem acessível

O ponto de partida de Turing foi o "computador" humano, palavra que na época designava a pessoa encarregada de fazer contas. Essa pessoa trabalha com papel, lê um símbolo de cada vez, anota resultados, consulta instruções e segue adiante. A máquina abstrata reproduz esses gestos com quatro componentes:

• Uma fita dividida em casas, que pode se estender indefinidamente, e onde cada casa guarda um símbolo ou fica em branco.
• Uma cabeça de leitura e escrita, que observa uma casa de cada vez, pode apagar ou escrever um símbolo e se mover uma casa para a esquerda ou para a direita.
• Um conjunto finito de estados, que funciona como a memória de curto prazo da máquina, indicando em que etapa do procedimento ela está.
• Uma tabela de regras, que diz, para cada combinação de estado atual e símbolo lido, o que escrever, para onde se mover e qual o próximo estado.

Um exemplo simples dá a medida da ideia. Para somar 1 a um número escrito em binário, a máquina começa no último dígito à direita. Se lê 1, escreve 0 e anda uma casa para a esquerda, repetindo o passo. Se lê 0 ou uma casa em branco, escreve 1 e para. Três regras bastam para uma operação que qualquer pessoa faz sem pensar.

O poder do modelo está em que procedimentos muito mais complexos, de multiplicar números a ordenar listas, podem ser decompostos em regras desse tipo. Turing chamou suas criações de "máquinas de computação" ou "máquinas automáticas". O nome "máquina de Turing" foi cunhado por Alonzo Church, lógico da Universidade de Princeton, em uma resenha do artigo publicada em 1937.

A máquina universal

A parte mais influente do artigo talvez seja a sexta seção. Nela, Turing mostra que é possível construir uma única máquina capaz de imitar qualquer outra. Basta escrever na fita a descrição da tabela de regras da máquina a ser imitada, codificada como uma sequência de símbolos, seguida dos dados de entrada. A máquina universal lê essa descrição e executa o que ela determina.

É, em essência, a ideia de programa armazenado. Em vez de construir um equipamento diferente para cada tarefa, constrói-se um equipamento geral e muda-se o que está gravado nele. Todo computador atual, do servidor em nuvem ao telefone celular, segue esse princípio: o mesmo hardware executa planilhas, navegadores, jogos e modelos de linguagem porque recebe instruções diferentes.

O que nenhuma máquina pode resolver

Com a definição em mãos, Turing respondeu à pergunta de Hilbert, e a resposta foi negativa. Ele mostrou que não existe uma máquina capaz de examinar a descrição de qualquer outra máquina e decidir, em todos os casos, se ela se comporta de determinada maneira. Uma versão dessa impossibilidade ficou conhecida mais tarde como problema da parada: não há um programa geral que determine, para todo programa e toda entrada, se a execução um dia termina. Daí decorre que o Entscheidungsproblem não tem solução.

Turing não estava sozinho. Pouco antes de concluir o trabalho, ele soube que Alonzo Church havia chegado à mesma conclusão por outro caminho, usando um formalismo chamado cálculo lambda. Turing acrescentou ao artigo um apêndice demonstrando que as duas definições de "calculável" eram equivalentes. A convergência deu origem ao que ficou conhecido como tese de Church-Turing: tudo o que pode ser calculado por um procedimento efetivo pode ser calculado por uma máquina de Turing.

Os dois abordaram a questão de modos complementares. A formulação de Turing, baseada em uma máquina que qualquer pessoa consegue visualizar, tornou-se a mais usada no ensino e na teoria da computação.

Do papel aos computadores de verdade

O artigo foi lido na Sociedade Matemática de Londres em novembro de 1936 e publicado nos anais da entidade na virada para 1937. Em setembro de 1936, antes mesmo da publicação, Turing havia se mudado para Princeton, onde fez o doutorado sob orientação de Church. Durante a Segunda Guerra Mundial, trabalhou em Bletchley Park, no Reino Unido, no esforço de decifrar as mensagens cifradas pela máquina alemã Enigma.

Depois da guerra, a ideia abstrata ganhou forma física. No Laboratório Nacional de Física britânico, Turing projetou o ACE (Automatic Computing Engine), um dos primeiros projetos detalhados de computador de programa armazenado. Em 1950, publicou na revista Mind o artigo Computing Machinery and Intelligence, que abre com a pergunta "as máquinas podem pensar?" e propõe o que ficou conhecido como teste de Turing. Ele morreu em 7 de junho de 1954, aos 41 anos. Desde 1966, a principal premiação da computação, concedida pela ACM, leva o seu nome.

Por que a ideia ainda sustenta a IA

Noventa anos depois, a máquina de Turing continua presente, ainda que invisível, em qualquer discussão sobre inteligência artificial.

• Todo sistema de IA é uma computação. Um modelo de linguagem, por mais sofisticado que pareça, roda em computadores digitais. Cada resposta é o resultado de uma sequência enorme de operações aritméticas definidas por regras, algo que uma máquina de Turing poderia, em princípio, executar, ainda que de forma incomparavelmente mais lenta.
• A universalidade explica a versatilidade. O mesmo tipo de processador que roda um sistema de gestão empresarial executa uma rede neural. O que muda é o programa e, no caso dos modelos de IA, os parâmetros aprendidos a partir de dados.
• Os limites continuam valendo. O resultado de 1936 não foi superado pela IA. Nenhum sistema, por mais avançado, decide em geral se um programa arbitrário vai terminar ou se comportar como esperado. Isso ajuda a explicar por que testes, revisões e monitoramento de software não podem ser totalmente automatizados com garantia absoluta.
• Computável não é o mesmo que viável. A teoria diz o que pode ser calculado com tempo e memória ilimitados. Na prática, custo de processamento, energia e tempo de resposta decidem o que vale a pena fazer, uma preocupação central de quem opera IA em empresas.

Há ainda uma herança menos técnica. A pergunta que Turing formulou em 1950, sobre se máquinas podem pensar, segue sem resposta consensual. O que se sabe, desde 1936, é o que qualquer máquina que siga regras pode fazer em princípio e onde estão os limites que nenhuma delas atravessa. Poucas ideias do século 20 se mantiveram tão estáveis enquanto a tecnologia construída sobre elas mudava tanto.