Langton's loops - AbsoluteAstronomy.com

Langton's loops are a particular "species" of artificial life

Artificial life

Artificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...

in a cellular automaton

Cellular automaton

A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...

created in 1984 by Christopher Langton

Christopher Langton

Christopher Langton is an American computer scientist and one of the founders of the field of artificial life. He coined the term in the late 1980s when he organized the first "Workshop on the Synthesis and Simulation of Living Systems" at the Los Alamos National Laboratory in 1987.Langton made...

. They consist of a loop of cells containing genetic information, which flows continuously around the loop and out along an "arm" (or pseudopod

Pseudopod

Pseudopods or pseudopodia are temporary projections of eukaryotic cells. Cells that possess this faculty are generally referred to as amoeboids. Pseudopodia extend and contract by the reversible assembly of actin subunits into microfilaments...

), 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

John von Neumann

John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...

created the first cellular automaton (CA) with the goal of creating a self-replicating machine. This automaton was necessarily very complex due to its computation- and construction-universality. In 1968 Edgar F. Codd

Edgar F. Codd

Edgar Frank "Ted" Codd was an English computer scientist who, while working for IBM, invented the relational model for database management, the theoretical basis for relational databases...

reduced the number of states from 29 in von Neumann's CA to 8 in his

Codd's cellular automaton

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

. 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

Von Neumann neighborhood

In cellular automata, the von Neumann neighborhood comprises the four cells orthogonally surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after John von Neumann, who used it for his pioneering cellular automata including the Universal Constructor...

with rotational symmetry. The transition table

State transition table

In automata theory and sequential logic, a state transition table is a table showing what state a finite semiautomaton or finite state machine will move to, based on the current state and other inputs...

can be found here: http://code.google.com/p/ruletablerepository/.

As with Codd's CA

Codd's cellular automaton

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

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

Coral

Corals are marine animals in class Anthozoa of phylum Cnidaria typically living in compact colonies of many identical individual "polyps". The group includes the important reef builders that inhabit tropical oceans and secrete calcium carbonate to form a hard skeleton.A coral "head" is a colony of...

-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

Asymptote

In analytic geometry, an asymptote of a curve is a line such that the distance between the curve and the line approaches zero as they tend to infinity. Some sources include the requirement that the curve may not cross the line infinitely often, but this is unusual for modern authors...

, 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

DNA replication

DNA replication is a biological process that occurs in all living organisms and copies their DNA; it is the basis for biological inheritance. The process starts with one double-stranded DNA molecule and produces two identical copies of the molecule...

the genome into the daughter loop. Clearly, this is dependent on the fourfold rotational symmetry

Rotational symmetry

Generally speaking, an object with rotational symmetry is an object that looks the same after a certain amount of rotation. An object may have more than one rotational symmetry; for instance, if reflections or turning it over are not counted, the triskelion appearing on the Isle of Man's flag has...

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

Icosahedral symmetry

A regular icosahedron has 60 rotational symmetries, and a symmetry order of 120 including transformations that combine a reflection and a rotation...

adenovirus.

Comparison of related CA loops

CA	number of states	neighborhood Neighbourhood (graph theory) In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...	number of cells (typical)	replication period (typical)
Langton's loops (1984): The original self-reproducing loop.	8	von Neumann	86	151
Byl's loop Byl's loop The Byl's loop is an artificial lifeform similar in concept to Langton's loop. It is a two-dimensional, 5-neighbor cellular automaton with 6 states per cell, and was developed in 1989 by John Byl, from the Department of Mathematical Sciences of Trinity Western University.- Details :The Byl's loop... (1989): By removing the inner sheath, Byl reduced the size of the loop.	6	von Neumann	12	25
Chou-Reggia loop (1993): A further reduction of the loop by removing all sheaths.	8	von Neumann	5	15
Tempesti loop (1995): Tempesti added construction capabilities to his loop, allowing patterns to be written inside the loop after reproduction.	10	Moore	148	304
Perrier loop (1996): Perrier added a program stack and an extensible data tape to Langton's loop, allowing it to compute anything computable Computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register... .	64	von Neumann	158	235
SDSR loop (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 (1999): An extension of the SDSR loop, Evoloop is capable of interaction with neighboring loops as well as of evolution Evolution Evolution is any change across successive generations in the heritable characteristics of biological populations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins.Life on Earth... . Often, the greatest selection pressure in a colony of Evoloops is the competition for space, and natural selection Natural selection Natural selection is the nonrandom process by which biologic traits become either more or less common in a population as a function of differential reproduction of their bearers. It is a key mechanism of evolution.... favors the smallest functional loop present. Further studies demonstrated more complexity than originally thought in the Evoloop system.	9	von Neumann	149	363
Sexyloop (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	?	?

External links

Video of Chris Langton demonstrating self reproducing loops.
visual representation of several of the self-replicating loops in a Java applet
Java applet
A Java applet is an applet delivered to users in the form of Java bytecode. Java applets can run in a Web browser using a Java Virtual Machine , or in Sun's AppletViewer, a stand-alone tool for testing applets...
The Rule Table Repository has the transition tables for many of the CA mentioned above.
Golly - supports Langton's Loops along with the Game of Life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

, and other rulesets.