| The Cellular Automata of John von Neumann
JVN and EVN transition rules
The cellular automata of von Neumann are infinite planar lattices of squared cells behaving as small systems with a finite number of states and interacting with their four closest neighbors, i.e., the adjacent cell-states on the left, up, right and down sides. The state of the whole cell-lattice is the ordered collection of cell states. The cell-lattice state evolves over a discrete temporal series t1, t2,... according to certain transition rules. These determine the state in which any given cell will be found at time tn+1 depending on its previous state and on those of its four closest neighbors at time tn.
The whole system has a geometric planar symmetry but not a functional planar symmetry. This means that the family of cell states as a whole is invariant with respect to arbitrary translations and reflections with respect to vertical, horizontal and diagonal lines, and that the transition rules tend when possible to preserve these symmetries, but that the transition rules are not fully translation-invariant. The reason for the lack of functional symmetry is that the generation of specifically oriented cell states through sequences of sensitized states depends strictly upon the bit-sequence of the activation train inputted to the vacuum state, which is independent of lattice orientation.
A striking aspect of von Neumann's automata is that the cell states and the transition rules admit functional meanings with respect to possible external interpreters. Indeed, one can interpret a cell state as a unit capable of performing operations provided with logical and physical meanings. The transition rules are just the "meanings" of these operations. Besides, providing an exact formal description of the transition rules would be a rather cumbersome task; we can accomplished this much more easily in terms of functional meanings by practical examples rather than by the complete list of cases.
Von Neumann designed his planar automata as a minimal systems governed by rules that are sufficient to implement the property of universal constructivity and to reach this goal he put forwards a series of reasoning that are very rich of functional meanings. In particular, he conceived the system as an environment in which a class of finite objects can generate a wide repertoire of other objects to an extent sufficient to implement self-reproduction. The extended von Neumann's (EVN) rules provided by the Author include new functional meanings. These rules, although not forming a minimal set, have the merit of simplifying considerably the achievement of von Neumann's goal.
Thus, the primary requirement for a set of transition rules is that there be elementary objects (cells) that maintain their identity in the course of their evolution. To obtain this, von Neumann imagined the cells as having a finite number of states, someone stable and others excited when the cell is isolated. The evolution of a cell assembly formed these objects is determined by the fact that each object can transmit its excitation to adjacent objects.
A second important requirement is that the transition rules should allow for the propagation of signals within the cell lattice. Thus, some cells must be able to communicate with adjacent cells in various directions. This property can be assured if certain cell states of definite spatial orientation can transit from a quiescent to an excited state or vice versa. Cell states of this sort can be defined transmission states. Suitable sequences of transmission states can then form trasmission lines capable of propagation trains of binary signals.
An important property of the transition rules, which is useful for the implementation of simple switches, is that any two adjacent transmission states of same type with opposite orientations should never transmit to each other their excitation.
Another important property of both the JVN and the EVN transition rules is that any cell state can be generated by the excitation of a fundamental state called the vacuum state, and destroyed (or "annihilated"), i.e., brought back to the vacuum state, by the excitatory discharge of a neighboring state. These construction-destruction properties are equivalent to assuming a principle of reversibility for the set of transition rules.
A further important requirement is the possibility of implementing the logical operations AND and OR for binary-signal trains at the meet of two transmission lines.
For obvious reasons, the automata of WJVN.EXE are implemented in a finite cell lattice, which, for "historical" reasons, is formed by 640x480 squared cells. The cell-lattice topology, however, can be organized as an open rectangle, a vertical cylinder, a horizontal cylinder or a torus.