Codd's cellular automaton is a cellular automaton (CA) devised by the British

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

Edgar F. Codd Edgar Frank "Ted" Codd (19 August 1923 – 18 April 2003) was an English computer scientist who, while working for IBM, invented the relational model for database management, the theoretical basis for relational databases and relational databa ...

in 1968. It was designed to recreate the computation- and construction-universality of von Neumann's CA but with fewer states: 8 instead of 29. 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.

History

In the 1940s and '50s,

John von Neumann John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...

posed the following problem: *What kind of logical organization is sufficient for an automaton to be able to reproduce itself? He was able to construct a cellular automaton with 29 states, and with it a universal constructor. Codd, building on von Neumann's work, found a simpler machine with eight states. This modified von Neumann's question: *What kind of logical organization is ''necessary'' for an automaton to be able to reproduce itself? 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. John Devore, in his 1973 masters thesis, tweaked Codd's rules to greatly reduce the size of Codd's design, to the extent that it could be implemented in the computers of that time. However, the data tape for self-replication was too long; Devore's original design was later able to complete replication using Golly.

Christopher Langton __NOTOC__ Christopher Gale Langton (born 1948/49) is an American computer scientist and one of the founders of the field of artificial life. He coined the term in the late 1980s when he organized the first "Workshop on the Synthesis and Simulati ...

made another tweak to Codd's cellular automaton in 1984 to create

Langton's loops Langton's loops are a particular "species" of artificial life in a cellular automaton created in 1984 by Christopher Langton. They consist of a loop of cells containing genetic information, which flows continuously around the loop and out along a ...

, exhibiting self-replication with far fewer cells than that needed for self-reproduction in previous rules, at the cost of removing the ability for universal computation and construction.

Comparison of CA rulesets

Specification

Codd's CA has eight states determined by a

von Neumann neighborhood In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, ...

with rotational symmetry. The table below shows the signal-trains needed to accomplish different tasks. 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'. {, class="wikitable" style="text-align:left" , - ! purpose !! signal train , - , extend , , 70116011 , - , extend_left , , 4011401150116011 , - , extend_right , , 5011501140116011 , - , retract , , 4011501160116011 , - , retract_left , , 5011601160116011 , - , retract_right , , 4011601160116011 , - , mark , , 701160114011501170116011 , - , erase , , 601170114011501160116011 , - , sense , , 70117011 , - , cap , , 40116011 , - , inject_sheath , , 701150116011 , - , inject_trigger , , 60117011701160116011

Universal computer-constructor

Codd designed a self-replicating computer in the cellular automaton, based on Wang's W-machine. However, the design was so colossal that it evaded implementation until 2009, when Tim Hutton constructed an explicit configuration. There were some minor errors in Codd's design, so Hutton's implementation differs slightly, in both the configuration and the ruleset.

References

External links

*Th
Rule Table Repository
has th
transition table for Codd's CA

Golly
- supports Codd's CA along with the

Game of Life ''The Game of Life'', also known as ''Life'', is an 1860 board game by Milton Bradley. Game of Life also often refers to: *Conway's Game of Life, in mathematics, a cellular automaton Game of Life or The Game of Life may also refer to: Games * ' ...