Jump to content

Codd's cellular automaton

From Wikipedia, the free encyclopedia
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.

Codd's cellular automaton is a cellular automaton (CA) devised by the British computer scientist Edgar F. Codd 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

[edit]

In the 1940s and '50s, John von Neumann posed the following problem:[1]

  • 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.[2] 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.[3] John Devore, in his 1973 masters thesis, tweaked Codd's rules to greatly reduce the size of Codd's design. A simulation of Devore's design was demonstrated at the third Artificial Life conference in 1992, showing the final steps of construction and activation of the offspring pattern, but full self-replication was not simulated until the 2000's using Golly. Christopher Langton made another tweak to Codd's cellular automaton in 1984 to create Langton's loops, 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.[4]

Comparison of CA rulesets

[edit]
CA number of states symmetries computation- and construction-universal size of self-reproducing machine
von Neumann 29 none yes 130,622 cells
Codd 8 rotations yes 283,126,588 cells[5]
Devore 8 rotations yes 94,794 cells
Banks IV (Banks IV Cellular Automaton) 2 - 4 [6][3] rotations and reflections yes Somewhere around 100,000,000,000 cells
Langton's loops 8 rotations no 86 cells

Specification

[edit]
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.

Codd's CA has eight states determined by a von Neumann neighborhood 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'.

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

[edit]

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.[5] There were some minor errors in Codd's design, so Hutton's implementation differs slightly, in both the configuration and the ruleset.

See also

[edit]

References

[edit]
  1. ^ von Neumann, John; Burks, Arthur W. (1966). "Theory of Self-Reproducing Automata.". www.walenz.org. Archived from the original on 2008-01-05. Retrieved 2012-01-28.
  2. ^ Codd, Edgar F. (1968). Cellular Automata. Academic Press, New York.
  3. ^ a b Banks, Edwin (1971). Information Processing and Transmission in Cellular Automata. PhD thesis, MIT, Department of Mechanical Engineering.
  4. ^ Langton, C. G. (1984). "Self-Reproduction in Cellular Automata" (PDF). Physica D: Nonlinear Phenomena. 10 (1–2): 135–144. Bibcode:1984PhyD...10..135L. doi:10.1016/0167-2789(84)90256-2. hdl:2027.42/24968.
  5. ^ a b Hutton, Tim J. (2010). "Codd's self-replicating computer" (PDF). Artificial Life. 16 (2): 99–117. doi:10.1162/artl.2010.16.2.16200. PMID 20067401. S2CID 10049331. Archived from the original (PDF) on 2012-02-05. Retrieved 2010-08-01.
  6. ^ "Roger Banks Proof of Universal Computation in Cellular Automata".
[edit]