Autômatos Celulares

AUTÔMATOS CELULARES: REVISÃO BIBLIOGRÁFICA E EXEMPLOS DE IMPLEMENTAÇÕES

www.unicentro.br

Lucas Gremonini

Eduardo Vicentini

RESUMO Autômatos Celulares são modelos matemáticos propostos inicialmente para simular a evolução da vida (Game of life). Por expressar, em sua evolução, comportamentos característicos dos sistemas naturais, os Autômatos Celulares difundiram-se e sua formalização e implementação computacional ganhou força nos últimos anos. Vários sistemas biológicos, físicos e sociais servem de estímulo para as simulações, utilizando as técnicas dos Autômatos Celulares. A evolução de um Autômato Celular mostra semelhança com padrões encontrados na natureza. Os modelos implementados são delimitados por uma malha contendo células de mesmo tamanho e forma e que são identificadas por estados. Os estados evoluem através de regras de interação locais e com evolução temporal discreta. Neste trabalho, apresenta-se alguns dos aspectos gerais que caracterizam os Autômatos Celulares e diferentes implementações, utilizando como base sistemas reais que evoluem no tempo, mostrando, assim, o potencial de aplicabilidade dos Autômatos Celulares. Palavras-chave: Autômatos Celulares; Aplicações e Implementações de Autômatos Celulares; Sistemas Complexos

ABSTRACT Cellular Automaton are mathematic models proposed initiately to simulate the evolution of life (Game of life). For express, in its evolution, characteristics behaviors of the natural systems, the Automaton Celullars diffused and its formalization and computational implementation earn power in the latest years. Various biologics systems, physicist and socials are used of stimulate to the simulations utilizing the technicals of the Automaton Celullars. The evolution of one Automaton Celullar display similarity with standards met in the nature. The models implemented are delimitated for one trap contain cells of the same size and way and that are identified for states. The states develop through of rules of local interations and with temporal evolution discreet. In this work present some general aspects that characterize the Automaton Celullars and different implementations utilizing with base of real systems that develop at the time, displaing like the potential of applicable of the Automaton Celullars. Key-words: Cellular Automaton; Apliations and Implementations of Automaton Celullars; Complicated Systems.

AUTÔMATOS CELULARES: REVISÃO BIBLIOGRÁFICA E EXEMPLOS DE IMPLEMENTAÇÕES

Revista Eletrônica Lato Sensu – UNICENTRO

Página 2 de 19

1 INTRODUÇÃO

Autômatos Celulares são utilizados como modelo para a determinação e/ou formação de padrões que tentam ou explicam fenômenos da natureza, bem como comportamentos sociais, ambientais e biológicos, assim como fatores que influenciam em suas regras de inter-relação/interação. Entre esses modelos, pode-se citar o modelo de autômato celular proposto por John Von Neumann com o auxílio de Stanislaw Ulam, objetivando a simulação de auto-reprodução de organismos biológicos e o modelo de Jonh Horton Conway com o Jogo da Vida (Game of Life) [1]. O estudo dos Autômatos Celulares atraiu um grande interesse nos últimos anos, devido a sua capacidade de gerar um amplo espectro de padrões comportamentais complexos a partir de conjuntos relativamente simples de regras. Além disso, eles parecem capturar a essência de comportamentos auto-organizados complexos observados em sistemas naturais [2]. Autômatos Celulares são modelos matemáticos discretos no tempo, no espaço e nas variáveis dinâmicas, cuja evolução é regida por regras simples. Eles são formados por unidades simples que interagem entre si (uma unidade influencia o comportamento da outra) e, à medida que o sistema evolui dinamicamente, emergem comportamentos complexos decorrentes dessas influências mútuas, uma característica importante dos sistemas complexos [3]. O método dos Autômatos Celulares difundiu-se, devido a sua capacidade de gerar simulações, previsões e resultados não conseguidos, utilizando outros métodos que envolvem equações matemáticas, como por exemplo, as equações diferenciais. A simplicidade e facilidade de implementação desse recurso matemático-computacional têm influenciado várias áreas do conhecimento como a Física [4, 5, 6, 7], a Química [8], as Ciências Humanas [9] e principalmente na Matemática e na Biologia [2, 10, 11], visto que essas foram as áreas precursoras e motivadoras no desenvolvimento do estudo dos Autômatos Celulares. O presente trabalho apresenta, qualitativamente, o modelo teórico-abstrato da Máquina de Turing [12], mesmo sendo proposta/formalizada, cronologicamente, depois da Teoria dos Autômatos, realizando um preâmbulo para apresentação do conceito de autômato. Na seqüência, apresenta-se algumas definições de uma classe de autômatos: os Autômatos Celulares. O autômato celular foi originalmente descrito por Jonh Von Neumann e apresentado nos trabalhos publicados por Ulam [13] e buscava uma maneira, através de suas interações, de representar um comportamento evolutivo (vida/morte) nos sistemas biológicos. A seguir apresentamos diferentes implementações de Autômatos Celulares aplicados a diferentes áreas do conhecimento como na teoria dos fractais, simulação de incêndios florestais e o jogo da vida (Game of life).

2 MÁQUINA DE TURING

Nesta seção é apresentada a Máquina de Turing como uma introdução ao conceito de autômato. A teoria de autômatos é o estudo dos dispositivos de computação abstratos, ou ”máquinas”. Antes de existirem os computadores, na década de 1930, A. Turing estudou uma máquina abstrata que tinha todas as características dos computadores atuais, pelo menos no que se refere ao quanto eles poderiam calcular. O objetivo de Turing era descrever com exatidão o limite entre o que uma máquina de computação podia fazer e aquilo que ela não podia; suas conclusões se aplicam não apenas às suas máquinas de Turing abstratas, mas também às máquinas reais de hoje [12]. Essa máquina é universalmente conhecida e aceita como formalização de algoritmo [8]. Trata-se de um

GREMONINI, Lucas; VICENTINI, Eduardo

Revista Eletrônica Lato Sensu – UNICENTRO

Página 3 de 19

mecanismo simples que formaliza a idéia de uma pessoa que realiza cálculos. Possui, no mínimo, o mesmo poder computacional de qualquer computador de propósito

...