Em 1936 não existia nenhum computador. A palavra computer, em inglês, queria dizer uma pessoa que fazia contas por profissão, com lápis e papel, em escritórios de seguros, observatórios e repartições. Turing partiu dessa pessoa. Perguntou o que ela realmente faz quando calcula e foi tirando tudo o que não é essencial.

O que sobra de quem calcula

O raciocínio de Turing, no artigo “Sobre os números computáveis”, é quase uma lista de simplificações:

  • O papel pode ser trocado por uma fita dividida em casas, porque uma conta no papel quadriculado pode ser copiada, casa por casa, numa linha só.
  • Em cada casa cabe um símbolo de uma lista finita: algarismos, letras, um branco.
  • Quem calcula olha para poucas casas de cada vez. Basta olhar para uma: olhar para várias é olhar para uma, depois para a vizinha.
  • Quem calcula tem um estado de espírito, como “estou somando” ou “estou levando um vai-um”. Esses estados são em número finito.
  • Cada passo depende só do estado atual e do símbolo que está sendo lido. O passo consiste em escrever um símbolo, mover-se uma casa para a esquerda ou para a direita e mudar de estado.

O que sobra é uma máquina: uma fita, uma cabeça que lê e escreve, e uma tabela de regras. Cada linha da tabela diz: “no estado tal, lendo o símbolo tal, escreva isto, mova-se para lá e passe para o estado tal”.

Uma máquina que soma 1

Vamos construir uma máquina que soma 1 a um número escrito em binário. Na mão, a conta $1011+1$ é feita da direita para a esquerda: o último 1 vira 0 e “vai um”; o penúltimo 1 também vira 0 e vai um; o 0 seguinte vira 1, e a conta acaba. O resultado é $1100$, ou seja, $11+1=12$.

A máquina faz exatamente isso, com um estado só, “somar”, mais o estado final “parar”. A cabeça começa no último algarismo:

Estado Lê Escreve Move Próximo estado
somar 1 0 esquerda somar
somar 0 1 fica parar
somar branco 1 fica parar

A primeira linha é o vai-um: troca 1 por 0 e continua para a esquerda. A segunda termina a conta quando encontra um 0. A terceira cuida do caso em que todos os algarismos eram 1, como em $111+1=1000$: a cabeça chega ao branco à esquerda do número e escreve ali o novo 1.

Por que tão pobre?

A máquina de Turing parece ridiculamente limitada. Não sabe somar dois números de uma vez, não tem memória além da fita, anda uma casa por vez. Mas essa pobreza é proposital. Turing queria uma definição de “cálculo mecânico” tão simples que ninguém pudesse duvidar de que uma pessoa a executa, e ao mesmo tempo tão geral que cobrisse qualquer cálculo.

A segunda metade dessa aposta é a chamada tese de Church–Turing: tudo o que pode ser calculado por um procedimento mecânico pode ser calculado por uma máquina de Turing. Não é um teorema, porque “procedimento mecânico” não é um conceito matemático antes de Turing. É uma tese que nunca foi contrariada: todos os computadores construídos desde então, do mais simples ao mais rápido, calculam exatamente as mesmas funções que as máquinas de Turing, só que mais depressa.

Exercício: siga a máquina em 111

Comece com a fita $111$ e a cabeça no último 1. Passo 1: lê 1, escreve 0, vai para a esquerda; a fita é $110$. Passo 2: lê 1, escreve 0, esquerda; fita $100$. Passo 3: lê 1, escreve 0, esquerda; fita $000$, e a cabeça está no branco antes do número. Passo 4: lê branco, escreve 1 e para. A fita é $1000$: $7+1=8$, em 4 passos.

Exercício: quantos passos?

Quantos passos a máquina leva para somar 1 a um número cujos últimos $k$ algarismos são 1 e o anterior é 0?

Os $k$ uns viram zeros, um passo cada, e mais um passo transforma o 0 em 1. São $k+1$ passos. Para números pares, que terminam em 0, basta um passo. O pior caso é um número só de uns, com $n$ algarismos: $n+1$ passos.

Fontes: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society (1936) · Charles Petzold, The Annotated Turing (2008).

Todos os tópicos de Alan Turing · ← A vida de Alan Turing · O problema da parada: a pergunta que nenhuma máquina responde →

Créditos das imagens.