Von Neumann cellular automaton

Cellular automaton used to model universal construction

Von Neumann cellular automata are the original expression of cellular automata, the development of which was 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 they 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.

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 make their transitions synchronously, in step with a universal "clock" as in a synchronous digital circuit.

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.