Em 1928, o alemão David Hilbert propôs um desafio que chamou de Entscheidungsproblem, o “problema da decisão”: encontrar um procedimento mecânico que, recebendo qualquer afirmação matemática escrita na linguagem da lógica, respondesse em tempo finito se ela é verdadeira ou falsa. Se existisse, a matemática viraria uma linha de montagem: bastaria escrever a pergunta e girar a manivela.

Hilbert acreditava que a resposta era sim. Oito anos depois, Turing e o americano Alonzo Church mostraram, cada um por um caminho, que é não.

Uma pergunta mais simples

Turing não atacou a pergunta de Hilbert de frente. Primeiro achou uma pergunta mais modesta que nenhuma máquina consegue responder. Hoje ela se conta assim:

Dado um programa e uma entrada, o programa vai parar um dia, ou vai rodar para sempre?

Às vezes é fácil saber. Um programa que soma 1 a um número para logo. Um programa que conta $1,2,3,\ldots$ sem condição de saída nunca para. Mas há programas muito curtos sobre os quais ninguém sabe a resposta. Este, por exemplo, testa a famosa conjectura de Goldbach, de que todo número par maior que 2 é soma de dois primos:

  1. Comece com $n=4$.
  2. Se $n$ não for soma de dois primos, pare.
  3. Senão, some 2 a $n$ e volte ao passo 2.

Esse programa para se e somente se a conjectura for falsa. Saber se ele para é resolver um problema aberto desde 1742. Um método geral para decidir se programas param resolveria esse e muitos outros de uma vez.

A prova

Suponha, por absurdo, que exista uma máquina $P$ que faz o serviço. Ela recebe a descrição de um programa $M$ e uma entrada $x$ e responde, sempre em tempo finito:

$$P(M,x)=\begin{cases}\text{“para”}&\text{se }M\text{ para com a entrada }x,\\ \text{“não para”}&\text{se }M\text{ roda para sempre.}\end{cases}$$

Com $P$ em mãos, construa uma nova máquina, a do contra, $D$. Ela recebe a descrição de um programa $M$ e faz o seguinte:

  • pergunta a $P$ o que $M$ faz quando recebe a própria descrição como entrada;
  • se $P$ disser “para”, $D$ entra num laço infinito;
  • se $P$ disser “não para”, $D$ para.

Agora vem a pergunta fatal: o que $D$ faz quando recebe a própria descrição?

  • Se $D(D)$ para, então $P$ respondeu “não para” sobre $D(D)$, e $P$ errou.
  • Se $D(D)$ não para, então $P$ respondeu “para”, e $P$ errou de novo.

Nos dois casos, $P$ erra. Logo a máquina $P$ não existe. $\blacksquare$

A diagonal

Essa prova é um parente próximo da diagonal de Cantor. Imagine uma tabela infinita em que a linha $i$ é o programa $M_i$, a coluna $j$ é a entrada “descrição de $M_j$” e cada casa diz se o programa para. A máquina $D$ olha só para a diagonal, as casas $(i,i)$, e faz o contrário de cada uma. Por isso não pode ser nenhuma das linhas: difere da linha $i$ pelo menos na casa $(i,i)$.

No artigo de 1936, Turing não usou exatamente a palavra “parar”: a pergunta dele era se uma máquina imprime infinitos algarismos ou trava no meio. O nome “problema da parada” veio depois, nos anos 1950. A ideia é a mesma. E dela Turing tirou a resposta a Hilbert: se houvesse um método para decidir qualquer afirmação lógica, ele decidiria também a afirmação “a máquina $M$ para”, o que é impossível.

Exercício: este programa para?

Programa: comece com $n=7$. Enquanto $n\neq1$: se $n$ é par, $n\leftarrow n/2$; senão, $n\leftarrow3n+1$.

Siga: $7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1$. Para, depois de 16 passos. Ninguém sabe se ele para para todo $n$ inicial: é a conjectura de Collatz, aberta desde 1937. Os computadores já a verificaram para números enormes, mas verificar casos não é provar.

Exercício: onde a prova usa a máquina P?

Explique por que a prova não diz que “nenhum programa pode ser analisado”.

A prova só mostra que não existe um único método que acerte para todos os programas. Para muitos programas particulares, decidir se param é fácil, e há ferramentas que fazem isso todos os dias. O que não existe é a máquina $P$ universal, que nunca erra e nunca deixa de responder.

Fontes: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem” (1936) · Alonzo Church, “An unsolvable problem of elementary number theory”, American Journal of Mathematics (1936) · Martin Davis, The Universal Computer (2000).

Todos os tópicos de Alan Turing · ← A máquina de Turing: calcular com lápis, fita e regras · Números computáveis: quase todo número é impossível de calcular →

Créditos das imagens.