Autômatos Celulares
Introdução
O primeiro Autômato Celular foi projetado por John Von Neumann no final dos anos 40 objetivando simular comportamentos evolutivos, sistemas que através de interações e regras simples evoluem e geram comportamentos complexos. O estudo de Neumann despertou grande interesse devido à capacidade de simular comportamentos auto-organizados complexos que são observados em sistemas naturais. Os estudos sobre Autômatos Celulares ganharam importância principalmente pelo sucesso em criar simulações e previsões de eventos naturais e comportamentos dos sistemas vivos. (GREMONINI; VICENTINI, 2008).
Os Autômatos Celulares são aplicados em diversas áreas do conhecimento e em diversas funções, como modelagem de sistemas físicos, biológicos e sociológicos, aplicativos que processam imagens digitais, simulações para estudos de centros urbanos, incêndios em florestas e comportamentos de gases. Na área pedagógica, os Autômatos Celulares são utilizados como uma ferramenta para possibilitar a aprendizagem de fenômenos da natureza por meio de aprendizagem visual (PÁDUA; VIEIRA, 2004).
Autômatos Celulares
Os Autômatos Celulares são sistemas evolutivos baseado em regras simples. Os Autômatos Celulares são formados por uma rede de células, um gride. Cada célula ocupa uma posição na rede e possui um determinado estado inicial que é alterado de acordo com as regras e com o estado das células vizinhas. Cada célula evolui em função do seu estado anterior e do estado anterior das células vizinhas (GREMONINI; VICENTINI, 2008). A partir de um ponto inicial e, baseado em uma regra que determina as condições para mudança de estado, a célula com estado inicial, ao ser alterado, interfere na célula vizinha, desencadeando um efeito evolutivo. Sendo que a mudança dos estados ocorre simultaneamente a cada instante de tempo e sem qualquer tipo de entrada. Iniciando um comportamento autônomo e evolutivo (PÁDUA; VIEIRA, 2004). Segundo Pádua e Vieira (2004) os Autômatos Celulares possuem três características importantes:
- Paralelismo: As células evoluem simultaneamente e independentes. A atualização do estado da célula é autônoma e independente.
- Localidade: A atualização do estado da célula depende somente do seu estado atual e do estado atual das células vizinhas.
- Homogeneidade: As regras valem para todas as células.
Descrição e características
Para Pádua e Vieira (2004) o Autômato Celular pode ser caracterizado por quatro fatores principais: geometria da rede, regras de estados, estados das células e vizinhança.
Geometria
A geometria de um Autômato Celular é o padrão de interconexão do conjunto das células (PÁDUA; VIEIRA, 2004). É a forma e dimensão de cada célula e como elas estão distribuídas na grade ou rede (GREMONINI; VICENTINI, 2008).
Dimensão
Um Autômato Celular pode ser de uma dimensão: a rede de células é formada por uma única linha, as células possuem vizinhas à esquerda e a direita (Figura 1: 1D). Duas dimensões: as células ficam uma do lado da outra, possuem vizinhas a direita, esquerda, superior, inferior e nas diagonais (Figura 1: 2D). Três dimensões: mesmas características da de suas dimensões, porem, são distribuídas tridimensionalmente e podem possui vizinhos na frente e atrás (Figura 1: 3D) (GREMONINI; VICENTINI, 2008).
Figura 1: representações das dimensões de um Autômatos Celulares (GREMONINI; VICENTINI, p.6, 2008).
Formato
As células de um Autômato Celular podem possuir o formato triangular, quadrangular ou hexagonal. Embora possa possuir diversas formas, em um sistema Autômato Celular, a rede de células de cada sistema são todas da mesma forma, não tendo dois tipos de formato em um mesmo sistema (GREMONINI; VICENTINI, 2008).
Estados de uma célula
As células de um Autômato Celular podem possui uma quantidade finita de estados, sendo seu estado alterado de acordo com as regras estabelecidas. Caso todas as células estejam em estado inicial, uma regra pode definir um estado especial para uma célula desencadear todo o processo de evolução, esse estado é chamado de estado inativo (PÁDUA; VIEIRA, 2004). Uma célula pode possuir qualquer valor, normalmente é atribuído um valor entre zero e um (GREMONINI; VICENTINI, 2008).
Regras
As regras determinam as condições para atualização do estado de uma célula. Sabendo quais são os estados das células vizinhas pode-se saber o próximo estado de uma célula. As regras podem ser determinísticas ou não-determinísticas. Regras não-determinísticas definem o próximo estado de uma célula baseado em uma função de probabilidades. As determinísticas, mais comuns, definem o próximo estado baseados nos estados das células vizinhas (GREMONINI; VICENTINI, 2008).
Tipos de vizinhança
O tipo de vizinhança de uma célula depende da dimensão geométrica da rede de células. Se a rede de células for de uma dimensão, a vizinhança de uma célula será uma de cada lado, uma na direita e outra na esquerda. Se a rede for de duas ou três dimensões a vizinhança poderá ser de várias formas: células na vertical, horizontalmente a adjacentes a célula (Figura 2: A e B); células na vertical, horizontal e diagonalmente adjacentes à célula(Figura 2: C e D); vizinhança aleatória e arbitrária (Figura 2: E);
Figura 2: Tipo de vizinhança de um Autômatos Celulares (GREMONINI; VICENTINI, p.7, 2008).
Computação universal e a Máquina de Turing
Os Autômatos Celulares apresentam características e propriedades da computação universal. Prova disso é que os Autômatos Celulares são capazes de simular passo a passo a Maquina de Turing (PÁDUA; VIEIRA, 2004).
A Máquina de Turing é uma máquina abstrata, que tinha todas as características dos computadores atuais, porém foi desenvolvida antes da criação do computador. A máquina de Turing descreve o que um computador pode fazer e aquilo que não pode. Essa máquina, atualmente, é aceita como formalização de algoritmo. A Máquina de Turing consiste no controle de estados finitos em uma fita infinita, divida em células, que se move em ambas a direções. Além da fita que grava caracteres ou estados, a máquina possui também uma cabeça móvel para realizar a leitura e a escrita em uma célula da fita. Cada célula possui um número finito de símbolos e apenas uma célula está na posição atual do cabeçote. Em um movimento da máquina, a fita mudará de estado, gravará um símbolo de fita na célula varrida, e movimentará a cabeça para esquerda ou direita. Um programa para a Máquina de Turing é uma lista de estados para a cabeça móvel. Os caracteres escritos na fita são as condições inicias do programa. O resultado é a seqüência de caracteres inscritos na fita quando a cabeça móvel para. (GREMONINI; VICENTINI, 2008).
No caso dos Autômatos Celulares, segundo Pádua e Vieira (2008), a fita da Máquina de Turing representa cada célula do Autômato Celular. Sendo a fita infinita e dividida em duas partes: a da direita e da esquerda. A parte da direita armazena o símbolo da célula correspondente na fita e a da esquerda indica se o cabeçote está lendo a célula correspondente. De modo, a partir do movimento da fita consegue-se derivar a regra do Autômato Celular:
- Se o cabeçote não estiver lendo a célula ou seus vizinhos a direita e a esquerda na fita, os conteúdos da célula correspondente no Autômatos Celulares não mudam;
- Se o cabeçote estiver lendo uma célula a esquerda e existir uma movimentação para a direita, então, no próximo passo o cabeçote lerá a célula atual. Processo semelhante ocorre na outra direção;
- Se o cabeçote estiver lendo a célula, então no próximo instante de tempo, o conteúdo da primeira parte da célula correspondente.