Six Line Ant Program

A program that does the following:

 while true:
   move forward
   toggle pixel
   if pixel black, turn left  90 degrees
   if pixel white, turn right 90 degrees
has surprisingly complex behaviour: it looks random to the human eye for a long time, and then ... something really cool emerges.

See it in action here:

This generalizes: you can have more possible colours of pixels, with turnings specified for each. See, for instance, and .

The original 2-state ant is called "Langton's ant", after its inventor Chris Langton.

The ant is deterministic but chaotic, meaning it has sensitive dependence on initial conditions: there is no way to predict a future state of the grid without explicitly running the simulation. Note that this is different than random. On the other hand, non-chaotic diagonal "highways" reliably emerge from the chaos (although exactly when and where they emerge is still chaotic, not predictable). This is not uncommon for chaotic systems.

LangtonsAnt? is a kind of CellularAutomaton. (EditHint: perhaps some of the discussion below about the difference between "random", "chaotic", "deterministic", etc., that applies to all CellularAutomata, not just this one, should be moved to the CellularAutomaton page).

Here's a PythonLanguage program that implements Langton's ant:

 turnings = [1,3]
 while 1:
     position += displacement
     screen[position] = (screen[position]+1) % len(turnings)
     displacement *= 1j**turnings[screen[position]]

Just add more elements to turnings to get the generalized version. You also need a suitable class for the screen object, of course. This program uses the insight that ComplexNumbersArePoints.

Random? Chaotic?

The early behaviour of the ant was described as appearing "random", which it does, but it isn't technically random.

"Chaotic" is not the same as "random", nor is it the same as "unpredictable". Consider, for instance, the LogisticEquation? x := kx(1-x); I believe (but haven't proved) that there are rational values of k for which the dynamics for rational x are chaotic. For all that, the iterated values can be calculated exactly as far out as you like, given only sufficient computer power. Here, for reference, is the usual definition of chaos for a (continuous) dynamical system. A system is chaotic if:

(A third condition ("periodic points are dense") is sometimes added.)

For cellular automata like Langton's ant, so far as I know no one has ever given a precise definition of "chaotic", though the term gets bandied about quite a bit in the literature. Incomprehensible?

It appears that whatever the initial configuration, the ant always ends up with the same sort of behaviour: "building a highway". (Run it and see.) So far as anyone on Wiki knows, there is no known proof that this always happens. Perhaps there is no proof? Perhaps it isn't even really true? It is alleged that PaulErdos tried to prove it and failed.

[Can anyone support the reference to Paul Erdős? I thought that story related to a different iteration-related problem.]

Refactoring notes:

Credits (delete yours if you're as happy without it):

Original content of page follows, below the double line. Some time early in May I'll delete it unless there are loud objections.

Write a program that does the following:

  move forward
  toggle pixel
  if pixel black, turn left  90 degrees
  if pixel white, turn right 90 degrees
For any initial configuration, this program does seemingly random behavior for a long time before something (the same thing regardless of the initial configuration) really cool emerges. It's conjectured to be chaotic, but this hasn't been proven yet. (cf. ChaosTheory)

See it in action here:

Idea: 3 states of pixel(white,gray,black)

  move forward
  rotate color
  if pixel white turn left 90 degrees
  if pixel black turn right 90 degrees
  if pixel gray reverse direction

Actually, if I recall correctly from a ScientificAmerican article from several years ago, the above algorithm is only one special case of a generalized class of state machine-based matrix traversal algorithms called LangtonsAnt? (actually Langton's Ant). I used to have a program lying around that would implement randomly-generated LangtonsAnt? machines; I'll have to look around for it. -- MikeSmith

Attempt to do some of this in PythonLanguage; the part described by the algorithm can be done in five lines: (PerlGolf, anyone?)

  while 1:
      position += displacement
      if screen[position]: displacement *=  1j
      else:                displacement *= -1j
Python has ComplexNumbers support, and this program assumes ComplexNumbersArePoints. All it needs is a proper class for the screen object.

-- NickBensema

Here is a program that dus that on QBASIC, on a finite grid insted uv infinite (so it dus stuf with the borders!):

 DRAW "a" + STR$(a) + "bu1"
 x = POINT(POINT(0), POINT(1))
 PSET STEP(0, 0), 1 - x
 a = (a + 4 + x + (x = 0)) MOD 4

PaulErdos tried and failed (Mathematics isn't ready for this yet.), but that doesn't mean anything. Langton's ant is merely conjectured to be chaotic, but not proven so. This is meant in a formal way, in the particular formal meanings of conjecture and prove.

There are bigwig mathematicians who are experts in this, and they say that LangtonsAnt? is chaotic.

I would like to suggest that in fact "Predicting the outcome by running the simulation" is not a prediction at all -- because it's not actually a "simulation", it's the entire universe of the domain. To predict it, you'd need a statistical measure based on observed characteristics. Kind of a PermutationCity sort of problem.


View edit of January 20, 2009 or FindPage with title or text search