Nessa subunidade, começaremos com um pouco de história
e então falaremos mais sobre o mais simples autômato celular possível,
chamado "Autômato Celular Elementar"
A ideia de autômato celular foi inventada na década de 40 por 2 matemáticos,
Stanislaw Ulam e John von Neumann.
Você pode conhecer o nome de John von Neumann como um dos pioneiros da
ideia de computadores, e computadores programáveis em particular.
von Neumann era particularmente interessado em como construir máquinas
que pudessem ter propriedades biológicas ou realistas
Ele era especialmente interessado na ideia de auto-reprodução por máquinas,
que naquela época muitas pessoas pensavam ser impossível.
Pensando sobre isso, von Neumann discutiu o problema com seu colega, Ulam
que sugeriu que von Neumann olhasse para o problema usando a noção
de espaço celular, muito parecido com o autômato celular sobre o qual falamos e
falaremos nessa unidade.
Não entrarei em detalhes no trabalho de von Neumann, mas é bastante fascinante
e ele na verdade tem um livro inteiro sobre esse assunto
chamado "Teoria de Autômato Auto-Reprodutor",
que foi completado após a morte de von Neumann por Arthur Burkes. Esse livro é
mais técnico, mas é um marco na conexão entre o campo nascente da computação
e a biologia.
Antes de começar a falar sobre autômato celular elementar,
deixe-me apenas mencionar algumas das aplicações do autômato celular.
Existem várias aplicações em Ciências da Computação
Autômato celular é uma arquitetura de modelo para computação maciçamente
paralela e também para computação a escala molecular.
Em sistemas complexos, autômato celular tem sido amplamente usado como uma
ferramenta para modelar processos na Física, Geologia, Química,
e assim por diante, entre muitas, muitas disciplinas.
É também usado como ferramenta para estudo de noções abstratas de auto-organização
e computação emergente em sistemas complexos.
E é nisso que estaremos focando nessa unidade
E eu apontaria que é importante para as pessoas que estudam sistemas complexos
saberem alguma coisa sobre autômato celular,
porque eles estão entre as ferramentas mais comuns de modelagem nessa área.
Vamos falar sobre o mais simples tipo de autômato celular,
que é chamado "autômato celular elementar"
Esses são unidimensionais. Perceba que o Jogo da Vida era bidimensional.
Nós tínhamos uma grade bidimensional.
Mas aqui nós temos só uma linha de células e somente dois estados, como no
Jogo da Vida. Células são ou pretas ou brancas
e cada célula olha para
o seu vizinho mais próximo
em sua linha. Então, a vizinhança
dessa célula branca é ela mesma e
essas duas células pretas, e assim por diante.
E aqui o todo pode ser circular,
onde a vizinhança dessa
célula preta do lado esquerdo é
a célula branca mais à direita e
sua vizinha do lado direito.
O todo se junta
como um círculo. Eu listei aqui
todas as possíveis vizinhanças
em que uma célula pode se encontrar.
E você mesmo pode verificar
que não existem quaisquer outras possibilidades.
Agora, para especificar
o autômato celular, nós temos que
especificar em que cada célula central
se transformará, dependendo de sua vizinhança.
Então essa tabela completa aqui é chamada uma "regra"
para o autômato celular, e isso diz que,
por exemplo, se uma célula é branca e tem
dois vizinhos brancos, ela se torna branca.
Se uma célula é branca e tem um vizinho branco à esquerda e
um vizinho preto à direita, ela se torna preta.
E assim por diante. Então aqui, nós temos que especificar
cada vizinhança possível e seu estado de atualização.
E essa é apenas uma forma particular de especificar
o estado de atualização para a célula central.
Vamos ver como funciona.
Toda célula olha para sua vizinhança a cada
passo do tempo e atualiza, e todas as células
atualizam simultaneamente.
Então vamos fazer isso.
Esse aqui de cima é o passo de tempo zero.
Aqui está o próximo passo de tempo onde, por exemplo,
nós temos preto, branco, preto. Essa célula olhou
na tabela -- preto, branco, preto -- e disse que tinha que
se tornar preta no próximo passo de tempo.
E você pode verificar que as outras células seguem
suas regras da mesma forma. Ok, então agora podemos
fazer a mesma coisa para o próximo passo de tempo,
e de novo, e de novo, e assim por diante.
Então adivinhe! É hora de um quiz!
O quiz dá a você uma regra, a mesma regra
que estávamos olhando antes, e diz:
"após o passo de tempo 3, desse estado da "grade",
o que será a grade no passo do tempo 4?"