Von Neumann cellular automata

From Wikipedia, the free encyclopedia

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 mathematician Stanisław Ulam. These cellular automata are a subclass of cellular automata. The purpose for which von Neumann developed cellular automata was to provide insight into the logical requirements for machine self-replication.

Contents 1 von Neumann Cellular Automata as a type of Cellular Automata 2 States 3 Transmission State Rules 4 Confluent State Rules 5 Construction Rules 6 Destruction Rules 7 See also

[edit] von Neumann Cellular Automata as a type of Cellular Automata

• In general, cellular automata 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. The positional relationship of von Neumann cellular automata is rectilinear in two dimensions; i.e. a two-dimensional grid, as formed by the intersection of two sets of mutually perpendicular lines, producing cells within each of which resides an FSA.
• The set of FSAs define a cell space, this space being of infinite size. All FSAs are identical in terms of state-transition function, or rule-set.
• NB - 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.

[edit] States

Each FSA of the von Neumann cell space can accept any of the 29 states of the rule-set. The rule-set includes 29 different states, these being grouped into five orthogonal subsets. They are

1. a ground state U
2. the transition or sensitised states (in 8 substates)
   1. S (newly sensitised)
   2. S₀ - (sensitised, having received no input for one cycle)
   3. S₀₀ - (sensitised, having received no input for two cycles)
   4. S₀₁ - (sensitised, having received no input for one cycle and then an input for one cycle)
   5. S₀₀₀ - (sensitised, having received no input for three cycle)
   6. S₁ - (sensitised, having received an input for one cycle)
   7. S₁₀ - (sensitised, having received an input for one cycle and then no input for one cycle)
   8. S₁₁ - (sensitised, having received input for two cycles)
3. the confluent states (in 4 states of excitation)
   1. C₀₀ - quiescent (and will also be quiescent next cycle)
   2. C₀₁ - excited (but will be quiescent next cycle)
   3. C₁₀ - next-excited (now quiescent, but will be excited next cycle)
   4. C₁₁ - excited next-excited (currently excited and will be excited next cycle)
4. the ordinary transmission states (in 4 directions, excited or quiescent, making 8 states)
   1. North-directed (excited and quiescent)
   2. South-directed (excited and quiescent)
   3. West-directed (excited and quiescent)
   4. East-directed (excited and quiescent)
5. the special transmission states (in 4 directions, excited or quiescent, making 8 states)
   1. North-directed (excited and quiescent)
   2. South-directed (excited and quiescent)
   3. West-directed (excited and quiescent)
   4. East-directed (excited and quiescent)

Activity/"excitement" represents data carriage, with data being communicated between states 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.

[edit] Transmission State Rules

• The flow of bits between cells is indicated by the direction property.
• 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 cells in the ordinary transmission states to other cells in the ordinary transmission states, according to the direction property (in the cell's direction only)
• Data passes from cells in the special transmission states to other cells in the special transmission states, according to the direction property (in the cell's direction only)
• 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

[edit] Confluent State Rules

• 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

[edit] 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 into a series of the transition 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/sensitized 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.

• a cell in the ground state U, given an input, will transision to a S (newly sensitised) state in the next cycle
• a cell in the S state, given no input, will transition into the S₀ state
  • a cell in the S₀ state, given no input, will transition into the S₀₀ state
    • a cell in the S₀₀ state, given no input, will transition into the S₀₀₀ state
      • a cell in the S₀₀₀ state, given no input, will transition into the "east-pointing" special transmission state
      • a cell in the S₀₀₀ state, given no input, will transition into the "north-pointing" special transmission state
    • a cell in the S₀₀ state, given an input, will transition into the "west-pointing" special transmission state
  • a cell in the S₀ state, given an input, will transition into the S₀₁ state
    • a cell in the S₀₁ state, given no input, will transition into the "south-pointing" special transmission state
    • a cell in the S₀₁ state, given an input, will transition into the "east-pointing" ordinary transmission state
• a cell in the S state, given an input, will transition into the S₁ state
  • a cell in the S₁ state, given no input, will transition into the S₁₀ state
    • a cell in the S₁₀ state, given no input, will transition into the "north-pointing" ordinary transmission state
    • a cell in the S₁₀ state, given an input, will transition into the "west-pointing" ordinary transmission state
  • a cell in the S₁ state, given an input, will transition into the S₁₁ state
    • a cell in the S₁₁ state, given no input, will transition into the "south-pointing" ordinary transmission state
    • a cell in the S₁₁ state, given an input, will transition into the quiescent confluent state C₀₀

Note that:

• one more cycle of input (four after the initial sensitization) is required to build the east- or north-pointing special 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-pointing special transmission state- which requires an initial sensitization input, and then four cycles of no input

[edit] Destruction Rules

• 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 special-transmission state cell being reduced back to the ground state
• Conversely, an input into a special transmission-state cell from a ordinary-transmission state cell will result in the ordinary-transmission state cell being reduced back to the ground state

[edit] See also

• Universal Constructor
• University of Leeds Artificial Life Overview
• J. von Neumann (1966), the Theory of self reproducing automata. Edited by A. Burks, Univ. of Illinois Press, Urbana.