Codd's cellular automaton

Codd's cellular automaton
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 around 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.

Contents

Historical Context

In the 1940s and 50's, 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 Universal Constructor with a square grid and 29 states. E.F. Codd found a simpler machine with only eight states[2]. Therefore von Neumann's question had to be modified:

  • 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 (appendix IV in his thesis) that was also computation- and construction-universal but again didn't implement a self-reproducing machine[3].

John Devore, in his 1973 master's thesis, was able to greatly reduce the size of Codd's machine design while using almost the same 8-state CA. More than just a theoretical device, Devore's machine was possibly the first implementation of a self-reproducing CA. The machine itself could fit inside computer memory but the data tape stretched for thousands of cells, so simulation of the entire self-reproduction cycle was not possible. Decades later, Devore's original design would complete self-reproduction in simulation using the Golly program.

In 1984, Christopher Langton extended Codd's cellular automaton to create Langton's loops[4], which also exhibits reproductive behavior but uses only a very small number of cells compared to the hundreds of thousands needed for self-reproduction in von Neumann, Codd or Banks' cellular automata.

Comparison of CA rulesets

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 4 rotations and reflections yes unknown
Langton's loops 8 rotations no 86 cells

Specification

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 8-states and the 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

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

References

  1. ^ von Neumann, John; Burks, Arthur W. (1966). "Theory of Self-Reproducing Automata." (Scanned book online). www.walenz.org. Archived from the original on 2008-01-05. http://web.archive.org/web/20080105213853/http://www.walenz.org/vonNeumann/index.html. Retrieved 2008-02-29. 
  2. ^ Codd, Edgar F. (1968). Cellular Automata. Academic Press, New York. 
  3. ^ Banks, Edwin (1971). Information Processing and Transmission in Cellular Automata. PhD thesis, MIT, Department of Mechanical Engineering. http://www.bottomlayer.com/bottom/banks/banks_commentary.htm. 
  4. ^ Langton, C. G. (1984). "Self-Reproduction in Cellular Automata". Physica D: Nonlinear Phenomena 10 (1-2): 135–144. doi:10.1016/0167-2789(84)90256-2. 
  5. ^ a b Hutton, Tim J. (2010). "Codd's self-replicating computer". Artificial Life 16 (2): 99–117. doi:10.1162/artl.2010.16.2.16200. PMID 20067401. http://www.sq3.org.uk/papers/Hutton_CoddsSelfReplicatingComputer_2010.pdf. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states …   Wikipedia

  • Edgar F. Codd — Infobox Scientist name = Edgar Frank Ted Codd image width = 150px caption = birth date = birth date|1923|8|23|mf=y birth place = Isle of Portland, England death date = death date and age|2003|4|18|1923|8|23|mf=y death place = Williams Island,… …   Wikipedia

  • Langton's loops — Langton s Loop, in the starting configuration. 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 …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • History of artificial life — The idea of human artifacts being given life has fascinated mankind for as long as men have been recording their myths and stories. Whether Pygmalion or Frankenstein, mankind has been fascinated with the idea of artificial life. Pre computer… …   Wikipedia

  • Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”