PROFILPELAJAR.COM

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

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.

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

↑ Daniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X
↑ 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
↑ Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling. [S.l.]: MIT Press. p. 27. ISBN 9780262200608
↑ 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)
«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»