Autômato celular de Codd
 |
 | A tradução deste artigo está abaixo da qualidade média aceitável. (Setembro de 2021) |
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[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 | não | 86 células |
Especificação[editar | editar código-fonte]
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.
Ver também[editar | editar código-fonte]
Referências
- ↑ von Neumann, John; Burks, Arthur W. (1966). «Theory of Self-Reproducing Automata.». www.walenz.org. Consultado em 28 de janeiro de 2012. Cópia arquivada em 5 de janeiro de 2008
- ↑ Codd, Edgar F. (1968). Cellular Automata. [S.l.]: Academic Press, New York
- ↑ Banks, Edwin (1971). Information Processing and Transmission in Cellular Automata. [S.l.]: PhD thesis, MIT, Department of Mechanical Engineering
- ↑ Langton, C. G. (1984). «Self-Reproduction in Cellular Automata». Physica D: Nonlinear Phenomena. 10 (1-2): 135–144. doi:10.1016/0167-2789(84)90256-2
- ↑ a b Hutton, Tim J. (2010). «Codd's self-replicating computer» (PDF). Artificial Life. 16 (2): 99–117. PMID 20067401. doi:10.1162/artl.2010.16.2.16200
Ligações externas[editar | editar código-fonte]
- 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.