Codd's cellular automaton

Codd showed that it was possible to make a self-reproducing machine in his CA, in a similar way to von Neumann's universal constructor, but never gave a complete implementation.

In the 1940s and '50s, John von Neumann posed the following problem:[1] He was able to construct a cellular automaton with 29 states, and with it a universal constructor.

[2] This modified von Neumann's question: Three years after Codd's work, Edwin Roger Banks showed a 4-state CA in his PhD thesis that was also capable of universal computation and construction, but again did not implement a self-reproducing machine.

Some of the signal trains need to be separated by two blanks (state 1) on the wire to avoid interference, so the 'extend' signal-train used in the image at the top appears here as '70116011'.

[5] There were some minor errors in Codd's design, so Hutton's implementation differs slightly, in both the configuration and the ruleset.

A simple configuration in Codd's cellular automaton. Signals pass along wire made of cells in state 1 (blue) sheathed by cells in state 2 (red). Two signal trains circulate a loop and are duplicated at a T-junction onto an open-ended section of wire. The first (7-0) causes the sheathed end of the wire to become exposed. The second (6-0) re-sheathes the exposed end, leaving the wire one cell longer than before.

The construction arm in Codd's CA can be moved into position using the commands listed in the text. Here the arm turns left, then right, then writes a cell before retracting along the same path.