Revisão Bibliográfica: Autômatos Celulares

Revisão Bibliográfica: Autômatos Celulares

Organização Geral

OBS.: Clique sobre o assunto escolhido para ler o seu conteúdo.

Do ponto de vista teórico, o termo Autômato Celular foi introduzido por volta de 1940 por John von Neumann (von Neumann, 1966; Toffoli, 1987) e Stanislaw Ulam. Do ponto de vista prático apenas em 1960 surgem as primeiras aplicações, quando John Horton Conway desenvolveu o Jogo da Vida (Gardner, 1970; Dewdney, 1989; Dewdney, 1990).

Autômatos celulares são sistemas dinâmicos discretos e são descritos freqüentemente como uma contrapartida a equações diferenciais parciais que têm capacidade para descrever sistemas dinâmicos contínuos. O significado de discreto é que espaço, tempo e propriedades do autômato podem ter apenas um finito e contável número de estados. A idéia básica é descrever um sistema complexo simulando-o por interação de células que seguem regras simples. Em outras palavras: _Não descrever um sistema complexo com equações complexas, mas deixar a complexidade emergir por interação de indivíduos simples que seguem regras simples.

Assim as propriedades essenciais dos autômatos celulares são:

_uma malha regular n-dimensional (n é na maioria dos casos de uma ou duas dimensões), onde cada célula desta malha tem um estado discreto;

_um comportamento dinâmico, descrito por regras. Estas regras descrevem o estado de uma célula para o próximo intervalo de tempo como dependente dos estados das células na vizinhança dela.

O primeiro sistema extensivamente calculado em computadores é o Jogo da Vida. Este jogo se tornou tão popular, que despertou o interesse de revistas científicas, que publicaram diversos artigos sobre o seu comportamento. Foram organizadas também competições com testes para provar certos problemas. No final dos anos 80, com a modernização dos computadores, o interesse em Autômatos Celulares ressurgiu. Atualmente, um conjunto de aplicações aceita em simulação de sistemas dinâmicos está disponível.
Construção de Autômatos Celulares:
• A Célula
O elemento básico de um autômato celular é a célula. A célula é um tipo de elemento de memória, e guarda estados. No caso mais simples, cada célula pode ter os estados binários 1 ou 0. Em situações mais complexas as células podem ter estados diferentes.

O estado inicial de um autômato celular está intrinsecamente relacionado ao conteúdo inicial das células, e a partir desta atribuição é desencadeado o processo de evolução do autômato.

Verifica-se, decorrente de várias experimentações, que essa evolução 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.
• A malha
Estas células são organizadas em uma rede espacial - a malha. A mais simples é a malha unidimensional o que significa que todas as células estão organizadas em uma linha como um colar de pérolas. Os autômatos celulares mais comuns são construídos em uma ou duas dimensões. Um autômato celular dimensional tem a grande vantagem de ser muito fácil de visualizar. Os estados de um passo no tempo são plotados em uma dimensão, e o desenvolvimento dinâmico pode ser mostrado na segunda dimensão. Um gráfico plano de um Autômato celular unidimensional mostra assim os estados do passo de tempo 0 ao n. Considere um autômato celular bi-dimensional: um gráfico bi-dimensional pode claramente mostrar somente o estado de um passo no tempo. Assim, visualizar a dinâmica de um autômato celular em 2D é muito difícil.

Por estas razões e porque os autômatos celulares unidimensionais são geralmente mais fáceis de lidar (há um conjunto muito menor de possíveis regras, comparadas a autômatos celulares bidimensionais como será explicado mais adiante). Primeiramente os autômatos celulares unidimensionais foram explorados pelos pesquisadores teóricos. Muitos artigos teóricos disponíveis lidam com propriedades de autômatos celulares unidimensionais.

Definições diferentes de vizinhança são possíveis. Considerando uma malha bidimensional, as definições seguintes são as mais comuns:

Quatro células, as células acima, abaixo, direita e esquerda são chamadas de vizinhança de Von Neumann desta célula. O raio desta definição é 1, já que somente a camada seguinte é considerada.

A vizinhança de Moore é uma amplificação da de Von Neumann, contém as células diagonais também. Neste caso, o raio também é 1 (r=1).

Equivalente a descrição da vizinhança de Moore acima, mas a vizinhança alcança além da distância das células adjacentes. Assim r=2 (ou maior).

Uma abordagem completamente diferente: considera 2x2 células de uma malha de uma só vez.

Vizinhança de Von Neumann	Vizinhança de Moore	Vizinhança de Moore estendida

A célula vermelha é a célula central, as células azuis são as células da vizinhança. Os estados destas células são usados para calcular o próximo estado da célula central (vermelha) de acordo com regras definidas.

Como o número de células em uma malha tem que ser finito (para propósitos práticos) um problema ocorre ao se considerar as vizinhanças propostas descritas acima: O que fazer com as células das bordas? A influência depende do tamanho da malha. Para dar um exemplo: em uma malha 10x10, aproximadamente 40% das células estão nas bordas, em uma malha 100x100 apenas 4% das células são células de borda. De qualquer maneira, este problema deve ser resolvido. Duas soluções são as mais comuns:

Bordas opostas da malha são colocadas juntas. Uma linha unidimensional se torna assim, um círculo, e uma malha bidimensional se torna um plano. As células da borda são refletidas: as conseqüências são propriedades de borda simétricas. O método mais comum é o primeiro.

Um exemplo de resultado dinâmico macroscópico por interação local é "a onda" em um estádio de futebol. Cada pessoa reage apenas ao estado do seu vizinho. Se eles se levantam, ele também se levantará, e após um curto período, senta-se novamente. A interação local conduz a uma dinâmica global. Pode-se organizar as regras em três classes.

1) Cada grupo de estados das células da vizinhança está relacionado ao estado da célula central. Por exemplo, considere um autômato celular unidimensional: uma regra poderia ser "011 -> x0x", que significa que a célula central se torna um 0 no próximo passo de tempo (geração) se a célula à esquerda é 0, a célula da direita é 1 e a célula central é 1. Todo possível estado tem que ser descrito.

2) Regras Totalísticas: o estado da próxima célula central é apenas dependente da soma dos estados das células vizinhas. Por exemplo, se a soma das células adjacentes é 4 o estado da célula central é 1, em todos os outros casos o estado da célula central é 0.

3) Regras legais: são tipos especiais de regras totalísticas. Como não é vantagem na maioria dos casos usar regras que produzem um padrão de malhas de estado zero total (todas as células no autômato são 0), Wolfram definiu as chamadas regras legais. Estas regras são um subconjunto de todas as possíveis regras, uma seleção de regras que não produzem "1" a partir de malhas de estado zero.

O caso 1 mostra por que Autômatos unidimensionais são tão populares em estudos teóricos. Se apenas as células da esquerda, da direita e a própria célula são consideradas nas regras (r=1), existem 256 possíveis regras no total:

2³=8 possíveis estados para três dígitos binários, cada um destes 8 estados pode produzir um 1 ou um 0 para a célula central na próxima geração. Assim 2⁸=256 regras possíveis.

Assim, em termos gerais o número de regras pode ser calculado por k^kn onde k é o número de estados para a célula e n é o número de vizinhos (inclusive a própria célula central). Assim nós podemos ver facilmente, que para um autômato celular bidimensional com vizinhança de Moore, 2 estados e r=1 seguem k=2 e n=9. Assim 2²⁹=262.144 possíveis regras existem.

Outras variações importantes são os autômatos celulares reversíveis. A única diferença entre estes e os autômatos celulares descritos acima é, que o tempo de desenvolvimento para o sistema é completamente reversível. Isso significa, que a qualquer passo de tempo do desenvolvimento das regras é permitido ir adiante ou voltar no tempo, sem perder qualquer informação.
• Espaços celulares, Vizinhos e Tempo.
O espaço celular é definido como:

onde i, j são o número de colunas e linhas da malha com a extensão máxima de n colunas e m linhas. Seja a definição da vizinhança de Moore:

(Outras definições de vizinhança são semelhantes. Por exemplo, para a vizinhança de Moore estendida temos que substituir o <= 1 por <= 2).

Considere um autômato celular unidimensional com dois possíveis estados para cada célula, em termos matemáticos Z={0,1} e as regras totalísticas significando, que o próximo estado de cada célula depende apenas da soma dos estados das células adjacentes. Assim o estado da célula z_i para o próximo passo de tempo (t+1), pode ser definido pela regra totalística como:

assim, o estado da célula central z_i é 1 se a soma das células da vizinhança inclusive a célula central for ς, 0 caso contrário. No caso de um autômato bidimensional esta formulação não é muito diferente e será mostrada nos exemplos que descrevem o Jogo da Vida.

É possível nomear um número definido a cada possível regra legal. Estes números-códigos podem ser representados como segue:

onde a função f é definida como

Agora um código para todas as regras legais pode ser calculado por:

No caso de um autômato como descrito acima, para todas as 32 regras legais, pode-se nomear um Código definido C_f contendo todos os números pares de 0 a 64.

As propriedades gerais dos autômatos celulares são:

• 
  Desenvolvimento de autômatos Celulares no espaço e tempo
  
• 
  Um autômato celular é um método de simulação discreto. Conseqüentemente espaço e tempo são definidos em passos discretos.
  
• 
  Um autômato celular é construído de células que são:
  

• 
  Alinhadas em um fio no caso dos autômatos unidimensionais.
  
• 
  Organizadas em malhas de duas ou mais dimensões no caso de autômatos de duas ou mais dimensões.
  
• 
  O número de estados de cada célula é finito
  
• 
  Os estados de cada célula são discretos
  
• 
  Todas as células são idênticas
  
• 
  O estado futuro de cada célula depende apenas do estado atual da célula e dos estados das células na vizinhança
  
• 
  O desenvolvimento de cada célula é definido por regras
  

• 
  Machado, K. F. , Schüler, J.P. S., Vieira, M.-H. T. – Autômatos Celulares
  

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

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

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