Nos últimos anos de vida, von Neumann se fez uma pergunta que parecia de filosofia: uma máquina pode construir uma cópia de si mesma? A dificuldade é lógica. Para construir uma cópia, a máquina precisa de uma descrição de si; mas a descrição faz parte da máquina, então precisaria descrever a si mesma, e assim por diante, numa regressão sem fim.

Descrição, construtor e copiador

A saída de von Neumann, apresentada em palestras a partir de 1948, foi separar três peças:

  1. um construtor $A$, que lê uma descrição $D(X)$ de qualquer máquina $X$ e constrói $X$;
  2. um copiador $B$, que copia qualquer descrição, sem entendê-la;
  3. um controle $C$, que liga os dois.

Agora dê à máquina $A + B + C$ a descrição dela mesma, $D(A + B + C)$. O construtor lê a descrição e constrói uma nova máquina $A + B + C$; o copiador faz uma cópia da descrição e a entrega à máquina nova. O resultado é uma cópia completa, com a sua própria descrição. A regressão acaba porque a descrição é usada de duas maneiras: uma vez como instruções a executar, outra vez como texto a copiar sem ler.

Uma grade de células

Para tornar a ideia rigorosa, von Neumann precisava de um “universo” simples onde máquinas pudessem ser construídas. Por sugestão de Ulam, usou uma grade infinita de quadradinhos, cada um num de 29 estados, que mudam todos ao mesmo tempo, a cada passo, conforme os estados dos quatro vizinhos. Dentro dessa grade, desenhou uma configuração enorme, com um número imenso de células, capaz de ler uma fita, construir uma cópia de si e copiar a fita. O trabalho ficou inacabado com a sua morte e foi completado e publicado pelo seu colaborador Arthur Burks em 1966, com o título Teoria dos autômatos autorreprodutores.

O crachá de Stanisław Ulam em Los Alamos. Foi Ulam quem sugeriu a von Neumann a grade de células como universo para as máquinas.
O crachá de Stanisław Ulam em Los Alamos. Foi Ulam quem sugeriu a von Neumann a grade de células como universo para as máquinas.Los Alamos National Laboratory · Wikimedia Commons · domínio público
Animação de construção de células no autômato de von Neumann. Nove canais transportam sinais que codificam estados distintos; ao chegar a uma célula vazia, cada sinal a transforma no estado especificado. É uma demonstração do mecanismo de construção, não da reprodução de uma máquina inteira.
Animação de construção de células no autômato de von Neumann. Nove canais transportam sinais que codificam estados distintos; ao chegar a uma célula vazia, cada sinal a transforma no estado especificado. É uma demonstração do mecanismo de construção, não da reprodução de uma máquina inteira.Ferkel (Ferkel (talk)) · Wikimedia Commons · Public domain

Essas grades se chamam hoje autômatos celulares. Em 1970, o inglês John Conway inventou um com só dois estados, vivo e morto, e regras de uma linha: uma célula viva com 2 ou 3 vizinhas vivas (contando as diagonais) sobrevive; uma célula morta com exatamente 3 vizinhas vivas nasce; todas as outras morrem ou continuam mortas. O Jogo da Vida, como Conway o chamou, é tão rico que nele também se constroem computadores e máquinas que se copiam.

Exercício: o pisca-pisca

No Jogo da Vida, três células vivas numa linha horizontal formam o “pisca-pisca”. Mostre que no passo seguinte elas viram uma linha vertical.

A célula do meio tem 2 vizinhas vivas e sobrevive. As das pontas têm só 1 vizinha viva e morrem. As duas células logo acima e logo abaixo do meio têm exatamente 3 vizinhas vivas (as três da linha) e nascem. Resultado: uma linha vertical de três. Pelo mesmo raciocínio, ela volta a ser horizontal no passo seguinte, e o padrão pisca para sempre.

Exercício: por que o copiador?

Por que a máquina de von Neumann precisa de um copiador $B$? Não bastaria o construtor $A$ construir também a descrição?

Para construir a descrição a partir das instruções, a descrição teria de conter uma descrição de si mesma, que conteria outra, e assim por diante: a regressão infinita do começo. O copiador evita isso: ele reproduz a descrição como uma sequência de símbolos, sem precisar de outra descrição para fazê-lo.

Fontes: John von Neumann, “The general and logical theory of automata” (palestra de 1948, publicada em 1951) · John von Neumann e Arthur W. Burks (org.), Theory of Self-Reproducing Automata (1966) · Martin Gardner, “The fantastic combinations of John Conway’s new solitaire game ‘life’”, Scientific American (1970).

Todos os tópicos de John von Neumann · ← A moeda viciada que vira justa · O legado de John von Neumann →

Créditos das imagens.