Please Place Your Ants On The Grid

Current Coordinates:   (0,0)

Number of Ants

 

Langton's Ant

Langton's ant is a type of cellular automaton, or a simple form of artificial life, named after its designer, Christopher Langton. The ant lives on an infinitely large chessboard, each square of which can be either black or white. Two pieces of information are associated with this digital insect: the direction that it's facing, and the state of the square that it's currently standing on. Furthermore, the ant's behavior is completely described by three simple rules:

  1. If it is on a black square, it makes a left turn and proceeds forward by one space.
  2. If it is on a white square, it makes a right turn and proceeds forward by one space.
  3. As it moves to the next square, the one it was on reverses color.

Interest in Langton's ant stems from the fact that despite being a completely determined system governed by such extremely simple rules, the patterns it produces are fantastically rich and complex. For example, with a single ant for the first 10,000 moves or so, the Ant meanders around, building and then unbuilding structures with little pattern to them. Then, near the end of this chaotic phase, the ant begins to construct a diagonal highway off toward one the edge of the board. In fact, this pattern stems from a sequence of 104 moves that, once started, will go on forever. In the language of chaos theory, the pattern is a stable attractor for the system. Remarkably, no matter what the initial arrangement of squares – even if the white and black squares are set up randomly – the ant will end up building a highway. The ant can be allowed to wrap around the edges of a finite board, thus allowing it to intersect its own path, and it will still end up building the highway. Are there any initial states that don't lead to the diagonal-road-building loop? No exceptions have been found from experiments – but proving it is quite another matter. Most mathematicians believe there is no general analytical method of predicting the position of the ant, or of any such chaotic system, after any given number of moves. Its behavior cannot be reduced to the rules that govern it. In this sense, Langton's ant is a very simple demonstration of the undecidability of the halting problem[1].

These simple, simulated ants, whose behavior is dictated by an extremely simple set of rules can, when they act collectively, exhibit some of the phenomena exhibited by large societies of much more complex organisms. From this example, we can begin to get an idea of the arbitrariness of the relationship that exists between some of the complex phenomena exhibited by living systems and their underlying hardware of implementation. In 'reality' these behaviors are just the result of the interactions of a specific kind of Virtual State Machine. The interpretation of their behavior as that of simu- lated ants resides entirely in our heads. Thus, this example can equally well be viewed as another example of an artificial biochemistry, based on the interactions of artificial molecular operators. By keeping the arbitrariness of our interpretations of these behaviors clearly in mind, we can see that complex, Virtual State Machine-like dynamics might be possible in any system that involves the interactions of many simple parts, be they systems at the molecular level or at the level of societies[2].

 

References:

[1] Darling,David. "Langton's ant". http://www.daviddarling.info/encyclopedia/L/Langtons_ant.html

[2] Langton, Chris G. (1986). "Studying artificial life with cellular automata". Physica D: Nonlinear Phenomena. 22 (1–3): 120–149. doi:10.1016/0167-2789(86)90237-X.