Langton's loops

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

Contents

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 \left \lfloor \frac{A}{121} \right \rfloor, 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 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 adenovirus.

Comparison of related CA loops

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
Langtons Loop.png
Byl's loop[4] (1989): By removing the inner sheath, Byl reduced the size of the loop. 6 von Neumann 12 25
Byl Loop.png
Chou-Reggia loop[5] (1993): A further reduction of the loop by removing all sheaths. 8 von Neumann 5 15
Chou-Reggia Loop.png
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
Tempesti Loop.png
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
Perrier Loop.png
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
SDSR Loop.png
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. Further studies demonstrated more complexity than originally thought in the Evoloop system.[10] 9 von Neumann 149 363
Evoloop closeup.png
Sexyloop[11] (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; 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. ^ C. G. Langton (1984). "Self-reproduction in cellular automata". Physica D 10: 135–144. doi:10.1016/0167-2789(84)90256-2. 
  4. ^ J. Byl (1989). "Self-Reproduction in small cellular automata". Physica D 34: 295–299. doi:10.1016/0167-2789(89)90242-X. 
  5. ^ J. A. Reggia, S. L. Armentrout, H.-H. Chou, and Y. Peng (1993). "Simple systems that exhibit self-directed replication". Science 259 (5099): 1282–1287. doi:10.1126/science.259.5099.1282. PMID 17732248. http://www.sciencemag.org/content/259/5099/1282.short. 
  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. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.7578. 
  7. ^ J.-Y. Perrier, M. Sipper, and J. Zahnd (1996). "Toward a viable, self-reproducing universal computer". Physica D 97: 335–352. doi:10.1016/0167-2789(96)00091-7. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3200. 
  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. 
  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. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.391. 
  10. ^ Chris Salzberg and Hiroki Sayama (2004). "Complex genetic evolution of artificial self-replicators in cellular automata". Complexity 10: 33–39. doi:10.1002/cplx.20060. http://www3.interscience.wiley.com/journal/109860047/abstract. 
  11. ^ 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. https://uhra.herts.ac.uk/dspace/bitstream/2299/1735/1/901918.pdf. 

See also

External links


Wikimedia Foundation. 2010.

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

Look at other dictionaries:

  • Langton's ant — after 11000 steps. A red pixel shows the ant s location. Langton s ant is a two dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of …   Wikipedia

  • Langton-Schleifen — 2 Langton Schleifen nach der Replikation (Elternschleife links, Tochterschleife rechts) Langton Schleifen (engl. Langton s Loops) stellen eine spezielle Form Künstlichen Lebens dar. Sie wurden 1984 von dem theoretischen Biologen Christopher… …   Deutsch Wikipedia

  • Langton-Schleife — 2 Langton Schleifen nach der Replikation (Elternschleife links, Tochterschleife rechts) Langton Schleifen (engl. Langton s Loops) stellen eine spezielle Form Künstlichen Lebens dar. Sie wurden 1984 von dem theoretischen Biologen Christopher… …   Deutsch Wikipedia

  • Christopher Langton — Born 1948/1949 Nationality American Alma mater …   Wikipedia

  • Boucle De Langton — La boucle de Langton est une structure autoréplicante d un automate cellulaire créée par Christopher Langton en 1984[1]. Sommaire 1 Histoire 2 Description 3 Notes et référenc …   Wikipédia en Français

  • Boucle de Langton — La boucle de Langton est une structure autoréplicante d un automate cellulaire créée par Christopher Langton (en) en 1984[1]. Sommaire 1 Histoire …   Wikipédia en Français

  • Boucle de langton — La boucle de Langton est une structure autoréplicante d un automate cellulaire créée par Christopher Langton en 1984[1]. Sommaire 1 Histoire 2 Description 3 Notes et référenc …   Wikipédia en Français

  • 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… …   Wikipedia

  • 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

  • Von Neumann universal constructor — John von Neumann s Universal Constructor is a self replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann s book… …   Wikipedia

Share the article and excerpts

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