Em 1936, o matemático inglês Alan Turing propôs uma máquina que existia só no papel: uma fita com símbolos e uma tabela de regras. Turing argumentou que esse modelo formal capta qualquer procedimento descrito passo a passo, ideia que ficou conhecida como tese de Church-Turing: uma tese amplamente aceita, não um teorema. Com o modelo, ele provou algo mais surpreendente: há problemas que nenhuma máquina desse tipo resolve de forma geral, por mais rápida que seja. Não são perguntas apenas difíceis; são problemas sem procedimento geral de solução.
Esse é o tema de um corte de 41 segundos da série A Informação, da XMACNA, tirado do episódio 7, "Lógica em fios". O artigo explica o que Turing propôs, o que exatamente ele provou e por que esse limite ainda importa numa época de IA cada vez mais capaz.
Uma máquina feita de papel
O trabalho saiu no artigo "On Computable Numbers, with an Application to the Entscheidungsproblem", que, segundo o próprio cabeçalho, foi recebido em 28 de maio de 1936 e lido em 12 de novembro do mesmo ano. A máquina que ele descreve é quase ridícula de tão simples: uma fita dividida em casas, um símbolo em cada casa e uma tabela de regras. A cada passo, a máquina lê o símbolo, escreve outro, anda uma casa e muda de estado, conforme a regra.
A força da ideia está nessa pobreza. Para Turing, tudo o que uma pessoa consegue calcular seguindo um procedimento passo a passo, uma receita, pode ser feito por uma máquina assim. Por isso o modelo virou a referência do que significa "computar". A tese de Church-Turing, que formaliza essa ideia, afirma que toda computação efetiva pode ser feita por uma máquina de Turing. Celulares e servidores são muito mais rápidos e práticos, mas, por essa tese, não ampliam o que é computável.
A série liga essa máquina à de Ada Lovelace: a mesma ideia de máquina de símbolos, agora descrita no papel. A história de Ada Lovelace e da máquina que ela programou antes de existir está no artigo Antes do computador: como instruções viraram máquinas de ideias.
O limite que ele provou
O título do artigo já anunciava a aplicação. O Entscheidungsproblem, ou problema da decisão, era um desafio proposto por David Hilbert: encontrar um procedimento mecânico capaz de decidir se qualquer fórmula de um sistema lógico é demonstrável. Turing escreve, logo no início, que mostra que esse problema "não pode ter solução".
Para chegar lá, ele prova um resultado sobre as próprias máquinas: não existe um processo geral capaz de examinar a descrição de uma máquina qualquer e decidir se ela continuará imprimindo seus resultados indefinidamente, que era o comportamento esperado das máquinas do artigo. Esse resultado está na origem do que hoje se ensina como o problema da parada: não existe procedimento geral capaz de decidir, para qualquer programa e entrada, se ele vai parar ou não parar. O nome e essa formulação vieram depois de 1936. Até onde vai a atribuição exata a Turing é discutido por especialistas, como no artigo de Joel David Hamkins e Theodor Nenu.
O ponto decisivo é que o limite não é de tecnologia. Não se trata de falta de memória ou velocidade. É um limite lógico, demonstrado para máquinas desse modelo, que pela tese de Church-Turing abrange qualquer procedimento efetivo. Por isso o vídeo diz: "nem a do futuro".
O que isso significa na prática
Para quem não é matemático, a consequência mais concreta é esta: nenhum procedimento geral consegue decidir, para todo programa, se ele vai parar ou não parar. Na prática, sempre haverá casos que só se resolvem olhando o caso.
É por isso que software continua precisando de testes, revisão e monitoramento, e é por isso que sistemas com IA também precisam. Um agente de IA pode ser muito útil, mas não existe um verificador universal que garanta, antes de ligar, como ele vai se comportar em todas as situações. O caminho prático é limitar o que ele pode fazer, registrar o que fez e acompanhar o resultado, com uma pessoa nas decisões que importam. O guia sobre o que é um agente de IA mostra como esse desenho funciona.
Não confundir com o teste de Turing
O nome de Turing também está num teste famoso sobre máquinas que conversam, proposto por ele anos depois. É outra pergunta: o resultado de 1936 trata do que é possível calcular, não de parecer humano. Para entender o que acontece por dentro dos modelos atuais, há o artigo Decifrando a mente da IA.
Três ideias para aplicar
- Separe o difícil do impossível. Muita coisa que parece impossível é só trabalhosa; algumas perguntas, porém, não têm resposta geral. Saber a diferença evita promessas erradas.
- Não espere um verificador universal. Para sistemas com IA, defina limites, registros e revisão em vez de supor que algo vai provar o comportamento em todos os casos.
- Escreva a receita. O que pode ser descrito passo a passo pode ser automatizado; comece pelas tarefas que já têm regras claras.
Assista ao trecho
O corte "Perguntas que nenhuma máquina responde" (YouTube, ID `hM0NV_OlWDs`) é um trecho de A Informação, EP 07, "Lógica em fios", série da XMACNA inspirada em The Information, de James Gleick. O episódio completo está no canal da XMACNA.
Perguntas frequentes
O que é a máquina de Turing?
É um modelo teórico descrito por Alan Turing em 1936: uma fita com símbolos e uma tabela de regras que mandam ler, escrever e andar. Ele se tornou a referência do que significa computar.
O que Turing provou sobre os limites das máquinas?
Que não existe um processo geral para decidir certas perguntas sobre máquinas, como se uma máquina qualquer continuará imprimindo resultados indefinidamente; na formulação moderna, se um programa vai parar ou não parar. Com isso, mostrou que o problema da decisão de Hilbert não tem solução.
Uma IA mais poderosa consegue superar esse limite?
Não, dentro do escopo do resultado. O limite é lógico, não de velocidade ou memória, e vale para máquinas e procedimentos equivalentes no sentido de Turing, o que inclui os computadores digitais que rodam a IA de hoje. Ele não diz que a IA não resolve perguntas difíceis; diz que certos problemas não têm solução geral por esse tipo de procedimento.
Qual a diferença para o teste de Turing?
O resultado de 1936 trata do que pode ser calculado. O teste de Turing, proposto por ele anos depois, discute se uma máquina consegue conversar de forma indistinguível de uma pessoa.
Próximo passo
Se a sua empresa quer saber quais tarefas já têm regras claras para automatizar, o diagnóstico gratuito indica um ponto de partida a partir das respostas ao formulário. O contato comercial é opcional e pode acontecer depois com Hermes, Funcionário Digital da XMACNA, pelo WhatsApp.