User:Rff2/sandbox

Uma configuração simples no Autômato Celular de von Neumann. Um sinal binário é passado repetidamente em torno do fio azul em formato de laço, usando estados de transição ordinária excitados e quiescentes. Uma célula confluente duplica o sinal para um segmento de fio vermelho formado por estados de transição especiais. O sinal percorre o fio e constrói uma nova célula no fim. Este sinal em particular (1011) codifica um estado de transição especial direcionado ao leste, estendendo assim o segmento de fio vermelho em uma célula por vez. Durante a construção, a nova célula passa por diversos estados sensibilizados, de acordo com a sequência binária que a estimule.

Autômato Celular de von Neumann—Autómato celular, teve seu desenvolvimento como consequência de sugestões feitas à 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.

Definição

Configuração

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

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:

1. Um estado vazio U (48, 48, 48)
2. 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)
3. 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)
4. Os estados de transição ordinária (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)
5. 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 transição 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

The flow of bits between cells is indicated by the direction property. The following rules apply:

• Transmission states apply the OR operator to inputs, meaning a cell in a transmission state (ordinary or special) will be excited at time t+1 if any of the inputs pointing to it is excited at time t
• Data passes from cell A in an ordinary transmission state to an adjacent cell B in an ordinary transmission state, according to the direction property of A (unless B is also directed towards A, in which case the data disappears).
• Data passes from cell A in a special transmission state to an adjacent cell B in a special transmission state, according to the same rules as for ordinary transmission states.
• The two subsets of transmission states, ordinary and special, are mutually antagonistic:
  • Given a cell A at time t in the excited ordinary transmission state
  • pointing to a cell B in any special transmission state
  • at time t+1 cell B will become the ground state. The special transmission cell has been "destroyed".
  • a similar sequence will occur in the case of a cell in the special transmission state "pointing" to a cell in the ordinary transmission state

Regras dos estados de confluência

The following specific rules apply to confluent states:

• Confluent states do not pass data between each other.
• Confluent states take input from one or more ordinary transmission states, and deliver output to transmission states, ordinary and special, that are not directed toward the confluent state.
• Data are not transmitted against the transmission state direction property.
• Data held by a confluent state is lost if that state has no adjacent transmission state that is also not pointed at the confluent state.
• Thus, confluent-state cells are used as "bridges" from transmission lines of ordinary- to special-transmission state cells.
• The confluent state applies the AND operator to inputs, only "saving" an excited input if all potential inputs are excited simultaneously.
• Confluent cells delay signals by one generation more than OTS cells; this is necessary due to parity constraints.

Regras de construção

The nine cell types that can be constructed in von Neumann's CA. Here, binary signals pass along nine ordinary transmission lines, constructing a new cell when they encounter a ground state at the end. For example, the binary string 1011 is shown on the fifth line, and constructs the east-directed special transmission state - this is the same process as used in the automaton at the top of this page. Note that there is no interaction between neighbouring wires, unlike in Wireworld for example, allowing for a compact packing of components.

Initially, much of the cell-space, the universe of the cellular automaton, is "blank," consisting of cells in the ground state U. When given an input excitation from a neighboring ordinary- or special transmission state, the cell in the ground state becomes "sensitised," transitioning through a series of states before finally "resting" at a quiescent transmission or confluent state.

The choice of which destination state the cell will reach is determined by the sequence of input signals. Therefore, the transition/sensitised states can be thought of as the nodes of a bifurcation tree leading from the ground-state to each of the quiescent transmission and confluent states.

In the following tree, the sequence of inputs is shown as a binary string after each step:

• a cell in the ground state U, given an input, will transition to the S (newly sensitised) state in the next cycle (1)
• a cell in the S state, given no input, will transition into the S₀ state (10)
  • a cell in the S₀ state, given no input, will transition into the S₀₀ state (100)
    • a cell in the S₀₀ state, given no input, will transition into the S₀₀₀ state (1000)
      • a cell in the S₀₀₀ state, given no input, will transition into the east-directed ordinary transmission state (10000)
      • a cell in the S₀₀₀ state, given an input, will transition into the north-directed ordinary transmission state (10001)
    • a cell in the S₀₀ state, given an input, will transition into the west-directed ordinary transmission state (1001)
  • a cell in the S₀ state, given an input, will transition into the S₀₁ state (101)
    • a cell in the S₀₁ state, given no input, will transition into the south-directed ordinary transmission state (1010)
    • a cell in the S₀₁ state, given an input, will transition into the east-directed special transmission state (1011)
• a cell in the S state, given an input, will transition into the S₁ state (11)
  • a cell in the S₁ state, given no input, will transition into the S₁₀ state (110)
    • a cell in the S₁₀ state, given no input, will transition into the north-directed special transmission state (1100)
    • a cell in the S₁₀ state, given an input, will transition into the west-directed special transmission state (1101)
  • a cell in the S₁ state, given an input, will transition into the S₁₁ state (111)
    • a cell in the S₁₁ state, given no input, will transition into the south-directed special transmission state (1110)
    • a cell in the S₁₁ state, given an input, will transition into the quiescent confluent state C₀₀ (1111)

Note that:

• one more cycle of input (four after the initial sensitization) is required to build the east- or north-directed ordinary transmission state than any of the other states (which require three cycles of input after the initial sensitization),
• the "default" quiescent state resulting in construction is the east-directed ordinary transmission state- which requires an initial sensitization input, and then four cycles of no input.

Regras de destruição

Roughly 4000 bits of data in a curled up "tape" constructing a complex pattern. This uses a 32-state variation of von Neumann cellular automata known as Hutton32.

• An input into a confluent-state cell from a special-transmission state cell will result in the confluent state cell being reduced back to the ground state.
• Likewise, an input into an ordinary transmission-state cell from a special-transmission state cell will result in the ordinary-transmission state cell being reduced back to the ground state.
• Conversely, an input into a special transmission-state cell from an ordinary-transmission state cell will result in the special-transmission state cell being reduced back to the ground state.

Ver também

• Codd's cellular automaton
• Langton's loops
• von Neumann Universal Constructor
• Wireworld

Referências

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

Ligações externas

• Golly - supports von Neumann's CA along with the Game of Life, and other rulesets.

Category:Cellular automaton rules