𝖂𝖎ƙ𝖎𝖊

Autómato celular


Os autómatos celulares elementares são os modelos de evolução temporal mais simples com capacidade para exibir comportamento complicado. Por isso, é muito fácil de aceitar a importância do seu estudo, quando se procura entender a complexidade que vemos surgir de uma forma transversal em todas as Ciências Naturais e Humanas. A classificação dos autómatos celulares elementares, apresentada por Stephen Wolfram, na década de 1980, foi construída a partir da simulação computacional de sistemas finitos, com condições de fronteira periódicas. Neste trabalho são consideradas outras escolhas para condições de fronteira, por reflexão e fixas, sendo estudadas as equivalências dinâmicas dos autómatos celulares finitos nesse contexto mais alargado. A partir desse estudo, mostramos que, com pouquíssimas exceções, a distribuição dos autómatos celulares elementares pelas quatro classes propostas por Wolfram vale igualmente quando se consideram condições de fronteira por reflexão e fixas. Mais interessante porém, foram os resultados obtidos no estudo de duas dessas exceções, onde se encontrou um tipo de comportamento para autómatos celulares elementares de caraterísticas não antecipadas por Wolfram na sua classificação.

História

Nos anos 1940, Stanisław 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

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 pseudoaleatórios (PRNG); de facto, passa muitos testes padrão para a aleatoriedade e Stephen Wolfram usa esta regra na seu programa Mathematica para criar inteiros aleatórios. (Embora a regra 30 produza aleatoriedade 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

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 exatamente 3 vizinhos vivos.

-Uma célula com 4 vizinhos vivos ou mais, acaba por morrer por excesso de população.

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

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

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 com imagens e outros ficheiros sobre Autómato celular

Ligações externas

talvez você goste

Permaneça conectado

Parceiros

Dieta Cetogenica | NutriPro Saúde