A program that does the following:

Here's a PythonLanguage program that implements Langton's ant:*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.
**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):

Write a program that does the following:*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)

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

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

*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

whilehas 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).true: move forward toggle pixel if pixel black, turn left 90 degrees if pixel white, turn right 90 degrees wend

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

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

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

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

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

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 wendFor any initial configuration, this program does seemingly random behavior for a long time before something (the

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 *= -1jPython 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.

TheDevilIsInTheDetails

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