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. 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

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.