Codd's cellular automaton
Codd's cellular automatonis acellular automaton(CA) devised by theBritishcomputer scientistEdgar F. Coddin 1968. It was designed to recreate the computation- and construction-universality ofvon Neumann's CAbut 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'suniversal constructor,but never gave a complete implementation.
History
[edit]In the 1940s and '50s,John von Neumannposed 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 acellular automatonwith 29 states, and with it auniversal 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 isnecessaryfor 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 usingGolly.Christopher Langtonmade another tweak to Codd's cellular automaton in 1984 to createLangton'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]
Codd's CA has eight states determined by avon Neumann neighborhoodwith 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 onWang'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]- Artificial life
- Cellular automaton
- Conway's Game of Life
- Langton's loops
- Von Neumann cellular automaton
- Wireworld
References
[edit]- ^von Neumann, John; Burks, Arthur W. (1966)."Theory of Self-Reproducing Automata.".walenz.org. Archived fromthe originalon 2008-01-05.Retrieved2012-01-28.
- ^Codd, Edgar F. (1968).Cellular Automata.Academic Press, New York.
- ^abBanks, Edwin (1971).Information Processing and Transmission in Cellular Automata.PhD thesis, MIT, Department of Mechanical Engineering.
- ^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.
- ^abHutton, Tim J. (2010)."Codd's self-replicating computer"(PDF).Artificial Life.16(2): 99–117.doi:10.1162/artl.2010.16.2.16200.PMID20067401.S2CID10049331.Archived fromthe original(PDF)on 2012-02-05.Retrieved2010-08-01.
- ^"Roger Banks Proof of Universal Computation in Cellular Automata".
External links
[edit]- TheRule Table Repositoryhas thetransition table for Codd's CA.
- Golly- supports Codd's CA along with theGame of Life,and other rulesets.
- Download the complete machine (13MB)and more details.
- [1]shows more on Banks IV.