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
 wend

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: http://www.annanardella.it/ant.html

This generalizes: you can have more possible colours of pixels, with turnings specified for each. See, for instance, http://www.math.sunysb.edu/~scott/ants/ and http://www.tiac.net/users/sw/LangtonsAnt/antlinks.html .

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.

That's not the point. It is "unpredictable" in the sense that there is no short cut to predicting it other than running the simulation, unlike other non-random but non-chaotic systems. Physics is a successful science largely because it has been able to predict without simulation. The newer branches of computational physics that depend on simulation are a sharp change.

Here, for reference, is the usual definition of chaos for a (continuous) dynamical system. A system is chaotic if:

It has sensitive dependence on initial conditions: there's some fixed distance such that given any point you can find arbitrarily close points whose iterates get at least that far away from those of the original point.
It is topologically transitive: there's some point whose iterates get arbitrarily close to all points.
- This is ergodicity, and absolutely is not characteristic of chaotic systems in general.

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

Sure they have. The first condition above works just fine with only a slightly modified interpretation of "sensitive dependence on initial conditions": Two arbitrarily-similar (but not identical) starting states can lead to arbitrarily-distant future states.

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

NickBensema wrote the original version of the Python program, now generalized somewhat.
MikeSmith told us of the name "Langton's ant" and the existence of generalized versions.
LeeNathan and RobertWatkins had an argument about whether the ant's behaviour is really "chaotic".

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:

 while(true) 
  move forward
  toggle pixel
  if pixel black, turn left  90 degrees
  if pixel white, turn right 90 degrees
 wend

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: http://users.iol.it/acnard/ant.html

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

 while(true)
  move forward
  rotate color
  if pixel white turn left 90 degrees
  if pixel black turn right 90 degrees
  if pixel gray reverse direction
 wend

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
      screen[position].toggle()
      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!):

 SCREEN 2
 DO WHILE INKEY$ = ""
 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
 LOOP

Behaviors emerge in chaotic systems which cannot be predicted by examining the inputs to the system or transformations caused by the system.

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.

TheDevilIsInTheDetails