Autómato celular

Um autómato ^{(português europeu)} ou autômato ^{(português brasileiro)} celular (AC) é um modelo discreto de computação estudado na teoria dos autômatos. Autômatos celulares também são chamados de espaços celulares, autômatos de mosaico, estruturas homogêneas, estruturas celulares, estruturas de mosaico e arranjos iterativos.^[2] Autômatos celulares encontraram aplicação em várias áreas, incluindo física, biologia teórica e modelagem de microestrutura.

Glider Gun de Gosper criando "planadores" no autômato celular Conway's Game of Life^[1]

Um autômato celular consiste em uma grade regular de células, cada uma em um número finito de estados, como ligado e desligado (em contraste com uma rede de mapa acoplado). A grade pode estar em qualquer número finito de dimensões. Para cada célula, um conjunto de células chamado vizinhança é definido em relação à célula especificada. Um estado inicial (tempo t = 0) é selecionado atribuindo um estado para cada célula. Uma nova geração é criada (avançando t em 1), de acordo com alguma regra fixa (geralmente, uma função matemática)^[3] que determina o novo estado de cada célula em termos do estado atual da célula e dos estados das células em sua vizinhança. Normalmente, a regra para atualizar o estado das células é a mesma para cada célula e não muda ao longo do tempo, e é aplicada a toda a grade simultaneamente,^[4] embora sejam conhecidas exceções, como o autômato celular estocástico e o autômato celular assíncrono.

O conceito foi originalmente descoberto na década de 1940 por Stanislaw Ulam e John von Neumann enquanto eles eram contemporâneos no Laboratório Nacional de Los Alamos. Embora estudado por alguns ao longo das décadas de 1950 e 1960, não foi até a década de 1970 e Conway's Game of Life, um autômato celular bidimensional, que o interesse no assunto se expandiu para além da academia. Na década de 1980, Stephen Wolfram se envolveu em um estudo sistemático de autômatos celulares unidimensionais, ou o que ele chama de autômatos celulares elementares; seu assistente de pesquisa Matthew Cook mostrou que uma dessas regras é Turing-completo.

As classificações primárias de autômatos celulares, conforme descrito por Wolfram, são numeradas de um a quatro. Eles são, em ordem, autômatos nos quais os padrões geralmente se estabilizam em homogeneidade, autômatos nos quais os padrões evoluem para estruturas principalmente estáveis ​​ou oscilantes, autômatos nos quais os padrões evoluem de maneira aparentemente caótica e autômatos nos quais os padrões se tornam extremamente complexos e podem durar por muito tempo, com estruturas locais estáveis. Esta última classe é considerada computacionalmente universal, ou capaz de simular uma máquina de Turing. Tipos especiais de autômatos celulares são reversíveis, onde apenas uma única configuração leva diretamente a uma subsequente, e totalísticas, em que o valor futuro de células individuais depende apenas do valor total de um grupo de células vizinhas. Autômatos celulares podem simular uma variedade de sistemas do mundo real, incluindo biológicos e químicos.

Referências

1. Daniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X
2. Wolfram, Stephen (1983). «Statistical Mechanics of Cellular Automata». Reviews of Modern Physics. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601. Consultado em 28 de fevereiro de 2011. Arquivado do original em 21 de setembro de 2013
3. Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling. [S.l.]: MIT Press. p. 27. ISBN 9780262200608
4. Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. [S.l.]: Wiley & Sons, Inc. p. 40. ISBN 9781118030639

Bibliografia

• Adamatzky, Andrew, ed. (2010). Game of Life Cellular Automata. [S.l.]: Springer. ISBN 978-1-84996-216-2
  • Wainwright, Robert. "Conway's game of life: early personal recollections". Em Adamatzky (2010).
  • Eppstein, David. "Growth and decay in life-like celular autometa". Em Adamatzky (2010).
• Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. [S.l.]: Oxford University Press. ISBN 978-0198531005
• Chopard, Bastien; Droz, Michel (2005). Cellular Automata Modeling of Physical Systems. [S.l.]: Cambridge University Press. ISBN 978-0-521-46168-9
• Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. [S.l.]: MIT Press. ISBN 9780262570862
• Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. [S.l.]: World Scientific. ISBN 9789812381835
• Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. [S.l.]: Springer. ISBN 9781402036576
• Kroc, Jiří; Jiménez-Morales, Francisco; Guisado, José Luis; Lemos, María Carmen; Tkáč, Jakub (dezembro de 2019). «Building Efficient Computational Cellular Automata Models of Complex Systems: Background, Applications, Results, Software, and Pathologies». Advances in Complex Systems. 22 (5): 1950013 (38 pages). doi:10.1142/S0219525919500139
• Wolfram, Stephen (2002). A New Kind of Science. [S.l.]: Wolfram Media. ISBN 978-1579550080
• «Cellular automaton FAQ». from the newsgroup comp.theory.cell-automata
• «"Neighbourhood Survey"». (includes discussion on triangular grids, and larger neighborhood CAs)
• von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
• «Cosma Shalizi's Cellular Automata Notebook». contains an extensive list of academic and professional reference material.
• «Wolfram's papers on CAs». Arquivado em 27 setembro 2013 no Wayback Machine
• A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237, pp. 37–72. (proposes reaction-diffusion, a type of continuous automaton).
• Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
• The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
• The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
• «Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata"»

Ligações externas

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

Wikilivros

O Wikilivros tem um livro chamado Cellular Automata

• Berto, Francesco; Tagliabue, Jacopo (26 de março de 2012). «Cellular Automata». Stanford Encyclopedia of Philosophy (em inglês) !CS1 manut: Nomes múltiplos: lista de autores (link)
• «Mirek's Cellebration». – Lar do software gratuito de explorador de autômatos celulares MCell e MJCell e bibliotecas de regras. O software suporta um grande número de regras 1D e 2D. O site fornece um extenso léxico de regras e muitas galerias de imagens carregadas de exemplos de regras. O MCell é um aplicativo do Windows, enquanto o MJCell é um applet Java. O código-fonte está disponível.
• «Modern Cellular Automata». – Exposições interativas fáceis de usar de autômatos celulares 2D em cores vivas, com tecnologia Java applet. Estão incluídas exibições de regras tradicionais, reversíveis, hexagonais, de múltiplas etapas, geração fractal e geração de padrões. Milhares de regras são fornecidas para visualização. O software livre está disponível.
• «Loops de auto-replicação no espaço celular». – exibições de loops de auto-replicação alimentadas por miniaplicativos Java.
• «Uma coleção de mais de dez applets de autômatos celulares diferentes». (no Laboratório Virtual da Monash University)
• «Golly». suporta von Neumann, Nobili, GOL e muitos outros sistemas de autômatos celulares. Desenvolvido por Tomas Rokicki e Andrew Trevorrow. Este é o único simulador atualmente disponível que pode demonstrar a autorreplicação do tipo von Neumann.
• «Fourier Life». - Uma coleção de regras que demonstram padrões auto-replicantes que emergem espontaneamente de um campo de células aleatórias. A maioria das regras foi encontrada usando um algoritmo que usa uma transformada de Fourier para detectar a autorreplicação.
• «Wolfram Atlas». – Um atlas de vários tipos de autômatos celulares unidimensionais.
• «Conway Life»
• «Primeira criatura replicante gerada no simulador de vida»
• «The Mathematics of the Models of Reference». , apresentando um tutorial geral sobre AC, applet interativo, código livre e recursos sobre AC como modelo de física fundamental
• «Fourmilab Cellular Automata Laboratory»
• «Busy Boxes». , um AC de arquitetura SALT SALT 3-D reversível
• «Cellular Automata Repository». (pesquisadores de AC, ligações históricas, software livre, livros e muito mais)
• «Autômatos celulares em 256 regras». (visualização interativa de uma única folha de 256 regras elementares)
• «Petri -- uma estrutura de autômatos celulares Go»

• Portal da biologia