Jump to content

Langton's loops: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Ferkel (talk | contribs)
357 edits
merger proposal
Ferkel (talk | contribs)
357 edits
Merge content from Byl's loop and Chou-Reggia loop, added new comparison table and images
Line 1: Line 1:
[[Image:Langtons_Loop.png|frame|right|Langton's Loop, in the starting configuration.]]
{{Mergefrom-multiple|Byl's loop|Chou-Reggia loop|discuss=Talk:Langton's loops|date=February 2009}}


⚫
'''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.
[[Image:LangtonLoop.PNG|thumb|right|A growing loop.]]

⚫
'''Langton's loops''' are a particular "species" of [[artificial life]] first conceived by [[Christopher Langton]]. The loops, which are simulated in a [[cellular automaton]] space, consist of a "sheath" of cells surrounding the genetic information, which flows continuously around the loop. Each instruction in turn collides with a particular site on the sheath, causing the loop to extend an "arm" (or [[pseudopod]]), which will become the daughter loop. The "genes" then enter the arm and instruct it to make three left turns, completing the loop, which then disconnects from its parent.


==History==
==History==
In 1952 [[John von Neumann]] <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}}</ref>created the first cellular automaton with the goal of creating a universally self-replicating machine. This automaton was necessarily very complex due to its universality. In 1968 [[Edgar F. Codd]] reduced the number of states in the automaton from 29 to 8. 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.
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}}</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==
⚫
==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 above, and may be stated as a series of numbered states starting from the bottom left corner and running counter-clockwise: 0710710711111041041071071071. In this example, black squares represent cells with state 0, red squares are in state 1, and so on.


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/].
⚫
==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.


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.
==Related organisms==


[[Image:Langtons_Loop_Colony.png|thumb|right|A colony of loops. The ones in the centre are "dead".]]
===SDSR Loop===
The '''SDSR''' ('''S'''tructurally '''D'''issolvable '''S'''elf-'''R'''eproducing) loop is a variant of Langton's loop by Hiroki Sayama that has a limited lifetime, and dissolves at the end of its life cycle. This allows continuous growth and turn-over of generations, whereas Langton's original loops' population is limited by the available space.


⚫
===Colonies===
An SDSR loop dissolves due to the introduction of a ninth state to the [[cellular automaton]]. This state appears when the sheathed "pseudopod" collides with a sheath fragment or another loop. Thus, when loops' pseudopodia collide, the loops dissolve, opening up space for the next generation.


⚫
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.
===Evoloop===

The '''Evoloop''' is a modification of Langton's loop by H. Sayama which is capable of interaction with neighboring loops as well as of [[evolution]]. Rather than becoming dormant when it is surrounded by neighbors, the Evoloop is capable of interacting with them. The Evoloop's [[genome]] is also much less rigid than that of the original loop, allowing [[speciation]]. Often, the greatest selection pressure in a colony of Evoloops is the competition for space, and [[natural selection]] often favors the smallest functional loop present.


⚫
===Encoding of the genome===
Though it is rare in any given Evoloop simulation, a form of [[conjugation]] can sometimes be observed among interacting loops. Following a collision between sheathed "pseudopodia", genes from one loop interfere with those from another, producing a [[Hybrid (biology)|hybrid]] or [[chimera (genetics)|chimera]] daughter loop. This conjugation, however, is not particularly useful for evolutionary purposes, as the daughter organisms are usually incapable of reproduction.
⚫
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 counter-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 directon. State 6 temporarily joins the genome of the daughter loop and initialises the growing arm at the next corner it reaches.
In the case of Evoloops, which have both the ability to evolve and a limited life span, it is possible for a simulated [[ecosystem]] to emerge.


==Comparison of related CA loops==
===Sexyloop===


{| class="wikitable" style="text-align:center"
Sexyloop is a modification of Evoloop by Nicolas Oros and Chrystopher Nehaniv in which collisions often result in transfer of genetic material between loops. This increases diversity in evolution of new species of loops.
|-
! 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}}</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}}</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|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}}</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|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}}</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}}</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. || 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}}</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 ==
Line 46: Line 59:


==External links==
==External links==
*[http://www.necsi.org/postdocs/sayama/sdsr/ Structurally Dissolvable Self-Reproducing Loop & Evoloop: Evolving SDSR Loop]
*[http://necsi.org/postdocs/sayama/sdsr/java/] A [[Java applet]] of several of the self-replicating loops.
*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%27s_Game_of_Life|Game of Life]], and other rulesets.


[[Category:Artificial life]]
[[Category:Artificial life]]
Line 53: Line 68:
[[de:Langton-Schleife]]
[[de:Langton-Schleife]]
[[fr:Boucle de Langton]]
[[fr:Boucle de Langton]]
[[ja:ラングトンのループ]]
[[ja:?????????]]
[[fi:Langtonin silmukka]]
[[fi:Langtonin silmukka]]

Revision as of 22:08, 4 February 2009

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[1]. 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's CA to 8 in his[2]. 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 transition table can be found here: [1].

As with 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.

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 asymptotic to , 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 counter-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 directon. State 6 temporarily joins the genome of the daughter loop and initialises the growing arm at the next corner it reaches.

CA number of states neighborhood number of cells (typical) replication period (typical) thumbnail
Langton's loops[3] (1984): The original self-reproducing loop. 8 von Neumann 86 151
Byl's loop[4] (1989): By removing the inner sheath, Byl reduced the size of the loop. 6 von Neumann 12 25
Chou-Reggia loop[5] (1993): A further reduction of the loop by removing all sheaths. 8 von Neumann 5 15
Tempesti loop[6] (1995): Tempesti added construction capabilities to his loop, allowing patterns to be written inside the loop after reproduction. 10 Moore 148 304
Perrier loop[7] (1996): Perrier added a program stack and an extensible data tape to Langton's loop, allowing it to compute anything computable. 64 von Neumann 158 235
SDSR loop[8] (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
Evoloop[9] (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. 9 von Neumann 149 363
Sexyloop[10] (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

  1. ^ von Neumann, John (1966). "Theory of Self-Reproducing Automata." (Scanned book online). www.walenz.org. Retrieved 2008-02-29. {{cite web}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  2. ^ Codd, Edgar F. (1968). "Cellular Automata". Academic Press, New York.
  3. ^ C. G. Langton (1984). "Self-reproduction in cellular automata". Physica D. 10: 135–144.
  4. ^ J. Byl (1989). "Self-Reproduction in small cellular automata". Physica D. 34: 295–299.
  5. ^ J. A. Reggia, S. L. Armentrout, H.-H. Chou, and Y. Peng (1993). "Simple systems that exhibit self-directed replication". Science. 259: 1282–1287.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  6. ^ G. Tempesti (1995). "A New Self-Reproducing Cellular Automaton Capable of Construction and Computation". Advances in Artificial Life, Proc. 3rd European Conference on Artificial Life. Granada, Spain: Lecture Notes in Artificial Intelligence, 929, Springer Verlag, Berlin. pp. 555–563. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  7. ^ J.-Y. Perrier, M. Sipper, and J. Zahnd (1996). "Toward a viable, self-reproducing universal computer". Physica D. 97: 335–352.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  8. ^ Hiroki Sayama (1998). "Introduction of Structural Dissolution into Langton's Self-Reproducing Loop". Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life. Los Angeles, California: MIT Press. pp. 114–122. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  9. ^ Hiroki Sayama (1999). "Toward the Realization of an Evolving Ecosystem on Cellular Automata". Proceedings of the Fourth International Symposium on Artificial Life and Robotics (AROB 4th '99). Beppu, Oita, Japan. pp. 254–257. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  10. ^ Nicolas Oros and C. L. Nehaniv (2007). "Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata". The First IEEE Symposium on Artificial Life (April 1-5, 2007, Hawaii, USA). pp. 130–138. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=Langton%27s_loops&oldid=268561992"