Von Neumann cellular automaton

Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanislaw Ulam. Their original purpose was to provide insight into the logical requirements for machine self-replication and were used in von Neumann's universal constructor.

Nobili's cellular automaton is a variation of von Neumann's cellular automaton, augmented with the ability for confluent cells to cross signals and store information. The former requires an extra three states, hence Nobili's cellular automaton has 32 states, rather than 29. Hutton's cellular automaton is yet another variation, which allows a loop of data, analogous to Langton's loops, to replicate.

Definition

Configuration

In general, cellular automata (CA) constitute an arrangement of finite state automata (FSA) that sit in positional relationships between one another, each FSA exchanging information with those other FSAs to which it is positionally adjacent. In von Neumann's cellular automaton, the finite state machines (or cells) are arranged in a two-dimensional Cartesian grid, and interface with the surrounding four cells. As von Neumann's cellular automaton was the first example to use this arrangement, it is known as the von Neumann neighbourhood.

The set of FSAs define a cell space of infinite size. All FSAs are identical in terms of state-transition function, or rule-set.

The neighborhood (a grouping function) is part of the state-transition function, and defines for any cell the set of other cells upon which the state of that cell depends.

All cells transition state synchronously, in step with a universal "clock" as in a synchronous digital circuit.

States

Each FSA of the von Neumann cell space can accept any of the 29 states of the rule-set. The rule-set is grouped into five orthogonal subsets. Each state includes the colour of the cell in the cellular automata program Golly in (red, green, blue). They are

  1. a ground state U (48, 48, 48)
  2. the transition or sensitised states (in 8 substates)
    1. S (newly sensitised) (255, 0, 0)
    2. S0 - (sensitised, having received no input for one cycle) (255, 125, 0)
    3. S00 - (sensitised, having received no input for two cycles) (255, 175, 50)
    4. S000 - (sensitised, having received no input for three cycles) (251, 255, 0)
    5. S01 - (sensitised, having received no input for one cycle and then an input for one cycle) (255, 200, 75)
    6. S1 - (sensitised, having received an input for one cycle) (255, 150, 25)
    7. S10 - (sensitised, having received an input for one cycle and then no input for one cycle) (255, 255, 100)
    8. S11 - (sensitised, having received input for two cycles) (255, 250, 125)
  3. the confluent states (in 4 states of excitation)
    1. C00 - quiescent (and will also be quiescent next cycle) (0, 255, 128)
    2. C01 - next-excited (now quiescent, but will be excited next cycle) (33, 215, 215)
    3. C10 - excited (but will be quiescent next cycle) (255, 255, 128)
    4. C11 - excited next-excited (currently excited and will be excited next cycle) (255, 128, 64)
  4. the ordinary transmission states (in 4 directions, excited or quiescent, making 8 states)
    1. North-directed (excited and quiescent) (36, 200, 36) (106, 106, 255)
    2. South-directed (excited and quiescent) (106, 255, 106) (139, 139, 255)
    3. West-directed (excited and quiescent) (73, 255, 73) (122, 122, 255)
    4. East-directed (excited and quiescent) (27, 176, 27) (89, 89, 255)
  5. the special transmission states (in 4 directions, excited or quiescent, making 8 states)
    1. North-directed (excited and quiescent) (191, 73, 255) (255, 56, 56)
    2. South-directed (excited and quiescent) (203, 106, 255) (255, 89, 89)
    3. West-directed (excited and quiescent) (197, 89, 255) (255, 73, 73)
    4. East-directed (excited and quiescent) (185, 56, 255) (235, 36, 36)

"Excited" states carry data, at the rate of one bit per state transition step.

Note that confluent states have the property of a one-cycle delay, thus effectively holding two bits of data at any given time.

Transmission state rules

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

Confluent state rules

The following specific rules apply to confluent states:

Construction rules

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:

Note that:

Destruction rules

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.

See also

References

External links

This article is issued from Wikipedia - version of the Saturday, December 20, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.