« June 19, 2017 | Main | June 24, 2017 »
Tuesday, June 20, 2017
Cellular Automata Laboratory: Langton's Ant
I have added another new rule to Cellular Automata Laboratory (CelLab): Langton's Ant. This rule was discovered by Christopher Langton in 1986, and is one of the simplest known moving-head Turing machine rules which exhibits complex behaviour.
It is a two-dimensional Turing machine with a head (ant) that moves on a map of cells which can be in one of two states. In each generation, the head moves to an adjacent cell, inverting the state of the cell it departs. The head can move in one of the four directions in the von Neumann neighborhood; the direction it moves is set by the current state of the head. Upon moving to a new cell, the head adjusts its direction by turning clockwise if the cell's state is zero and counterclockwise if it is one.
When started with an all-zero map, the head starts by tracing out a lacy pattern exhibiting symmetries, but then, as the pattern grows, appears to be following a random walk, occasionally adding to the borders of the pattern. After around 10,000 generations, however, the head will begin to create a “highway” which extends in a diagonal direction in a cycle of 104 generations. This is an example of spontaneous emergence of order after a long period of apparently chaotic behavior. If run on an infinite map, the highway would extend without bound, but on our wrap-around map, it will eventually collide with the original random pattern, producing interesting interactions. All starting configurations which have been tested eventually produce a highway, but it has not been proved that every possible configuration does so. It has, however, been proved that the pattern always grows without bound in some manner. Try starting the rule on the square pattern and watch how it evolves into a lattice of ordered highways and burl-like intersections.
Run the Langton's Ant rule in CelLab
Posted at
23:09
