Autômato celular de Von Neumann - Von Neumann cellular automaton

Uma configuração simples no autômato celular de von Neumann. Um sinal binário é passado repetidamente ao redor do loop do fio azul, usando estados de transmissão comuns excitados e quiescentes . Uma célula confluente duplica o sinal em um fio vermelho que consiste em estados de transmissão especiais . O sinal passa por esse fio e constrói uma nova célula no final. Este sinal particular (1011) codifica um estado de transmissão especial direcionado para o leste, estendendo assim o fio vermelho em uma célula de cada vez. Durante a construção, a nova célula passa por vários estados sensibilizados, dirigidos pela seqüência binária.

Os autômatos celulares de Von Neumann são a expressão original dos autômatos celulares , cujo desenvolvimento foi impulsionado por sugestões feitas a John von Neumann por seu amigo íntimo e colega matemático Stanislaw Ulam . Seu propósito original era fornecer informações sobre os requisitos lógicos para a auto-replicação da máquina , e eles foram usados ​​no construtor universal de von Neumann .

O autômato celular de Nobili é uma variação do autômato celular de von Neumann, ampliado com a capacidade das células confluentes de cruzar sinais e armazenar informações. O primeiro requer três estados extras, portanto, o autômato celular de Nobili tem 32 estados, em vez de 29. O autômato celular de Hutton é outra variação, que permite que um loop de dados, análogo aos loops de Langton , se replique.

Definição

Configuração

Em geral, autômatos celulares (CA) constituem um arranjo de autômatos de estado finito (FSA) que se assentam em relações posicionais entre si, cada FSA trocando informações com aqueles outros FSAs aos quais é posicionalmente adjacente. No autômato celular de von Neumann, as máquinas de estado finito (ou células ) são organizadas em uma grade cartesiana bidimensional e fazem interface com as quatro células circundantes. Como o autômato celular de von Neumann foi o primeiro exemplo a usar esse arranjo, ele é conhecido como vizinhança de von Neumann .

O conjunto de FSAs define um espaço celular de tamanho infinito. Todos os FSAs são idênticos em termos de função de transição de estado ou conjunto de regras.

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

Todas as células fazem suas transições de maneira síncrona, em sintonia com um "relógio" universal, como em um circuito digital síncrono.

Estados

Cada FSA do espaço celular de von Neumann pode aceitar qualquer um dos 29 estados do conjunto de regras. O conjunto de regras é agrupado em cinco subconjuntos ortogonais. Cada estado inclui a cor da célula no programa de autômatos celulares Golly em (vermelho, verde, azul). Eles são

  1. um estado fundamental U   (48, 48, 48)
  2. os estados de transição ou sensibilizados (em 8 subestados)
    1. S (recentemente sensibilizado)  (255, 0, 0)
    2. S 0 - (sensibilizado, não tendo recebido nenhuma entrada por um ciclo)  (255, 125, 0)
    3. S 00 - (sensibilizado, não tendo recebido nenhuma entrada por dois ciclos)  (255, 175, 50)
    4. S 000 - (sensibilizado, sem receber entrada por três ciclos)  (251, 255, 0)
    5. S 01 - (sensibilizado, não tendo recebido nenhuma entrada para um ciclo e, em seguida, uma entrada para um ciclo)  (255, 200, 75)
    6. S 1 - (sensibilizado, tendo recebido uma entrada para um ciclo)  (255, 150, 25)
    7. S 10 - (sensibilizado, tendo recebido uma entrada para um ciclo e, em seguida, nenhuma entrada para um ciclo)  (255, 255, 100)
    8. S 11 - (sensibilizado, tendo recebido entrada por dois ciclos)  (255, 250, 125)
  3. os estados confluentes (em 4 estados de excitação)
    1. C 00 - quiescente (e também estará quiescente no próximo ciclo)  (0, 255, 128)
    2. C 01 - próximo excitado (agora quiescente, mas será excitado no próximo ciclo)  (33, 215, 215)
    3. C 10 - animado (mas estará quiescente no próximo ciclo)  (255, 255, 128)
    4. C 11 - animado próximo - animado (atualmente animado e será animado no próximo ciclo)  (255, 128, 64)
  4. os estados de transmissão comuns (em 4 direções, excitado ou quiescente, perfazendo 8 estados)
    1. Orientado para o norte (animado e quiescente)   (36, 200, 36)   (106, 106, 255)
    2. Direcionado para o sul (animado e quiescente)   (106, 255, 106)   (139, 139, 255)
    3. Dirigido para o oeste (animado e quiescente)   (73, 255, 73)   (122, 122, 255)
    4. Orientado para o leste (animado e quiescente)   (27, 176, 27)   (89, 89, 255)
  5. os estados de transmissão especiais (em 4 direções, excitado ou quiescente, perfazendo 8 estados)
    1. Orientado para o norte (animado e quiescente)   (191, 73, 255)   (255, 56, 56)
    2. Direcionado para o sul (animado e quiescente)   (203, 106, 255)   (255, 89, 89)
    3. Dirigido para o oeste (animado e quiescente)   (197, 89, 255)   (255, 73, 73)
    4. Orientado para o leste (animado e quiescente)   (185, 56, 255)   (235, 36, 36)

Os estados "excitados" transportam dados, à taxa de um bit por etapa de transição de estado.

Observe que os estados confluentes têm a propriedade de um atraso de um ciclo, mantendo assim efetivamente dois bits de dados a qualquer momento.

Regras de estado de transmissão

O fluxo de bits entre as células é indicado pela propriedade direction. As seguintes regras se aplicam:

  • Os estados de transmissão aplicam o operador OR às entradas, o que significa que uma célula em um estado de transmissão (comum ou especial) será excitada no tempo t + 1 se qualquer uma das entradas apontando para ela estiver excitada no tempo t
  • Os dados passam da célula A em um estado de transmissão comum para uma célula adjacente B em um estado de transmissão comum, de acordo com a propriedade de direção de A (a menos que B também seja direcionado para A , caso em que os dados desaparecem).
  • Os dados passam da célula A em um estado de transmissão especial para uma célula B adjacente em um estado de transmissão especial, de acordo com as mesmas regras dos estados de transmissão comuns.
  • Os dois subconjuntos de estados de transmissão, ordinário e especial, são mutuamente antagônicos:
    • Dada uma célula A no tempo t no estado de transmissão normal excitado
    • apontando para uma célula B em qualquer estado de transmissão especial
    • no instante t + 1, a célula B se tornará o estado fundamental. A célula de transmissão especial foi "destruída".
    • uma sequência semelhante ocorrerá no caso de uma célula no estado de transmissão especial "apontando" para uma célula no estado de transmissão normal

Regras de estado confluente

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

  • Os estados confluentes não transmitem dados entre si.
  • Os estados confluentes recebem a entrada de um ou mais estados de transmissão comuns e fornecem a saída para os estados de transmissão, comuns e especiais, que não são direcionados ao estado confluente.
  • Os dados não são transmitidos em relação à propriedade de direção do estado de transmissão.
  • Os dados mantidos por um estado confluente são perdidos se esse estado não tiver um estado de transmissão adjacente que também não seja apontado para o estado confluente.
  • Assim, as células em estado confluente são usadas como "pontes" de linhas de transmissão de células em estado de transmissão comum a especial.
  • O estado confluente aplica o operador AND às entradas, apenas "salvando" uma entrada excitada se todas as entradas potenciais forem excitadas simultaneamente.
  • As células confluentes atrasam os sinais em uma geração a mais do que as células OTS; isso é necessário devido às restrições de paridade .

Regras de construção

Os nove tipos de células que podem ser construídos na CA de von Neumann. Aqui, os sinais binários passam por nove linhas de transmissão comuns, construindo uma nova célula quando encontram um estado fundamental no final. Por exemplo, a string binária 1011 é mostrada na quinta linha e constrói o estado de transmissão especial direcionado para o leste - este é o mesmo processo usado no autômato no topo desta página. Observe que não há interação entre os fios vizinhos, ao contrário do Wireworld por exemplo, permitindo um empacotamento compacto de componentes.

Inicialmente, grande parte da célula-espaço, o universo do autômato celular, é "em branco", que consiste de células no estado fundamental U . Quando recebe uma excitação de entrada de um estado de transmissão comum ou especial vizinho, a célula no estado fundamental torna-se "sensibilizada", passando por uma série de estados antes de finalmente "descansar" em uma transmissão quiescente ou estado confluente.

A escolha de qual estado de destino a célula alcançará é determinada pela sequência de sinais de entrada. Portanto, os estados de transição / sensibilizados podem ser pensados ​​como os nós de uma árvore de bifurcação que vai do estado fundamental a cada transmissão quiescente e estados confluentes.

Na árvore a seguir, a sequência de entradas é mostrada como uma string binária após cada etapa:

  • uma célula no estado fundamental U , dada uma entrada, fará a transição para o estado S (recém-sensibilizado) no próximo ciclo (1)
  • uma célula no estado S , sem entrada, fará a transição para o estado S 0 (10)
    • uma célula no estado S 0 , sem entrada, fará a transição para o estado S 00 (100)
      • uma célula no estado S 00 , sem entrada, fará a transição para o estado S 000 (1000)
        • uma célula no estado S 000 , sem entrada, fará a transição para o estado de transmissão comum direcionado para o leste (10000)
        • uma célula no estado S 000 , dada uma entrada, fará a transição para o estado de transmissão comum direcionado para o norte (10001)
      • uma célula no estado S 00 , dada uma entrada, fará a transição para o estado de transmissão comum direcionado para oeste (1001)
    • uma célula no estado S 0 , dada uma entrada, fará a transição para o estado S 01 (101)
      • uma célula no estado S 01 , sem entrada, fará a transição para o estado de transmissão comum direcionado para o sul (1010)
      • uma célula no estado S 01 , dada uma entrada, fará a transição para o estado de transmissão especial direcionado para o leste (1011)
  • uma célula no estado S , dada uma entrada, fará a transição para o estado S 1 (11)
    • uma célula no estado S 1 , sem entrada, fará a transição para o estado S 10 (110)
      • uma célula no estado S 10 , sem entrada, fará a transição para o estado de transmissão especial direcionado para o norte (1100)
      • uma célula no estado S 10 , dada uma entrada, fará a transição para o estado de transmissão especial direcionado para oeste (1101)
    • uma célula no estado S 1 , dada uma entrada, fará a transição para o estado S 11 (111)
      • uma célula no estado S 11 , sem entrada, fará a transição para o estado de transmissão especial direcionado para o sul (1110)
      • uma célula no estado S 11 , dada uma entrada, fará a transição para o estado confluente quiescente C 00 (1111)

Observe que:

  • mais um ciclo de entrada (quatro após a sensibilização inicial) é necessário para construir o estado de transmissão comum direcionado para leste ou norte do que qualquer um dos outros estados (que requerem três ciclos de entrada após a sensibilização inicial),
  • o estado quiescente "padrão" que resulta na construção é o estado de transmissão comum direcionado para o leste - que requer uma entrada de sensibilização inicial e, em seguida, quatro ciclos sem entrada.

Regras de destruição

Aproximadamente 4000 bits de dados em uma "fita" enrolada construindo um padrão complexo. Ele usa uma variação de 32 estados do autômato celular de von Neumann conhecido como Hutton32.
  • Uma entrada em uma célula de estado confluente de uma célula de estado de transmissão especial resultará na célula de estado confluente sendo reduzida de volta ao estado fundamental.
  • Da mesma forma, uma entrada em uma célula de estado de transmissão comum de uma célula de estado de transmissão especial resultará na célula de estado de transmissão comum sendo reduzida de volta ao estado fundamental.
  • Por outro lado, uma entrada em uma célula de estado de transmissão especial de uma célula de estado de transmissão comum resultará na célula de estado de transmissão especial sendo reduzida de volta ao estado fundamental.

Veja também

Referências

  • Von Neumann, J. e AW Burks (1966). Teoria dos autômatos auto-reprodutores. Urbana, University of Illinois Press. [1]

links externos

  • Golly - suporta CA de von Neumann junto com o Jogo da Vida e outros conjuntos de regras.