frame|direita|Glider Gun de Gosper criando "planadores" no autômato celular Conway's Game of LifeDaniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ,
Um 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. 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) 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, 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.
Bibliografia
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).
von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
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)
Ligações externas