Autômato celular de von Neumann

Um autômato Celular de von Neumann é um Autómato celular (AC) que teve seu desenvolvimento como consequência de sugestões feitas a John von Neumann por seu grande amigo e companheiro matemático Stanislaw Ulam. A sua finalidade original era fornecer informações sobre os requisitos lógicos de uma Máquina autorreplicadora, e foi usado no construtor universal de Von Neumann.

O autômato celular de Nobili é uma variação do autômato celular de von Neumann, incrementado com a habilidade das células confluentes de cruzar sinais e armazenar informação. Para tanto, é necessário o acréscimo de três estados, por isso o autômato celular de Nobili possui 32 estados (em vez dos 29 do autômato celular de Von Neumann). O autômato celular de Hutton é ainda outra variação, que permite um laço de dados, de forma semelhante aos laços de Langton, para replicação.

Outro AC relacionado é o autômato celular de Codd, que foi feito para recriar o cálculo do construtor universal de von Neumann, mas com menos estados: 8 em vez de 29.

Definição editar

Configuração editar

Em geral, um autômato celular (CA) é constituído por um arranjo de máquinas de estados finitos (FSM- do inglês Finite State Machine) que estão dispostas de forma a manter relações entre umas e outras, cada FSM combina sua informação com outras imediatamente adjacentes a ela. No autômato celular de von Neumann, as máquinas de estados finitos (ou células) estão dispostas em uma Grade Cartesiana de duas dimensões, e interage com as quatro células vizinhas. Como o autômato celular de von Neumann foi o primeiro exemplo de uso deste arranjo, ele é conhecido como Vizinhança de von Neumann.

O conjunto de FSMs definem um espaço celular de tamanho infinito. Todas as FSMs são idênticas em termos de estados e funções de transição.

A vizinhança (uma função de grupo) é parte da função de transição de estados, e define para qualquer célula o conjunto de outras células dais quais o estado da célula depende.

Todas as transições de estado das células ocorrem simultaneamente, de acordo com um "clock" universal como nos circuitos digitais síncronos.

Estados editar

Cada FSM do espaço de células de von Neumann pode alcançar qualquer um dos 29 estados do modelo. O modelo pode ser dividido em cinco subconjuntos próprios. (cada estado inclui a cor da célula no programa de visualização de autômatos celulares Golly no formato (RGB)) Eles são:

Um estado vazio U (48, 48, 48)
Os estados de transição ou sensibilizados (em 8 sub-estados)
1. S - (recém sensibilizados) (255, 0, 0)
2. S₀ - (sensibilizados, não receberam estímulo por um ciclo) (255, 125, 0)
3. S₀₀ - (sensibilizados, não receberam estímulo por dois ciclos) (255, 175, 50)
4. S₀₀₀ - (sensibilizados, não receberam estímulo por três ciclos) (251, 255, 0)
5. S₀₁ - (sensibilizados, não receberam estímulo por um ciclo e depois receberam um estímulo por um ciclo) (255, 200, 75)
6. S₁ - (sensibilizados, receberam estímulo por um ciclo) (255, 150, 25)
7. S₁₀ - (sensibilizados, receberam estímulo por um ciclo e depois não receberam estímulo por um ciclo) (255, 255, 100)
8. S₁₁ - (sensibilizados, receberam estímulo for dois ciclos) (255, 250, 125)
Os estados confluentes (em 4 estados de excitação)
1. C₀₀ - quiescentes (e continuarão quiescentes no próximo ciclo) (0, 255, 128)
2. C₀₁ - prestes a estarem excitados (agora quiescentes, mas estarão excitados no próximo ciclo) (33, 215, 215)
3. C₁₀ - excitados (mas estarão quiescentes no próximo ciclo) (255, 255, 128)
4. C₁₁ - excitados e prestes a estarem excitados (estão excitados agora e continuarão excitados no próximo ciclo) (255, 128, 64)
Os estados de transmissão comum (em quatro direções, excitados ou quiescentes, totalizando 8 estados)
1. Norte (excitados e quiescentes) (36, 200, 36) (106, 106, 255)
2. Sul (excitados e quiescentes) (106, 255, 106) (139, 139, 255)
3. Oeste (excitados e quiescentes) (73, 255, 73) (122, 122, 255)
4. Leste (excitados e quiescentes) (27, 176, 27) (89, 89, 255)
Os estados de transmissão especial (em quatro direções, excitados ou quiescentes, totalizando 8 estados)
1. Norte (excitados e quiescentes) (191, 73, 255) (255, 56, 56)
2. Sul (excitados e quiescentes) (203, 106, 255) (255, 89, 89)
3. Oeste (excitados e quiescentes) (197, 89, 255) (255, 73, 73)
4. Leste (excitados e quiescentes) (185, 56, 255) (235, 36, 36)

Estados "Excitados" transportam dados, em uma frequência de um bit por troca de estado.

Note que estados confluentes possuem a propriedade de atraso em um ciclo, logo eles retêm efetivamente dois bits de dados em qualquer momento.

Regras dos estados de transmissão editar

O fluxo de bits entre células é indicado pela direção das células transmissoras. Para isso, são aplicadas as seguintes regras:

Estados de transmissão aplicam o operador OU em suas entradas de estímulo (vizinhos), o que significa que uma célula num estado de transmissão (comum ou especial) estará excitada no tempo t+1 se algum de seus vizinhos está apontando para ela e está excitado no tempo t
Dados passam de uma célula A em um estado de transmissão comum para uma célula adjacente B também em um estado de transmissão comum, de acordo com a direção de A (a menos que B esteja direcionada para A).
Dados passam de uma célula A em um estado de transmissão especial para uma célula adjacente B também em um estado de transmissão especial, de acordo com as mesmas regras que valem para estados de transmissão comum.
Os dois subconjuntos de estados de transmissão, comum e especiais, são mutuamente antagonistas:
- Dado uma célula A no tempo t no estado de transmissão comum excitada
- apontando para uma célula B em algum estado de transmissão especial
- no tempo t+1 a célula B irá para o estado vazio(U). A célula de transmissão especial foi "destruída".
- uma sequência similar ocorrerá no caso de uma célula num estado de transmissão especial "apontar" para uma célula num estado de transmissão comum.

Regras dos estados de confluência editar

As seguintes regras específicas se aplicam aos estados confluentes:

Estados confluentes não transportam dados entre si.
Estados confluentes recebem estímulos de entrada de um ou mais estados de transmissão comum, e devolvem estímulos à estados de transmissão, comum e especiais, que não estão voltados contra ele.
Dados não são transmitidos entre dois estados de transmissão direcionados um contra o outro.
Dados retidos por um estado confluente se perderão se não houver estados de transmissão adjacentes que não estejam voltados contra ele.
Dessa forma, células em estados confluentes são usadas como "pontes" entre linhas de células em estado de transmissão comum, para células em estado de transmissão especial.
O estado confluente aplica o operador E às entradas, ou seja: só "salva" um estímulo de entrada excitado se todas as potenciais entradas estão excitadas simultaneamente.
Células confluentes atrasam o sinal em uma geração à mais que células em estado de transmissão comum; isto ocorre devido às restrições de paridade.

Regras de construção editar

Os nove tipos de células que podem ser construídas no AC de von Neumann. Aqui, sinais binários passam ao longo de nove linhas de transmissão comum, construindo uma nova célula quando eles encontram uma célula no estado vazio U no fim. Por exemplo, a cadeia binária 1011 é demonstrada na quinta linha, e constrói uma célula no estado de transmissão especial Leste - este é o mesmo processo usado no autômato no topo desta página. Note que não há interação entre vizinhos no fio, diferente do que acontece por exemplo no wireworld.

Inicialmente, a maior parte do espaço de células -o universo do autômato celular- está em branco. Consistindo de células no estado vazio U. Quando dado um estímulo de entrada de um vizinho em estado de transmissão comum -ou especial, a célula no estado vazio se tornará "sensibilizada", transmutando por uma série de estados antes de finalmente "repousar" em um estado de transmissão ou confluência.

A escolha do estado final no qual a célula ficará é determinada pela sequência dos sinais/estímulos de entrada. Dessa forma, podemos visualizar os estados de transição/sensibilizados como sendo os nós de uma árvore: a raiz seria o estado U e as folhas seriam cada um dos estados quiescentes, tanto de transmissão quanto de confluência.

Na árvore seguinte, a sequência de estímulos é mostrada como uma cadeia binária após cada passo:

uma célula no estado vazio U, recebendo um estímulo, transmutará para o estado S (recém sensibilizado) no próximo ciclo (1)
uma célula no estado S, não recebendo um estímulo, transmutará para o estado S₀ (10)
- uma célula no estado S₀, não recebendo um estímulo, transmutará para o estado S₀₀ (100)
  - uma célula no estado S₀₀, não recebendo um estímulo, transmutará para o estado S₀₀₀ (1000)
    - uma célula no estado S₀₀₀, não recebendo um estímulo, transmutará para o estado de transmissão comum Leste (10000)
    - uma célula no estado S₀₀₀, recebendo um estímulo, transmutará para o estado de transmissão comum Norte (10001)
  - uma célula no estado S₀₀, recebendo um estímulo, transmutará para o estado de transmissão comum Oeste (1001)
- uma célula no estado S₀, recebendo um estímulo, transmutará para o estado S₀₁ (101)
  - uma célula no estado S₀₁, não recebendo um estímulo, transmutará para o estado de transmissão comum Sul (1010)
  - uma célula no estado S₀₁, recebendo um estímulo, transmutará para o estado de transmissão especial Leste (1011)
uma célula no estado S, recebendo um estímulo, transmutará para o estado S₁ (11)
- uma célula no estado S₁, não recebendo um estímulo, transmutará para o estado S₁₀ (110)
  - uma célula no estado S₁₀, não recebendo um estímulo, transmutará para o estado de transmissão especial Norte (1100)
  - uma célula no estado S₁₀, recebendo um estímulo, transmutará para o estado de transmissão especial Oeste (1101)
- uma célula no estado S₁, recebendo um estímulo, transmutará para o estado S₁₁ (111)
  - uma célula no estado S₁₁, não recebendo um estímulo, transmutará para o estado de transmissão especial Sul (1110)
  - uma célula no estado S₁₁, recebendo um estímulo, transmutará para o estado quiescente de confluência C₀₀ (1111)

Note que:

É necessário um ciclo de estímulo a mais (quatro após o estímulo inicial) para construir os estados de transmissão comum Norte e Leste, diferente de qualquer outro estado (que requer apenas três ciclos de estímulos após o inicial),
O estado final "padrão" da construção é o estado de transmissão comum Leste -o qual requer apenas o estímulo inicial, e depois quatro ciclos sem estímulos.

Regras de destruição editar

Cerca de 4000 bits de dados em uma "fita retorcida" construindo um padrão complexo. Está sendo usado uma variação do autômato celular de von Neumann: o Hutton32.

Um estímulo em uma célula num estado confluente proveniente de uma célula num estado de transmissão especial resultará na célula confluente sendo reduzida ao estado vazio U.
Da mesma forma, um estímulo em uma célula num estado de transmissão comum proveniente de uma célula num estado de transmissão especial resultará na célula transmissora comum sendo reduzida ao estado vazio U.
Reciprocamente, um estímulo em uma célula num estado de transmissão especial proveniente de uma célula num estado de transmissão comum resultará na célula transmissora especial sendo reduzida ao estado vazio U.

Ver também editar

Referências editar

Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana, University of Illinois Press. [1]

Ligações externas editar

Golly - Implementa o AC de von Neumann, o conhecido Jogo da vida de Conway além de outras regras de AC.