Von Neumann's Constructor In the 1950's, John von Neumann developed a model, known as the Universal Constructor, a cellular automaton that became the basis for the greater part of the research on self-replicating machines for decades following its conception.

The field of bio-inspired digital hardware was pioneered by John von Neumann. A gifted mathematician and one of the leading figures in the development of the field of computer engineering, von Neumann dedicated the final years of his life on what he called the theory of automata. This research, which was unfortunately interrupted by his untimely death in 1957, was inspired by the parallel between artificial automata, of which the paramount example are computers, and natural automata such as the nervous system, evolving organisms, etc. To find a physical realization for his theory of automata, von Neumann developed a model, known as von Neumann's Universal Constructor, a cellular automaton that became the basis for the greater part of the research on self-replicating machines for decades following its conception.

In von Neumann's work, self-replication is always presented as a special case of universal construction: his machine Uconst is capable of building any other machine M, provided it can access its description D(M) (Figure 1). This approach was maintained in the design of his cellular automaton, which is therefore much more than a self-replicating machine. The complexity of its purpose is reflected in the complexity of its structure, based on three separate components:

• A memory tape, containing the description (a one-dimensional string of elements) of the machine to be built. In the special case of self-replication, the memory contains a description of the universal constructor itself.
• The constructor itself, a machine capable of reading the memory tape and interpreting its contents.
• A constructing arm, directed by the constructor, used to build the offspring (the machine described in the memory tape). The arm moves in space and sets the state of the elements of the offspring to the appropriate state.

Beyond this already considerable complexity, von Neumann postulated the presence of a universal computer Ucomp (in practice, a universal Turing machine, an automaton capable of performing any finite computation) that is attached to, and replicated with, the universal constructor. The implementation as a cellular automaton is correspondingly complex. Each cell has 29 possible states, and thus, since the next state of a cell depends on its current state and that of its four cardinal neighbors, 29⁵=20,511,149 transition rules are required to exhaustively define its behavior. If we consider that the size of von Neumann's constructor is of the order of 100,000 elements, we can easily understand why the automaton has not even been fully simulated as of today.

In fact, as part of the Embryonics project, we did realize a hardware implementation of a set of elements of von Neumann's automaton. By carefully designing the hardware structure of each element, we were able to considerably reduce the amount of memory required to host the transition rules. Using this same technique, we were able to encode one cell of von Neumann's automaton in each element of the BioWall, providing us with a surface of 3200 elements that, while not sufficient by far to fully implement the universal constructor, represents a sufficiently large surface to implement many of the significant portions (organs, in von Neumann's terminology) of the machine.

• J.-L. Beuchat, J.-O. Haenni. "Von Neumann's 29-State Cellular Automaton: A Hardware Implementation". IEEE Trans. on Education, Vol. 43, No 3, pp. 300-308, August 2000.
  
• J. von Neumann. The Theory of Self-Reproducing Automata. A.W. Burks (ed.), University of Illinois Press, Urbana, IL, 1966.