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:Автомат Фон-Неймана]]