Von Neumann machines

The cellular automata of von Neumann are finite or infinite arrays of squared cells that can be found in a finite number of states S₁, S₂, ..., S_N. The state of each cell evolves in discrete time steps according to laws depending on the cell state and the states of the closest-neighbor cells. A particular state is assumed to be stable and passive, i.e. incapable of influencing neighboring cells. For this reason, it is called vacuum state.

Suitable assemblies of cells behave as systems provided with operational capabilities. Some systems can act on the neighboring vacuum states in such a way to create other cell-state assemblies. For this reasons, they are called constructors.

The planar automata designed by von Neumann provide simple examples of a much wider class of mathematical or physical systems endowed with construction capabilities, which we can therefore calle von Neumann machines. In certain respects, von Neumann machines are similar to Turing machines. At variance from the latter, however, we can assume that the constructing machines and their possible inputs and outputs are composed of elementary objects belonging to an infinite physical environment. This is not a limitation, as suitable von Neumann machines can work as Turing machines in which suitable arrangements of elementary components play the role of alphanumeric strings (as proteins and nucleic acid chains for those real machines which are called living cells).

We can imagine the cellular automata reported by Burks as excitations of a planar cell lattice. Each cell can be found in a finite number of states and each state can evolve according to certain transition rules, depending on the cell state as well as on the states of the adjacent cells. These simple systems together provide a general framework in which we can pose and analyze several theoretical problems concerning the origin and the nature of life. Since the cellular automata are capable of generating and modifying ordered sets of elements according to precise rules, they possess algorithmic capabilities.

The class of von Neumann machines comprises that of constructors and universal constructors, the latter being a natural generalization of the universal Turing machines. Von Neumann's constructors are provided with one or more reading/writing arms and a constructing arm. A reading/writing arm retrieves information from a tape formed by sting of cells and work approximately as the reading/writing head of a Turing machine. The constructing arm scans an area of the planar cell lattice area and elicit from vacuum cell-states new cell states by the injection of activation pulse streams. Under the direction of a program stored in the tape, the constructor can create any desired assembly of quiescent cell states, then activate this assembly to perform some function. Here, the planar lattice itself plays the role of Turing machine recording tape. It is very likely that in the EVN automaton environment, also universal Turing machines can be implemented (but whether other systems universal constructive capability implies universal computability is not known).

In von Neumann's view, cellular automata of sufficient degree of complexity provide models of processes that are characteristic of living systems. In this framework, the question naturally arises of whether there are automata capable of producing other automata and automata capable of self-reproducing. According to von Neumann, self-reproduction capability requires universal construction capability, i.e. the capability of constructing automata of any sort, even automata whose complexity is greater than that of the universal constructor itself.

The cellular automata designed by von Neumann are assemblies of cells belonging to an infinitely extended two-dimensional cell-lattice. Each cell can be found in a finite number of states and interacts with the four adjacent cells (left, up, right, down), which forms the closest neighbor of the given cell.