Autômatos Celulares



Marlo-Hur Toral Vieira MC060/2000

João Paulo Schwarz Schüler MC038/2000

Karla Fedrizzi Machado MC043/2000

Autômato Finito


Um autômato finito determinístico, ou simplesmente autômato finito, pode ser visto como como uma máquina composta, basicamente, de três partes:

  1. Fita. Dispositivo de entrada que contém a informação a ser processada;

  2. Unidade de Controle. Reflete o estado corrente da máquina. Possui uma unidade de leitura (cabeça da fita) a qual acessa uma célula da fita de cada vez e movimenta-se exclusivamente para a direita;

  3. Programa ou Função de Transição. Função que comanda as leituras e define o estado da máquina.



Autômato Celular


Um autômato celular é um conjunto de autômatos identicamente programados que interagem entre si. No autômato celular, cada autômato é uma célula. Podemos construir autômatos celulares com uma ou mais dimensões. Um autômato celular 1D é um autômato celular que possui uma seqüência infinita de autômatos justapostos em linha. Um autômato celular 2D é composto por autômatos postos lado a lado formando um plano. A mesma abordagem pode ser usada para autômatos celulares de maior dimensionalidade.[GRE93]



Autômato Celular a partir de Autômatos Finitos


Um autômato celular, pensado a partir de um autômato finito, considera como fita (neste caso finita) o valor individual da vizinhança de cada célula, ou seja, o peso agregado de cada vizinho. A unidade de controle (cabeça da fita) é um ente de apontamento, muito provavelmente um índice ou ponteiro, que individualiza os vizinhos de uma célula. O programa ou função de transição de uma célula pode ser visto como uma fórmula que considera os pesos da vizinhança, juntamente com o próprio peso, e atribui um novo valor a esta célula.


Autômato Celular Unidimensional


Normalmente, no autômato celular, o próximo estado de uma célula depende do seu estado atual e do estado das células vizinhas. Em um autômato celular 1D, o próximo estado de uma célula depende do estado dela própria e de suas duas vizinhas. Normalmente, só existem dois estados possíveis para cada célula: 0 ou 1 ou verdadeiro ou falso.[GRE93] Nesse caso, o estado de uma célula é definido com 1 bit. Sendo assim, se o próximo estado de cada célula é função do seu próprio estado e o estado de suas duas células vizinhas, teremos uma entrada de 3 bits para cada célula.




Autômato Celular Bidimensional


Um autômato de duas dimensões implica numa vizinhança celular com oito elementos, ficando a célula de transição no centro destes elementos. Assim, o cálculo do novo estado de uma célula considera nove bits no processo.




Autômato Celular e o seu Estado Inicial


O estado inicial de um autômato celular está intrinsecamente relacionado ao conteúdo inicial das célula. Qualquer valor (normalmente entre zero e um) pode ser atribuído a cada célula, e a partir desta atribuição é desencadeado o processo de evolução do autômato.


Verifica-se, decorrente de várias experimentações, que a evolução do autômato, normalmente, flui para estados bem diversos conforme o estado inicial. De maneira mais específica, com pequenas variações no estado inicial se tem grandes variações nos estados remotamente conseqüentes, ou seja, os autômatos celulares são muito sensíveis às variações no seu estado inicial.


Os autômatos celulares são muito úteis para resolver alguns problemas de forma distribuída.[WIL96] Por exemplo, uma maneira muito simples de desenhar o triângulo de Sierpinski é simplesmente construir um autômato celular 1D em que cada célula segue a seguinte regra de transição: ou exclusivo dos estados das células vizinhas. Cada linha horizontal do triângulo de Sierpinski é um momento durante a evolução do autômato celular.





FIGURA - Vista de uma região do Triângulo de Sierpinski. Cada parte do triângulo revela estrutura semelhante ao seu todo.









Outra maneira de gerar o triângulo de Sierpinski é simplesmente construir um autômato celular em que cada célula é programada da seguinte fórmula: o próximo estado de cada célula será o resto da divisão por 2 da soma dos estados das células vizinhas. Segue em anexo autômatos celulares 1D e 2D implementados em Pascal baseados em resto da divisão por números naturais inferiores a 255.



Game of Life

Game of Life é um autômato celular criado em 1970 por um jovem matemático chamado John Horton Conway. Sua meta era criar um simulador de células com três objetivos: nenhum desenho ( colônia ) simples iria obviamente crescer para sempre, algumas colônias simples deveriam crescer selvagemente, garantir que colônias simples poderiam levar muito tempo para desaparecer ou estabilizar. O próximo estado de cada posição ocupável por célula é função dos estados anteriores de suas vizinhas e dela própria.

O simulador Life segue a uma regra de produção bidimensional que obedece às seguintes regras gerais de produção: todas as células que tiverem duas ou três células vizinhas permanecem vivas, e em todos os espaços ocupáveis por células que tiverem três vizinhas, nascerá uma célula na próxima geração e em qualquer outro caso a célula perecerá. Vale observar que cada posição ocupável por células possui um estado "viva" ou "não viva". [DEW85]


FIGURA 5.5 - Algumas Colônias Estáveis



Autômatos Celulares Implementados



Foram implementados diversos autômatos celulares em Turbo Pascal V. 5.5. Considerando que muitos autômatos implementados são muito semelhantes entre si, apresentaremos aqui somente os mais importantes. Em anexo, segue um disquete com todos os autômatos celulares implementados na forma de código executável e código fonte.

Para efeito de notação, entenderemos por c[x,y] o autômato de índices x e y pertencente a um autômato celular 3D. Ainda para efeito de notação, entendemos o operador mod como o operador de resto da divisão.

Na tabela que segue, podemos ver as fórmulas usadas para implementação dos autômatos.






FIGURA 1 – DANTE1.PAS






FIGURA 2 – DANTE2.PAS




FIGURA 3 – DANTE3.PAS






FIGURA 4 – DANTE4.PAS







FIGURAS 5 e 6 – DANTE7.PAS



Nome

N. Dimensões

C[x,y]=

DANTE1.PAS

2

C[x-1] xor C[x+1]

DANTE2.PAS

    2

(C[x-1] + C[x+1]) mod 10

DANTE3.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] ) mod 119

DANTE4.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] +

C[x-1,y-1] + C[x+1,y-1] + C[x+1,y-1] + C[x+1,y+1] ) mod 4

DANTE5.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] +

C[x-1,y-1] + C[x+1,y-1] + C[x+1,y-1] + C[x+1,y+1] ) mod 2

DANTE7.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] ) mod 200

DANTE8.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] ) mod 100

DANTE9.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] ) mod 20

DANTE10.PAS

3

(C[x-1,y] + C[x+1,y] + C[x,y-1] + C[x,y+1] +

C[x-1,y-1]*2 + C[x+1,y-1]*2 + C[x+1,y-1]*2 + C[x+1,y+1]*2 ) mod 2

As fórmulas de geração dos programas DANTE2.PAS e DANTE3.PAS são semelhantes às fórmulas encontradas no livro Chaos and Fractals[PEIT] .



Impementação de Autômato 2D

Observe no código que segue a simplicidade de se construir um autômato celular 2D.

type TVIDEO = array[0..199,0..319] of byte;

procedure Automato2D(var R:TVIDEO); // DANTE4.PAS

var I,J:integer;

D:TVIDEO;

begin

D:=R;

for I:=1 to 318 do

for J:=1 to 198 do

D[J,I]:=(R[J,I-1] + R[J,I+1] +

R[J-1,I] + R[J+1,I] +

R[J-1,I-1] + R[J+1,I+1] +

R[J-1,I+1] + R[J+1,I-1]

) mod 4;

R:=D;

end;


Conclusão

Podemos observar que os autômatos celulares apresentam computação distribuída e paralela. É interessante verificar que modelos muito simples para as células resultam em comportamentos globais muito complexos.

Os autômatos celulares podem ser relacionados com a teoria do CAOS. Vale lembrar que podemos construir fractais como o triângulo de Sierpinski. Outro aspecto que se ressalta nos autômatos celulares é a sua imensa dependência de seus estados iniciais. Uma pequena modificação no estado inicial de um autômato celular pode provocar uma grande modificação em sua evolução.



Bibliografia


        [GRE93] GREEN, David G. Cellular Automata , 1993. Disponível por WWW em http://life.csu.edu.au/complex/tutorials/tutorial1.html

        [PEIT] PEITGEN, Heinz-Otto; JÜRGENS, Harmut; SAUPE, Dietmar. Chaos and Fractals. Chapter 8. Springer-Verlag.


[WIL96] WILBERGER, A. Martim. Introduction to Cellular Automata for Modeling and Simulation. SCS, Istanbul, Turkey.