View source for Arf invariant of a knot

[[Image:Langtons Loop.png|frame|right|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 continuously around the loop and out along an "arm" (or [[pseudopod]]), which will become the daughter loop. The "genes" instruct it to make three left turns, completing the loop, which then disconnects from its parent.

== History ==

In 1952 [[John von Neumann]] created the first cellular automaton (CA) with the goal of creating a self-replicating machine.<ref name=TSRA>{{cite web| url=http://www.walenz.org/vonNeumann/index.html| title=''Theory of Self-Reproducing Automata.''| author=von Neumann, John| coauthors=Burks, Arthur W.| date=1966| publisher=www.walenz.org| format=Scanned book online| accessdate=2008-02-29 |archiveurl = http://web.archive.org/web/20080105213853/http://www.walenz.org/vonNeumann/index.html <!-- Bot retrieved archive --> |archivedate = 2008-01-05}}</ref> This automaton was necessarily very complex due to its computation- and construction-universality. In 1968 [[Edgar F. Codd]] reduced the number of states from 29 in [[von Neumann cellular automaton|von Neumann's CA]] to 8 in [[Codd's cellular automaton|his]].<ref name=Codd68>{{cite book|author = Codd, Edgar F.|title="Cellular Automata"|publisher=Academic Press, New York|year=1968}}</ref> When Christopher Langton did away with the universality condition, he was able to significantly reduce the automaton's complexity. Its self-replicating loops are based on one of the simplest elements in Codd's automaton, the periodic emitter.

== Specification ==

Langton's Loops run in a CA that has 8 states, and uses the [[von Neumann neighborhood]] with rotational symmetry. The [[State transition table|transition table]] can be found here: [http://code.google.com/p/ruletablerepository/wiki/TheRules#Self-replicating_loops].

As with [[Codd's cellular automaton|Codd's CA]], Langton's Loops consist of sheathed wires. The signals travel passively along the wires until they reach the open ends, when the command they carry is executed.

[[Image:Langtons Loop Colony.png|thumb|right|A colony of loops. The ones in the centre are "dead".]]

=== Colonies ===

Because of a particular property of the loops' "pseudopodia", they are unable to reproduce into the space occupied by another loop. Thus, once a loop is surrounded, it is incapable of reproducing, resulting in a [[coral]]-like colony with a thin layer of reproducing organisms surrounding a core of inactive "dead" organisms. Unless provided unbounded space, the colony's size will be limited. The maximum population will be [[asymptote|asymptotic]] to <math>\left \lfloor \frac{A}{121} \right \rfloor</math>, where ''A'' is the total area of the space in cells.

=== Encoding of the genome ===

The loops' genetic code is stored as a series of nonzero-zero state pairs. The standard loop's genome is illustrated in the picture at the top, and may be stated as a series of numbered states starting from the T-junction and running clockwise: 70-70-70-70-70-70-40-40. The '70' command advances the end of the wire by one cell, while the '40-40' sequence causes the left turn. State 3 is used as a temporary marker for several stages.

While the roles of states 0,1,2,3,4 and 7 are similar to Codd's CA, the remaining states 5 and 6 are used instead to mediate the loop replication process. After the loop has completed, state 5 travels counter-clockwise along the sheath of the parent loop to the next corner, causing the next arm to be produced in a different direction.  State 6 temporarily joins the genome of the daughter loop and initialises the growing arm at the next corner it reaches.

The genome is used a total of six times: once to extend the pseudopod to the desired location, four times to complete the loop, and again to [[DNA replication|transfer]] the genome into the daughter loop. Clearly, this is dependent on the fourfold [[rotational symmetry]] of the loop; without it, the loop would be incapable of containing the information required to describe it. The same use of symmetry for genome compression is used in many biological [[viruses]], such as the [[icosahedral symmetry|icosahedral]] [[adenovirus]].

== Comparison of related CA loops ==

{| class="wikitable" style="text-align:center"
|-
! CA !! number of states !! [[Neighbourhood (graph theory)|neighborhood]] !! number of cells (typical) !! replication period (typical) !! thumbnail
|-
| '''Langton's loops'''<ref name=Langton1984>{{cite journal|author=C. G. Langton|title=Self-reproduction in cellular automata|journal=Physica D|volume=10|pages=135–144|year=1984|doi=10.1016/0167-2789(84)90256-2}}</ref> (1984): The original self-reproducing loop.  || 8 || von Neumann || 86 || 151 || [[Image:Langtons Loop.png|none|100x100px]]
|-
| '''[[Byl's loop]]'''<ref name=Byl1989>{{cite journal|author=J. Byl|title=Self-Reproduction in small cellular automata|journal=Physica D|volume=34|pages=295–299|year=1989|doi=10.1016/0167-2789(89)90242-X}}</ref> (1989): By removing the inner sheath, Byl reduced the size of the loop. || 6 || von Neumann || 12 || 25 || [[Image:Byl Loop.png|none|100x100px]]
|-
| '''Chou-Reggia loop'''<ref name=Reggia1993>{{cite journal |url=http://www.sciencemag.org/content/259/5099/1282.short|author=J. A. Reggia, S. L. Armentrout, H.-H. Chou, and Y. Peng|title=Simple systems that exhibit self-directed replication|journal=Science|volume=259|pages=1282–1287|year=1993|doi=10.1126/science.259.5099.1282|pmid=17732248|issue=5099}}</ref> (1993): A further reduction of the loop by removing all sheaths. || 8 || von Neumann || 5 || 15 ||[[Image:Chou-Reggia Loop.png|none|100x100px]]
|-
| '''Tempesti loop'''<ref name=Tempesti1995>{{cite conference|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.7578|author=G. Tempesti|title=A New Self-Reproducing Cellular Automaton Capable of Construction and Computation|booktitle=Advances in Artificial Life, Proc. 3rd European Conference on Artificial Life|location=Granada, Spain|year=1995|publisher=Lecture Notes in Artificial Intelligence, 929, Springer Verlag, Berlin|pages=555–563}}</ref> (1995): Tempesti added construction capabilities to his loop, allowing patterns to be written inside the loop after reproduction. || 10 || Moore || 148 || 304 || [[Image:Tempesti Loop.png|none|100x100px]]
|-
| '''Perrier loop'''<ref name=Perrier1996>{{cite journal|author=J.-Y. Perrier, M. Sipper, and J. Zahnd|title=Toward a viable, self-reproducing universal computer|journal=Physica D|volume=97|pages=335–352|year=1996|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3200|doi=10.1016/0167-2789(96)00091-7}}</ref> (1996): Perrier added a program stack and an extensible data tape to Langton's loop, allowing it to compute anything [[Computable function|computable]]. || 64 || von Neumann || 158 || 235 || [[Image:Perrier Loop.png|none|100x100px]]
|-
| '''SDSR loop'''<ref name=Sayama1998>{{cite conference|author=Hiroki Sayama|title=Introduction of Structural Dissolution into Langton's Self-Reproducing Loop|booktitle=Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life|pages=114–122|location=Los Angeles, California|year=1998|publisher=MIT Press}}</ref> (1998): With an extra structure-dissolving state added to Langton's loops, the SDSR loop has a limited lifetime and dissolves at the end of its life cycle. This allows continuous growth and turn-over of generations. || 9 || von Neumann || 86 || 151 || [[Image:SDSR Loop.png|none|100x100px]]
|-
| '''Evoloop'''<ref name=Sayama1999>{{cite conference|author=Hiroki Sayama|title=Toward the Realization of an Evolving Ecosystem on Cellular Automata|booktitle=Proceedings of the Fourth International Symposium on Artificial Life and Robotics (AROB 4th '99)|pages=254–257|location=Beppu, Oita, Japan|year=1999|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.391}}</ref> (1999): An extension of the SDSR loop, Evoloop is capable of interaction with neighboring loops as well as of [[evolution]]. Often, the greatest selection pressure in a colony of Evoloops is the competition for space, and [[natural selection]] favors the smallest functional loop present. Further studies demonstrated more complexity than originally thought in the Evoloop system.<ref name=Salzberg2004>{{cite journal|author=Chris Salzberg and Hiroki Sayama|title=Complex genetic evolution of artificial self-replicators in cellular automata|journal=Complexity|volume=10|pages=33–39|year=2004|url=http://www3.interscience.wiley.com/journal/109860047/abstract|doi=10.1002/cplx.20060}}</ref> || 9 || von Neumann || 149 || 363 || [[Image:Evoloop closeup.png|none|100x100px]]
|-
| '''Sexyloop'''<ref name=Oros2007>{{cite conference|author=Nicolas Oros and C. L. Nehaniv|title=Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata|booktitle=The First IEEE Symposium on Artificial Life (April 1-5, 2007, Hawaii, USA)|pages=130–138|year=2007|url=http://hdl.handle.net/2299/6711}}</ref> (2007): Sexyloop is a modification of Evoloop in which collisions often result in transfer of genetic material between loops. This increases diversity in evolution of new species of loops. || 10 || von Neumann || ? || ? ||
|}

== References ==

<references/>

== See also ==

* [[Artificial life]]
* [[Cellular automaton]]
* [[Christopher Langton]]
* [[Codd's cellular automaton]]
* [[Conway's game of life]]
* [[Langton's ant]]
* [[von Neumann cellular automaton]]

== External links ==
{{commonscat|Self-replicating loops}}
* [http://www.youtube.com/watch?v=2iDc4C6vbcc Video] of Chris Langton demonstrating self reproducing loops.
* [http://necsi.edu/postdocs/sayama/sdsr/java/ visual representation] of several of the self-replicating loops in a [[Java applet]] 
* The [http://code.google.com/p/ruletablerepository/ Rule Table Repository] has the transition tables for many of the CA mentioned above.
* [http://golly.sourceforge.net Golly] - supports Langton's Loops along with the [[Conway's Game of Life|Game of Life]], and other rulesets.

{{DEFAULTSORT:Langton's Loops}}
[[Category:Artificial life]]
[[Category:Cellular automaton rules]]