Revisão Bibliográfica: Autômatos Celulares

Internet

• 
  http://alife.santafe.edu/alife/topics/cas/ca-faq/ca-faq.html: FAQ at the SantaFe Institute
  
• 
  http://www.mathcs.sjsu.edu/faculty/rucker and www.mathcs.sjsu.edu/capow: Thank´s to Rudy Rucker who sent me these URLs.
  

Fonte: http://madeira.cc.hokudai.ac.jp/RD/takai/automa.html

• 
  Cluster shape modeling (Y.Takai, T.Saito, Y.Tomikawa, and N.K.Takai: "A Particle Cluster Deformation Model by the Probabilistic Cellular Automata", IEICE Trans. Inf. and Sys., Vol.J83-A, (2000)
  

• 
  Burks, A. W. Essays on Cellular Automata. Univ. of Ill. Press, 1970.
  
• 
  Codd, E. F. Cellular Automata. Academic Press, Inc., 1968.
  

• 
  Smith, Alvy Ray III. "Cellular Automata Theory." Technical Report No. 2: Digital Systems Laboratory, Stanford Electronics Laboratories. Stanford University, 1969.
  
• 
  Thatcher, J. W. "Universality in the von Neumann Cellular Model." Technical Report 03105-30-T, ORA. The University of Michigan, 1964.
  

• 
  Lee, Chester. "Synthesis of a Cellular Universal Machine using the 29-state Model of von Neumann." Automata Theory Notes. The University of Michigan Engineering Summer Conferences, 1964.
  

1) Auto-Replicação

Uma propriedade essencial da vida é a auto-replicação. Cientistas do SantaFe Institute, especialmente Christopher Langton trabalharam neste tópico (Langton, 1984).

Historicamente John von Neumann propôs a pergunta, se uma máquina auto-replicante existe, então, que tipo de organização lógica de um autômato é suficiente para produzir auto-replicação? Este é um problema que pode ser aproximado para um problema matemático-lógico clássico. O resultado da dedução teórica dele é que esta é uma máquina de Turing universal embutida em uma ordem celular que usa células com 29 estados e uma vizinhança com 5 células. Esta máquina é chamada de construtor universal, e é capaz de construir qualquer máquina descrita na fita introdutória e reproduzir essa fita na construção da máquina. São necessários então na replicação, o autômato celular e o construtor universal dentro deste autômato.

Como John von Neumann (1903-1957) morreu muito cedo, seu sistema não foi publicado. Algum tempo depois, seu amigo Arthur W.Burks (Burks, 1968) publicou sua descoberta. E.F.Codd (Codd, 1968) tentou mostrar uma possibilidade para reduzir a complexidade do autômato de Von Neumann e introduziu uma máquina capaz de realizar a auto-replicação, mas que requeria apenas 8 estados por célula.

Christopher Langton e outros discutiram o problema geral de como definir a propriedade da auto-replicação, excluindo sistemas triviais, mas evitando também uma definição muito restritiva: o problema chave é a demanda em construção universal. Esta demanda não é cumprida através de sistemas naturais (por exemplo, em padrões de peles de animais. O procedimento bioquímico pode criar os padrões em uma pele de jaguar, mas seguramente não é capaz da construção universal...).

Na figura seguinte temos o esquema de auto-replicação apresentado por Codd. A estrutura básica é um chamado caminho de dados e contém um fio de células - células centrais (na figura são representadas pelo estado 2) - cercadas por células de borda (estado 1).

1 1 1 1 1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2
Em vez da série de uns (1) estas células podem ser substituídas através de comandos de estado por exemplo, um sinal "7 0" produz o seguinte comportamento:
tempo t: t+1:

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

1 1 1 0 7 1 1 1 1 1 1 1 1 -> 1 1 1 1 0 7 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

2 1 2 2 1 2

2 1 2 2 1 2

2 1 2 2 1 2

2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2

1 1 1 1 0 7 1 1 1 1 1 1 1 1 1 1 1 1 0 7 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
t+2: t+3:

2 1 2 2 1 2

2 1 2 2 1 2

2 1 2 2 7 2

2 2 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2

1 1 1 1 1 1 0 7 1 1 1 1 1 1 1 1 1 1 1 1 0 7 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Outra propriedade importante desta máquina é a extensão do caminho. A próxima figura mostra a extensão de caminho de um caminho de dados através do comando "7 0 1 1 6 0"

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

1 0 6 1 1 0 1 1 1 1 2 -...-> 1 1 1 1 1 0 6 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2

-...-> 1 1 1 1 1 1 1 1 1 1 1 2

2 2 2 2 2 2 2 2 2 2 2
Uma figura "adicional" deve ser explicada: O emissor periódico. Este padrão muito importante pode ser usado para produzir um sinal de cronômetro ou armazenar dados.

2 2 2 2 2 2

2 0 1 1 1 1 1 2

2 7 2 2 2 2 1 2

2 1 2 2 1 2

2 1 2 2 1 2

2 1 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 2

2 1 1 1 1 1 0 7 1 1 1 1 1 1 1 1 0 7 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

e a máquina de extensão de caminho:

2 2 2 2 2 2

2 0 1 1 6 0 1 2

2 7 2 2 2 2 1 2

2 1 2 2 1 2

2 1 2 2 1 2

2 1 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 2

2 1 0 6 1 1 0 7 1 1 1 1 0 6 1 1 0 7 1 1 2

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Com o novo código descrito em detalhes em Langton (1984) é possível criar loops de auto-replicação e populações iguais de loops com certa facilidade, partindo-se do mesmo principio.

• 
  Arbib, M. A. "A Simple Self-Reproducing Universal Automaton," Information and Control , 1966.
  
• 
  Gardner, Martin. "On cellular automata, self-reproduction, the Garden of Eden and 'Life.'" Scientific American, October 1970.
  
• 
  Moore, E. F. "Machine Models of Self-Reproduction." Proceedings of Symposia in Applied Mathematics. vol. XIV. American Matematical Society, 1962.
  
• 
  von Neumann, J. The Theory of Self-Reproducing Automata. (edited by A. W. Burks), University of Illinois Press, 1966.
  
• 
  Winograd, T. A. I. "A Simple Algorithm for Self-Replication." A. I. Memo 197, Project MAC. MIT, 1970.