Langton's loops
From Wikipedia, the free encyclopedia
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.
Contents |
[edit] History
In 1947 John von Neumann 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.
[edit] 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.
[edit] 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.
[edit] Related organisms
[edit] Evoloop
The Evoloop is a modification of Langton's loop 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.
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 or chimera daughter loop. This conjugation, however, is not particularly useful for evolutionary purposes, as the daughter organisms are usually incapable of reproduction.
[edit] SDSR Loop
The SDSR (Structurally Dissolvable Self-Reproducing) loop is a variant of Langton's loop that has a limited lifetime, and dissolves at the end of its life cycle. This allows continuous growth, whereas Langton's original loops' population is limited by the available space.
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.
[edit] SDSR Evoloop
In the case of SDSR Evoloops, which have both the ability to evolve and a limited life span, it is possible for a simulated ecosystem to emerge.
