Autômato Celular de Codd

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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 Newmann, 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[editar | editar código-fonte]

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

  • 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.[2] 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. [3] 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.[4]

Comparação com o conjunto de regras do AC[editar | editar código-fonte]

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[5]
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 no 86 células

Especificação[editar | editar código-fonte]

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[editar | editar código-fonte]

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.[5] 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.

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. von Neumann, John (1966). Theory of Self-Reproducing Automata.. www.walenz.org. Página visitada em 2012-01-28. Cópia arquivada em 2008-01-05.
  2. Codd, Edgar F.. Cellular Automata. [S.l.]: Academic Press, New York, 1968.
  3. Banks, Edwin. Information Processing and Transmission in Cellular Automata. [S.l.]: PhD thesis, MIT, Department of Mechanical Engineering, 1971.
  4. Langton, C. G.. (1984). "Self-Reproduction in Cellular Automata". Physica D: Nonlinear Phenomena 10 (1-2): 135–144 pp.. DOI:10.1016/0167-2789(84)90256-2.
  5. a b Hutton, Tim J.. (2010). "Codd's self-replicating computer". Artificial Life 16 (2): 99–117 pp.. DOI:10.1162/artl.2010.16.2.16200. PMID 20067401.

Ligações externas[editar | editar código-fonte]