Autómato celular

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Um autómato (português europeu) ou autômato (português brasileiro) celular é um modelo discreto estudado na teoria da computabilidade, matemática, e biologia teórica. Consiste de uma grelha infinita e regular de células, cada uma podendo estar em um número finito de estados, que variam de acordo com regras determinísticas. A grelha pode ser em qualquer número finito de dimensões. O tempo também é discreto, e o estado de uma célula no tempo t é uma função do estado no tempo t-1 de um número finito de células na sua vizinhança. Essa vizinhança corresponde a uma determinada selecção de células próximas (podendo eventualmente incluir a própria célula). Todas as células evoluem segundo a mesma regra para actualização, baseada nos valores das suas células vizinhas. Cada vez que as regras são aplicadas à grelha completa, uma nova geração é produzida.

Os autómatos celulares foram introduzidos por von Neumann e Ulam como modelos para estudar processos de crescimento e auto-reprodução. Qualquer sistema com muitos elementos idênticos que interagem local e deterministicamente podem ser modelados usando autómatos celulares.

História[editar | editar código-fonte]

Nos anos 1940, Stanislaw Ulam estudou o crescimento dos cristais no Laboratório Nacional de Los Alamos, modelando-o usando uma grelha. Ao mesmo tempo, John von Neumann, colega de Ulam em Los Alamos, trabalhava em sistemas auto-replicativos e encontrava dificuldades para explicitar o seu modelo inicial de um robô que fosse capaz de se copiar sozinho a partir de um conjunto de peças separadas. Ulam sugeriu-lhe que inspirasse nos seus trabalhos, o que conduziu a von Neumann a conceber um modelo matemático abstracto para seu problema. O resultado foi o “copiador e constructor universal” (universal copier and constructor, em inglês), o primeiro autómato celular, baseado numa grelha com duas dimensões onde cada célula podia estar em um de 29 estados.

Em 1969, Konrad Zuse publicou o livro Rechnender Raum (“Calcular o espaço”) onde adiantou a hipótese de as leis físicas serem discretas e que o universo era o resultado de um gigantesco autómato celular.

Nos anos 1970, um autómato celular a duas dimensões e dois estados, chamado “o jogo da vida”, inventado por John Conway, conheceu um grande sucesso, particularmente entre a comunidade informática nascente. Foi popularizado por Martin Gardner num artigo da revista Scientific American.

Em 1983, Stephen Wolfram publicou a primeira de uma série das publicações onde analisou de uma maneira sistemática um tipo autómatos celulares muito simples. A complexidade do seu comportamento, induzida por régras elementares, levou-o a conjecturar que mecanismos similares poderiam esclarecer fenómenos físicos complexos, ideias que desenvolveu no seu livro A New Kind of Science, publicado em 2002.

No seu livro The Lifebox, The Seashell and The Soul, publicado 2005, o Dr. Rudy Rucker expandiu as teorias de Wolfram para uma teoria do Automatismo Universal, que usa os autómatos celulares como um modelo para explicar como regras simples podem gerar resultados complexos [1]. Segundo esta teoria, tudo que existe no universo (o tempo meteorológico, a forma das folhas das árvores ou dos continentes, o movimento das estrelas, os processos da mente, etc) tem por base algoritmos simples capazes de gerar a complexidade que vemos nos mundos da física, biologia, sociedade, cultura e até da psicologia.

Autómatos celulares unidimensionais[editar | editar código-fonte]

O autómato celular mais simples e não trivial é unidimensional, com dois estados possíveis por célula e sendo os vizinhos de uma célula as células adjacentes de cada lado dela. Uma célula e as suas duas vizinhas formam uma vizinhança de 3 células, por isso existem 2³=8 padrões possíveis para uma vizinhança. Há então 28=256 regras possíveis. Referem-se usualmente os autómatos pelo número decimal que, em binário, representa a tabela da regra. Por exemplo, a representação gráfica da evolução de um autómato com a regra 30 (em binário 11110) começando com um padrão de entrada inicial com apenas um 1 no centro é a seguinte:

CA rule30s.png

Autómato celular com Regra 30
padrão actual 111 110 101 100 011 010 001 000
novo estado para a célula central 0 0 0 1 1 1 1 0

Uma tabela define completamente uma regra de um autómato porque indica o que vai acontecer para cada um dos padrões possíveis para uma vizinhança. Por exemplo, a tabela da regra 30 diz que se três células adjacentes têm actualmente o padrão 100 (célula da esquerda a 1, com as outras a 0) ou 001 (célula da direita a 1, com as outras a 0) então a célula do meio tornar-se-a 1 na próxima iteração.

A regra 30 gera uma sequência aparentemente aleatória apesar da falta de qualquer coisa que poderia razoavelmente ser considerada uma entrada aleatória. Stephen Wolfram propôs usar a sua coluna central como um gerador de números pseudoalatórios (PRNG); de facto, passa muitos testes padrão para a aliatoriedade e Stephen Wolfram usa esta regra na seu programa Mathematica para criar inteiros aleatórios. (Embora a regra 30 produza aliatoriedade para muitos padrões da entrada inicial, há também um número infinito dos testes padrões da entrada inicial que resultam num ciclo repetitivo. O exemplo trivial é o padrão da entrada que consiste somente de zeros.)

Autómatos celulares bidimensionais[editar | editar código-fonte]

Animação do jogo da vida.

O autómato celular bidimensional mais conhecido é o jogo da vida, inventado pelo matemático britânico John Horton Conway em 1970.

O jogo da vida é um autómato celular que simula processos de evolução de células biológicas. Pode-se provar que é um autómato «computacionalmente universal», ou seja, potencialmente seria capaz de simular qualquer sistema possível.

As regras deste autómato são as seguintes:

- Uma célula sobrevive (continua com um valor 1) se tem 2 ou 3 vizinhos vivos (com um valor 1).

- Uma nova célula é criada num quadrado vazio (o seu valor passa de 0 a 1) se esse quadrado tem exactamente 3 vizinhos vivos.

O jogo da vida em si consiste em escolher uma configuração inicial de células vivas tais que elas acabem por sobreviver.

Autómatos celulares naturais[editar | editar código-fonte]

Conus textile apresentando um motivo parecido com o de certos autómatos celulares.

Os motivos de certas conchas são gerados como autómatos celulares naturais. As células responsáveis pela pigmentação estão situadas sobre uma banda estreita ao longo da boca da concha. Cada célula segrega pigmentos de acordo com a segregação (ou ausência de segregação) das suas vizinhas e o conjunto das células produz o motivo da concha à medida que ela cresce. Por exemplo, a espécie conus textile apresenta um motivo parecido com o de um autómato com regra 30.

Uso em criptografia[editar | editar código-fonte]

Algumas regras de evolução de um autómato celular finito (como a regra 30) foram sugeridas como uma cifra possível para uso em criptografia. Dada uma regra, qualquer um pode facilmente calcular os estados futuros, mas parece ser muito difícil calcular estados precedentes. No entanto, o desenhador da regra pode criá-la de tal maneira que seja fácil invertê-la. Consequentemente, será uma função que pode ser usada como chave pública criptográfica. A segurança de tais sistemas não é actualmente conhecida.

O Commons possui uma categoria contendo imagens e outros ficheiros sobre Autómato celular

Ligações externas[editar | editar código-fonte]