O título do artigo de 1936 não fala de máquinas. Fala de números: “Sobre os números computáveis”. Turing os definiu assim: um número real é computável quando existe uma máquina que escreve, um depois do outro, todos os seus algarismos, sem nunca errar nenhum.

Quem é computável

Quase todos os números que aparecem na escola são computáveis.

  • Frações: $\frac17=0{,}142857142857\ldots$ A máquina faz a divisão longa e repete o ciclo para sempre.
  • Raízes: $\sqrt2=1{,}41421356\ldots$ Para achar o próximo algarismo, a máquina testa de 0 a 9 qual é o maior que, acrescentado, ainda dá um número cujo quadrado não passa de 2.
  • $\pi$ e $e$: há séries que os aproximam tanto quanto se queira, como $e=1+\frac1{1!}+\frac1{2!}+\frac1{3!}+\cdots$, e com elas uma máquina produz qualquer algarismo, mais cedo ou mais tarde.

Parece que todo número “de verdade” é computável. E aqui vem a surpresa: quase nenhum é.

As máquinas podem ser contadas

Toda máquina de Turing é descrita por uma tabela finita de regras. Essa tabela pode ser escrita como um texto com um alfabeto fixo e, portanto, como um único número inteiro, que Turing chamou de número de descrição. Basta trocar cada símbolo por um algarismo.

Então as máquinas podem ser postas numa lista: a de menor número de descrição, a seguinte, e assim por diante. Muitos números não descrevem máquina nenhuma, e muitas máquinas não escrevem número nenhum, mas isso não importa. O que importa é que os números computáveis cabem numa lista $c_1,c_2,c_3,\ldots$ Em linguagem técnica, são enumeráveis.

Os reais não podem ser contados

Em 1891, Georg Cantor mostrou que os números reais não cabem numa lista. A prova é a diagonal. Suponha uma lista de todos os reais entre 0 e 1:

$$\begin{aligned} r_1&=0{,}\underline{5}\,1\,3\,9\ldots\\ r_2&=0{,}2\,\underline{7}\,0\,4\ldots\\ r_3&=0{,}8\,8\,\underline{1}\,6\ldots\\ r_4&=0{,}3\,0\,2\,\underline{2}\ldots \end{aligned}$$

Construa um número $d$ trocando o algarismo da diagonal: onde houver 5, ponha 6; onde houver qualquer outro, ponha 5. Aqui, $d=0{,}6555\ldots$ Esse $d$ difere de $r_1$ na primeira casa, de $r_2$ na segunda, de $r_n$ na $n$-ésima. Não está na lista. Logo, nenhuma lista contém todos os reais.

Juntando os dois fatos: os computáveis cabem numa lista, os reais não. Sobram reais fora de qualquer máquina, e são a imensa maioria. Se você escolher um número real ao acaso, a chance de ele ser computável é zero.

Exercício: aplique a diagonal

A lista começa com $0{,}1234\ldots$, $0{,}5555\ldots$, $0{,}9090\ldots$, $0{,}3141\ldots$ Use a regra “5 vira 6, o resto vira 5” e escreva os quatro primeiros algarismos do número diagonal.

A diagonal é $1,5,9,1$. Trocando: $1\to5$, $5\to6$, $9\to5$, $1\to5$. O número é $0{,}5655\ldots$, que difere de cada um dos quatro na casa da diagonal.

Exercício: 1/7 é computável

Descreva em palavras a máquina que escreve os algarismos de $\frac17$.

A máquina guarda o resto da divisão, que só pode ser 1, 3, 2, 6, 4 ou 5. Em cada passo, multiplica o resto por 10, escreve o quociente por 7 e guarda o novo resto: $10=1\cdot7+3$, escreve 1; $30=4\cdot7+2$, escreve 4; $20=2\cdot7+6$, escreve 2; e assim por diante. Como há só seis restos possíveis, seis estados bastam, e a máquina escreve $142857$ para sempre.

Fontes: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem” (1936) · Georg Cantor, “Über eine elementare Frage der Mannigfaltigkeitslehre” (1891) · Charles Petzold, The Annotated Turing (2008).

Todos os tópicos de Alan Turing · ← O problema da parada: a pergunta que nenhuma máquina responde · A máquina universal: o programa também é um dado →

Créditos das imagens.