View source for Codd's cellular automaton

{{short description|2D cellular automaton devised by Edgar F. Codd in 1968}}
[[Image:Codd CA RepeaterEmitter.gif|right|frame|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 [[United Kingdom|British]] [[computer scientist]] [[Edgar F. Codd]] in 1968. It was designed to recreate the computation- and construction-universality of [[von Neumann cellular automaton|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 [[von Neumann Universal Constructor|universal constructor]], but never gave a complete implementation.

==History==
In the 1940s and '50s, [[John von Neumann]] posed the following problem:<ref name=vonNeumann66>{{cite web|url=http://www.walenz.org/vonNeumann/index.html| title=''Theory of Self-Reproducing Automata.''|last1=von Neumann|first1=John|last2=Burks|first2=Arthur W.|year=1966|publisher=www.walenz.org|accessdate=2012-01-28 |archiveurl=https://web.archive.org/web/20080105213853/http://www.walenz.org/vonNeumann/index.html|archivedate=2008-01-05}}</ref>
*What kind of logical organization is sufficient for an automaton to be able to reproduce itself?
He was able to construct a [[von Neumann cellular automaton|cellular automaton]] with 29 states, and with it a [[Von Neumann universal constructor|universal constructor]]. Codd, building on von Neumann's work, found a simpler machine with eight states.<ref name=Codd68>{{cite book|author=Codd, Edgar F.|title=Cellular Automata|publisher=Academic Press, New York|year=1968}}</ref> 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.<ref name=Banks1971>{{cite book|title=Information Processing and Transmission in Cellular Automata|year=1971| first=Edwin| last=Banks|publisher=PhD thesis, MIT, Department of Mechanical Engineering|url=http://www.bottomlayer.com/bottom/banks/banks_commentary.htm}}</ref> 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 (program)|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.<ref name=Langton84>{{cite journal|doi=10.1016/0167-2789(84)90256-2|title=Self-Reproduction in Cellular Automata|author=Langton, C. G.|year=1984| journal=Physica D: Nonlinear Phenomena|volume=10|issue=1–2|pages=135–144|bibcode=1984PhyD...10..135L|url=https://deepblue.lib.umich.edu/bitstream/2027.42/24968/1/0000395.pdf|hdl=2027.42/24968|hdl-access=free}}</ref>

===Comparison of CA rulesets===
{| class="wikitable" style="text-align:center"
|-
!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<ref name=Hutton2010>{{cite journal|doi=10.1162/artl.2010.16.2.16200|journal=Artificial Life|volume=16|issue=2|pages=99–117|author=Hutton, Tim J.|year=2010|url=http://www.sq3.org.uk/papers/Hutton_CoddsSelfReplicatingComputer_2010.pdf|title=Codd's self-replicating computer|pmid=20067401|s2cid=10049331|access-date=2010-08-01|archive-date=2012-02-05|archive-url=https://web.archive.org/web/20120205001352/http://www.sq3.org.uk/papers/Hutton_CoddsSelfReplicatingComputer_2010.pdf|url-status=dead}}</ref>
|-
| Devore || 8 || rotations || yes || 94,794 cells
|-
| Banks IV ([[Banks IV Cellular Automaton]]) || 2 - 4 <ref>{{Cite web|url=http://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm|title=Roger Banks Proof of Universal Computation in Cellular Automata}}</ref><ref name=Banks1971 /> || rotations and reflections || yes || Somewhere around 100,000,000,000 cells
|-
| Langton's loops || 8 || rotations || no || 86 cells
|}

==Specification==

[[Image:Codd CA ConstructionArm.gif|right|frame|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'.

{| 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 B-machine|Wang's W-machine]]. However, the design was so colossal that it evaded implementation until 2009, when Tim Hutton constructed an explicit configuration.<ref name=Hutton2010 /> There were some minor errors in Codd's design, so Hutton's implementation differs slightly, in both the configuration and the ruleset.

==See also==
*[[Artificial life]]
*[[Cellular automaton]]
*[[Conway's Game of Life]]
*[[Langton's loops]]
*[[Von Neumann cellular automaton]]
*[[Wireworld]]

==References==
<references/>

==External links==
*The [https://github.com/GollyGang/ruletablerepository Rule Table Repository] has the [https://github.com/GollyGang/ruletablerepository/blob/gh-pages/downloads/Codd2.table transition table for Codd's CA].
*[http://golly.sourceforge.net Golly] - supports Codd's CA along with the [[Conway's Game of Life|Game of Life]], and other rulesets.
*[https://github.com/GollyGang/ruletablerepository/wiki/CoddsDesign Download the complete machine (13MB)] and more details.
*[http://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm] shows more on Banks IV.

[[Category:Artificial life]]
[[Category:Cellular automaton rules]]