Estudar Autômatos Celulares como computadores
é um grande assunto, digno de um curso
próprio dele.
Aqui eu vou dar uma visão geral rápida
mas eu coloquei algumas leituras
na seção de leituras opcionais
da página do curso para você
estudar esse tópico.
Vamos primeiro falar sobre o que
nós queremos dizer por computação.
Computação é o processamento de informação.
Em uma computação,
informação é uma entrada do sistema,
ela está armazenada na memória de alguma forma,
ela é transferida de
uma parte da memória para outra,
e é combinada com outra informação
e essa também pode ser dita processada.
Finalmente, a informação processada
é a saída para o usuário
ou para o sistema todo para usar de alguma forma.
Um pequeno esboço: nós temos entrada,
e então um programa que realiza
a computação, e então a saída.
Alguma vezes, por exemplo,
em um sistema dinâmico,
a saída voltaria
e se tornaria a entrada.
Existe uma noção que é muito importante
no campo das ciências da computação
e no campo dos sistemas complexos
que é a noção da computação universal.
Basicamente, computação universal
é o fenômeno de
um computador ser capaz de ser programado.
Ou seja, um computador universal
é um computador que pode rodar qualquer programa.
Então é como o computador na sua mesa,
se ele tivesse uma quantidade infinita de memória,
então ele poderia executar qualquer programa possível
e computar qualquer função possível
que fosse computável.
Então a ideia aqui é ao invés de apenas uma entrada,
nós temos uma entrada e um programa.
Isso entra em um computador universal
e o resultado é uma saída.
Você pode pensar nisso como se no computador
na sua mesa, onde você pode colocar seus dados,
existisse um programa que foi colocado
ou por você ou por alguma outra pessoa,
que está na memória do seu computador.
Seu computador age como um computador universal
e roda aquele programa com aquela entrada,
e então cria a saída.
Um dos triunfos
da área das ciências da computação
foi a descoberta de que
somente um pequeno conjunto de operações lógicas
é necessária para suportar computações universais.
Por suportar computação universal,
eu quero dizer ser capaz de construir
um computador programável.
O que isso significa é que se você pode implementar
um conjunto particular de operações lógicas,
usá-las e combiná-las de diferentes formas
você será capaz, em princípio, de ter
um computador que possa rodar
qualquer programa sobre qualquer entrada,
Isso é um computador universal.
Como mencionado anteriormente,
John Von Nuemann foi um dos primeiros
cientistas a olhar para autômato celular
como modelos de sistemas complexos
e em particular
ele estava olhando para a ideia de
auto-reprodução em máquinas ou autômatos.
Ele construiu um autômato celular,
um de duas dimensões.
Cada célula poderia estar em um de 29 estados,
e esse autômato celular
poderia replicar qualquer padrão
que fosse entrada para isso, inclusive ele mesmo.
Essa é uma figura esquemática
desse tipo de auto-reprodução,
aqui é uma máquina complicada.
Ela tem um espaço de entrada, espaço de saída,
e cria uma cópia de si mesma,
ou qualquer outro padrão que você dê a ela.
Mas Von Nuemann também fez disso
um computador universal.
Ou seja, isso pode não só se auto-reproduzir,
como pode computar qualquer função computável.
Muitas pessoas simplificaram o autômato
auto-reprodutor de Von Neumann
para ter menos estados, mas essa foi
a primeira criação de um computador universal
dentro de um autômato celular.
O Jogo da Vida também foi mostrado
suportar computação universal.
Em 1970, John Conway mostrou que Vida
pode implementar operações lógicas simples
que são necessárias em princípio
para computação universal.
Ele também esboçou como
um computador universal pode ser construído.
Então, nos anos 90, Paul Rendell
construiu o computador universal.
Aqui está uma figura de parte
do computador universal que ele construiu.
Um pouco difícil de ver,
mas ele usa algumas dessas estruturas
que nós vimos anteriormente,
tais como gliders, armas de gliders, e assim por diante,
para implementar essas operações lógicas
necessárias para computação universal.
Eu preciso dizer que isso é
uma tarefa fantasticamente complicada
de fato implementar esse tipo
de computação em um autômato celular.
Por um longo tempo, Stephen Wolfram suspeitou
que alguns autômatos celulares elementares
poderiam suportar computação universal
Isso seria significante
naqueles autômatos celulares elementares,
se você se lembra, são extremamente simples
e a pergunta era: poderia
o comportamento complexo que eles criaram
ser complexo o suficiente
para implementar essa forma mais poderosa
de processamento de informação?
Bem, a hipótese de Wolfram era
de que todos os autômatos celulares de classe 4
pudessem suportar computação universal.
Lembre-se, classe 4 eram aqueles
entre periódico e caótico,
aqueles autômatos celulares no Limite do Caos.
Essa hipótese é difícil de avaliar.
Bem, um problema é que
que não existe realmente
uma definição formal da classe 4
de autômatos celulares.
Também, parece muito difícil
de fato provar que algum sistema
é capaz de computação universal.
Entretanto, Wolfram e seu colega,
Matthew Cook, tiveram sucesso
em provar que a Regra 110
pode suportar computação universal
Essa prova foi descrita em um longo capítulo
do livro do Wolfram, A New Kind of Science.
Você na verdade pode lê-lo de graça online.
Eu coloquei um link em nossa página de materiais do curso.
É uma prova mais técnica, mas
a ideia geral é que a Regra 110
suporta essas chamadas partículas em movimento,
ou seja, essas estruturas localizadas
que se movem no espaço e no tempo.
Lembre-se, o tempo vai para baixo na vertical,
e o espaço segue na horizontal
em uma dimensão,
e então, essas particulas em movimento
podem integrar informação
de localidades espaciais diferentes
e colidirem com uma outra.
Então, por exemplo, nós vemos aqui
essa partícula colidindo com essa partícula
e criando uma nova partícula.
A ideia é que informação pode ser armazenada
nesses mais regulares padrões,
transferidas via essas partículas,
e processadas via a colisão das partículas
Em princípio, essas podem suportar
uma computação universal
Na prática, entretanto, é difícil
se não impossível de fato programar
esses autômatos celulares para fazer
qualquer tarefa útil.
Bem, computação universal
em autômatos celulares é muito interessante,
e até mesmo surpreendente, dada a simplicidade
deles, especialmente dos ACs elementares.
Não é uma forma muito prática
de realizar computação.
É muito lento simular
um computador universal
em um autômato celular
É também difícil de programar.
Então ninguém realmente faz computações
para qualquer finaliade prática
usando habilidades de computação
universal de autômatos celulares.
Entretanto, ACs foram explorados
para computações paralelas mais práticas.
Por exemplo, no campo do processamento de imagem.
Eu não vou falar muito sobre isso aqui,
mas na próxima subunidade
eu vou falar sobre
um projeto em particular
em que algoritmos genéticos
foram usados para evoluir autômatos celulares
para realizar computações práticas.
Finalmente, deixe-me apenas dizer algumas palavras sobre a significância
de autômatos celulares para sisemas complexos
Bem, você viu que autômatos celulares
são sistemas complexes altamente idealizados
que podem produzir comportamento muito complexo
a partir de regras simples
Você viu que sistemas complexos naturais
podem ser modelados usando autômatos celulares
como arquiteturas,
e que autômatos celulares
dão uma estrutura para compreensão
de como dinâmicas complexas podem produzir
processamento de informação coletiva, ou seja,
processamento de informação que emerge
de uma coleção de componentes simples
em um sistema realista.
Onde realista quer dizer componentes
decentralizados, relativamente simples,
comunicação limitada
entre componentes, e assim por diante.