Autômato celular de Codd

Uma configuração simples no autômato celular de Codd. Os sinais passam por meio de um fio feito de células no estado 1 (azul) revestido por células no estado 2 (vermelho). Dois sinais de treinamento circulam em volta de um loop e são duplicados numa T-junção para uma seção de fio com final aberto. O primeiro (7-0) causa um revestimento final do fio para ficar exposto. O segundo (6-0) reveste novamente o fim do exposto, deixando a célula do primeiro fio mais longa que antes.

Autômato celular de Codd é um autômato celular (AC) inventado pelo Britânico cientista da computação Edgar F. Codd em 1968. Foi feita para recriar o cálculo e a construção universal do AC de von Neumann, mas com menos estados: 8 em vez de 29. Codd mostrou que é possível fazer uma máquina no seu autômato celular que se auto-reproduz, de uma maneira similar ao de von Neumann construtor universal mas nunca deu uma implementação completa.

História

Nas décadas de 1940 e 1950, John von Neumann propôs o seguinte problema:

• Que tipo de organização lógica é suficiente para um autômato ser capaz de se auto-reproduzir?

Ele foi capaz de construir um autômato celular com 29 estados, e com isso um construtor universal. Codd, trabalhando em cima dos resultados de von Neumann, achou uma máquina mais simples com 8 estados. Isso modificou a pergunta de von Neumann para a seguinte:

• Que tipo de organização lógica é necessária para um autômato ser capaz de reproduzir-se?

Três anos depois do trabalho de Codd, Edwin Roger Banks mostrou um autômato celular de 4 estados na sua tese de PhD, que também era capaz de fazer computação e construção universal, mas também não implementou uma máquina auto-reprodutora. John Devore, na sua tese de mestrado de 1973, modificou as regras de Codd para reduzir imensamente o tamanho do modelo de Codd a ponto de que poderia ser implementada nos computadores da época. Porém, a fita de dados da auto-replicação era muito longa; o modelo original de Devora foi mais tarde capaz de completar a replicação usando Golly. Christopher Langton fez outra modificação no autômato celular de Codd em 1984 para criar os loops de Langton, exibindo a auto-replicação com muito menos células que o necessário para a auto-reprodução nos modelos anteriores, ao custo de remover a habilidade de computação e construção universal.

Comparação com o conjunto de regras do AC

AC	número de estados	simetrias	computação e construção universal	tamanho da máquina auto-reprodutora
von Neumann	29	nenhuma	sim	130,622 células
Codd	8	rotações	sim	283,126,588 células
Devore	8	rotações	sim	94,794 células
Banks-IV	4	rotações e reflexões	sim	desconhecido
Loops de Langton	8	rotações	não	86 células

Especificação

O braço de construção no AC de Codd pode ser movido em posição usando os comandos listados no texto. Aqui o braço vira para a esquerda, depois para a direita, e depois escreve na célula antes de retrair sobre o mesmo caminho.

O AC de Codd tem oito estados determinados por uma vizinhança de von Neumann com simetria rotacional.

A tabela abaixo mostra os sinais de treinamento necessários para realizar diferentes tarefas. Alguns dos sinais de treinamento precisam ser separados por dois espaços brancos (estado 1) no fio para evitar interferência, portanto o sinal de treinamento estendido usado na imagem no topo aparece aqui como '70116011'.

propósito	sinal de treinamento
extend	70116011
extend_left	4011401150116011
extend_right	5011501140116011
retract	4011501160116011
retract_left	5011601160116011
retract_right	4011601160116011
mark	701160114011501170116011
erase	601170114011501160116011
sense	70117011
cap	40116011
inject_sheath	701150116011
inject_trigger	60117011701160116011

Computador e construtor Universal

Codd modelou um computador auto-replicador no autômato celular, baseado na máquina Wang-b. Porém, o modelo era tão colossal que só foi implementado em 2009, quando Tim Hutton construiu uma configuração explícita. Havia alguns erros pequenos no modelo de Codd, portanto a implementação de Hutton difere levemente tanto na configuração quanto no conjunto de regras.

Ver também

• Vida artificial
• Jogo da vida
• Wireworld

Ligações externas

• The Rule Table Repository has the transition table for Codd's CA.
• Golly - supports Codd's CA along with the Game of Life, and other rulesets.
• Download the complete machine (13MB) and more details.