Saltar para o conteúdo

Autómato celular

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Autômato celular)
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

  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 

Ligações externas

[editar | editar código-fonte]
O Commons possui uma categoria com imagens e outros ficheiros sobre Autómato celular
Wikilivros
Wikilivros
O Wikilivros tem um livro chamado Cellular Automata