Langton's Loops

In 1984 Christopher Langton of Langton's Ant fame created another cellular automata which was capable of reproducing itself using only simple rules. Cellular automata are any collection of spaces (usually arranged as a 2D grid of squares) where each space can take one of several states. Each time click forwards allows each space to update itself based on the values of the cells around it. Conway’s Game of Life is by far the most famous, but apart from Langton’s Ant from above and Rule 110, Langton’s Loop is probably the next most famous.

In essence Langton’s Loop was a vast improvement on several other loop designs starting with John von Neumann’s in 1954. It had 8 different states, each of which we will represent with colour and designate with a number. Here it is in its initial form:

The black 0s are the dead space around the loop in which it will grow, while 1 and 2 act as wires, with the 1 propagating signals like copper and the red insulation of 2 isolating it from the outside world.

The light blue 7s turn surrounding dark blue 1s into themselves while, in the same time click, the original 7 will die back to black. Simulatanously the black 0 behind them will be upgraded back into wire. The net result of this is that 11107111 turns into 11110711, the information has propagated itself. In a similar way it is able to navigate the corners of the loop. When two 7 signals get to the open end of the loop they have the net result of extending it out.

The loop contains six 7s and then two 4s. The result is that it extends straight outwards and then turns 90 degrees anticlockwise on the instruction of the 4s. This pattern of 7s and 4s keeps going around the loop and so the instruction is repeated until all four sides of the new loop have been created.

The other states are used to move on to making new loops. Once a parent loop has created a fully formed child a signal of 5 gets sent to the parent to tell it to rotate 90 degrees and start creating a child on another side. 6 is similar, telling the child to also rotate and move on to making its on children.

Once a loop has used its genome 6 times: once to make an arm, once for each of the four sides of its child and once to transfer the genome to its child (its clone, this is asexual reproduction) it then turns to make the next child. Once all four children are complete the parent will die, leaving only a spiral shell and an empty genome. The whole thing spirals out around a dead middle (like the cross section of a tree trunk).

There have been various improvements on this design (mostly during the 90s). Of particular interest to me is Evoloop which is frankly amazing. More to follow on this once I have had a play around.

Edit: The follow up is here.