Euler's Eyes
2026-10-16
A máquina universal: o programa também é um dado
Cada máquina de Turing faz uma coisa só. A que soma 1 soma 1; a que escreve $\frac17$ escreve $\frac17$. Para fazer outra conta, seria preciso outra máquina. Em 1936, isso era o normal: as calculadoras mecânicas, os tabuladores de cartões e as máquinas de tábuas de maré eram construídos para uma tarefa, e trocar de tarefa era trocar de máquina ou religar fios.
No mesmo artigo, Turing mostrou que isso não é necessário.
Uma máquina que lê máquinas
A tabela de regras de qualquer máquina pode ser escrita como texto, numa fita. Turing então descreveu uma máquina especial, $U$, a máquina universal, que faz o seguinte:
- Na fita, recebe a descrição de uma máquina $M$ e, depois dela, uma entrada $x$.
- Procura na descrição a regra que corresponde ao estado atual de $M$ e ao símbolo que $M$ estaria lendo.
- Executa essa regra na parte da fita que representa a fita de $M$, anota o novo estado e volta ao passo 2.
Assim, $U$ imita passo a passo qualquer máquina, desde que receba a sua tabela. Em símbolos:
$$U(\langle M\rangle,x)=M(x)\quad\text{para toda máquina }M\text{ e toda entrada }x.$$O preço é a lentidão: cada passo de $M$ custa a $U$ muitos passos de busca e cópia. Mas o que $U$ consegue calcular é exatamente o que todas as máquinas juntas conseguem.
O programa na memória
A consequência prática é a ideia do programa armazenado. Em vez de construir uma máquina para cada tarefa, constrói-se uma só, e a tarefa entra como dado, na mesma memória que guarda os números. Trocar de tarefa vira trocar de texto. É o que acontece quando você abre um aplicativo no celular: o aparelho é sempre o mesmo, e o que muda é a descrição que ele lê.
Mais ainda: se o programa é um dado, um programa pode ler, escrever e modificar outros programas. É isso que fazem os compiladores, os sistemas operacionais e, de certo modo, a própria máquina $D$ da prova do problema da parada, que recebe a sua própria descrição.
Do papel ao metal
Depois da guerra, em 1945–1946, Turing escreveu o projeto completo de um computador de programa armazenado, o ACE (Automatic Computing Engine), no Laboratório Nacional de Física. Era ousado: memória em linhas de atraso de mercúrio, velocidade de um milhão de pulsos por segundo, e até a ideia de que a máquina poderia ser programada para modificar as próprias instruções. A burocracia e a falta de engenheiros atrasaram a construção. Uma versão reduzida, o Pilot ACE, só funcionou em 1950, e por algum tempo foi um dos computadores mais rápidos do mundo.
Enquanto isso, em Manchester, Frederic Williams e Tom Kilburn fizeram rodar, em 21 de junho de 1948, o primeiro programa armazenado numa memória eletrônica, numa máquina apelidada de Baby. Turing chegou a Manchester alguns meses depois e trabalhou nas máquinas que vieram em seguida.
Exercício: escreva uma máquina como texto
Codifique a máquina que soma 1 como uma sequência de quíntuplas (estado, lê, escreve, move, próximo estado), usando S para somar, P para parar, B para branco, E para esquerda e F para fica.
$$\text{S1 0 E S}\quad\text{S0 1 F P}\quad\text{SB 1 F P}$$São 15 símbolos. Escritos numa fita, eles são a descrição $\langle M\rangle$ que a máquina universal lê para imitar a máquina original.
Exercício: quantos passos custa imitar?
Suponha que, para imitar um único passo de $M$, a máquina universal precise percorrer a descrição de $M$ inteira, com $d$ casas, e voltar. Se $M$ leva $t$ passos, quantos passos, aproximadamente, a máquina universal leva?
Cada passo de $M$ custa cerca de $2d$ passos de $U$, então o total é cerca de $2dt$. Para a máquina que soma 1, com $d=15$ e $t=4$ passos em $111+1$, seriam uns 120 passos: trinta vezes mais lento, mas o mesmo resultado.
Fontes: Alan Turing, “On computable numbers” (1936) e “Proposed electronic calculator” (1946) · B. Jack Copeland (org.), Alan Turing’s Automatic Computing Engine (2005) · The Manchester Baby, Science and Industry Museum.
Todos os tópicos de Alan Turing · ← Números computáveis: quase todo número é impossível de calcular · A Enigma: 159 quintilhões de chaves e um defeito →