Von Neumann cellular automaton
2234009
197786091
2008-03-12T19:31:06Z
71.105.36.87
/* States */
{{references|date=December 2007}}
{{wikify|date=December 2007}}
'''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 [[Stanisław Marcin Ulam|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.
== 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.
== 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. They are
# a '''ground''' state '''U'''
# the '''transition''' or '''sensitised''' states (in 8 substates)
## '''S''' (newly sensitised)
## '''S<sub>0</sub>''' - (sensitised, having received no input for one cycle)
## '''S<sub>00</sub>''' - (sensitised, having received no input for two cycles)
## '''S<sub>01</sub>''' - (sensitised, having received no input for one cycle and then an input for one cycle)
## '''S<sub>000</sub>''' - (sensitised, having received no input for three cycle)
## '''S<sub>1</sub>''' - (sensitised, having received an input for one cycle)
## '''S<sub>10</sub>''' - (sensitised, having received an input for one cycle and then no input for one cycle)
## '''S<sub>11</sub>''' - (sensitised, having received input for two cycles)
# the '''confluent''' states (in 4 states of excitation)
## '''C<sub>00</sub>''' - quiescent (and will also be quiescent next cycle)
## '''C<sub>01</sub>''' - excited (but will be quiescent next cycle)
## '''C<sub>10</sub>''' - next-excited (now quiescent, but will be excited next cycle)
## '''C<sub>11</sub>''' - excited next-excited (currently excited and will be excited next cycle)
# the '''ordinary transmission''' states (in 4 directions, excited or quiescent, making 8 states)
## North-directed (excited and quiescent)
## South-directed (excited and quiescent)
## West-directed (excited and quiescent)
## East-directed (excited and quiescent)
# the '''special transmission''' states (in 4 directions, excited or quiescent, making 8 states)
## North-directed (excited and quiescent)
## South-directed (excited and quiescent)
## West-directed (excited and quiescent)
## 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.
== 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
== 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
== 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 transition to a '''S''' (newly sensitised) state in the next cycle
* a cell in the '''S''' state, given no input, will transition into the '''S<sub>0</sub>''' state
** a cell in the '''S<sub>0</sub>''' state, given no input, will transition into the '''S<sub>00</sub>''' state
*** a cell in the '''S<sub>00</sub>''' state, given no input, will transition into the '''S<sub>000</sub>''' state
**** a cell in the '''S<sub>000</sub>''' state, given no input, will transition into the "east-pointing" special transmission state
**** a cell in the '''S<sub>000</sub>''' state, given an input, will transition into the "north-pointing" special transmission state
*** a cell in the '''S<sub>00</sub>''' state, given an input, will transition into the "west-pointing" special transmission state
** a cell in the '''S<sub>0</sub>''' state, given an input, will transition into the '''S<sub>01</sub>''' state
*** a cell in the '''S<sub>01</sub>''' state, given no input, will transition into the "south-pointing" special transmission state
*** a cell in the '''S<sub>01</sub>''' 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<sub>1</sub>''' state
** a cell in the '''S<sub>1</sub>''' state, given no input, will transition into the '''S<sub>10</sub>''' state
*** a cell in the '''S<sub>10</sub>''' state, given no input, will transition into the "north-pointing" ordinary transmission state
*** a cell in the '''S<sub>10</sub>''' state, given an input, will transition into the "west-pointing" ordinary transmission state
** a cell in the '''S<sub>1</sub>''' state, given an input, will transition into the '''S<sub>11</sub>''' state
*** a cell in the '''S<sub>11</sub>''' state, given no input, will transition into the "south-pointing" ordinary transmission state
*** a cell in the '''S<sub>11</sub>''' state, given an input, will transition into the quiescent confluent state '''C<sub>00</sub>'''
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
== 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 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
==See also==
* [[von Neumann Universal Constructor]]
==References==
* Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana,, University of Illinois Press. [http://www.walenz.org/vonNeumann/index.html]
[[Category:Cellular automaton rules]]
[[ru:Автомат Фон-Неймана]]