Chaotic ant

[Starman]

Please can anyone tell me where I may have read this.

The ant was somebody's invention. It walks forever over an infinite chessboard. Whenever it lands on a white square it changes the square to black and turns right. Whenever it lands on a black square it changes the square to white and turns left.
I think it was just a short introduction to a chapter on random walks.

Where did I read it ?, Who's ant was it ?

[jim mcnamara]

The ant eventually leaves the chessboard, unless the board is infinite.

It was part of the Life/Chaos theory business. I first saw it in Scientific American - Ian Stewart's column, I think. Could be wrong. About 1993 - 1994.

However, it was interesting enough for me to write this "ANT" code in Turbo C about 1993 or so:

[Starman]

Thanks for the reply Jim, I have read the description more recently and I'm certain it was in a book. Fairly definitely one from the 'popular science' section. It's probably one I borrowed from the library as I can't find it in any that I have at home.

I got the feeling that what I read was just a brief description and that there was more information available, but I've forgotten who the mathematician/theorist was (not the book's author but the ant's creator).

I've been looking at it as a way of encrypting text. Convert the characters into binary, place a white square where there is a 1, a black square where there is a 0 and let the ant loose for a while. It really messes up the text and it is reversable (with a four part key).

Where did I put that book ?

[Starman]

Whoo!! I've been promoted again.
It says I'm addicted now - I'll have to try to control it or book myself into a cyberclinic or something

[Starman]

Thanks wossname!

Langton's ant.

I have found many references on the web now I know what it's called.

Still not sure where I read it but it was the name I was chiefly needing.

[wossname]

Glad to be of assistance

[JaredM]

Isn't it kind of pointless?

[wossname]

Oh dear, oh deary deary me!

It seems we have stumbled upon a heathen! heh heh.

No, seriously though, its not pointless because it is a good example of how unimagineable complexity can arise from extremely simple rules, like "If you are standing on a black square then turn right and step forward" etc...

It is thought (up to now no-one has disproven it) that the ant will ALWAYS build a highway eventually, even if the "infinitely large chessboard" has patterns on it before the ant starts. For example if you scatter 1000 black squares at random, then the ant will obviously abandon its standard path and do what comes naturally for the new situation. The clever thing is, that you cannot possibly say for certain where the ant will be in 100000 moves time unless you follow it through every single intermediate step.

Another thing in the same category is Cellular Automata, you have the same chessboard, but instead of an ant you simple have a cluster of black squares. At each iteration, each square counts how many of its neighboring squares are black and then based on this number, decides what colour it wants to be at the next iteration.

If the number is 0, 1, 4, 5, 6, 7, 8 then the square goes white.
If the number is 2 then the square stays as it is.
If the number is 3 then the square goes black, alive!

Try it and you'll see some weird evolving communities of shapes, some even glide around the screen, some oscillate and some get stuck in loops.

Check it out!

[JaredM]

I think AI makes for better observation then a simple decision making program based on some random numbers.

I understand the experiment, but it's so obvious. If you add infinity to anything it instantly become complex, and unfathomable. I hope no one is aclaiming him a genious for this.

[JaredM]

Count to infinity.

I dare ya. Math can't quantify it, all of it is theory. How do you prove it beyond the self containing system?

"I proved it in an imaginary system that is used for measurement! Whahaha!"

[Starman]

wossname,
When you say "the ant will ALWAYS build a highway eventually" would this still be true if the grid was bounded, ie when the ant travels over one edge it appears on the opposite side, or if the ant bounced back from an edge like a billiard ball?

I have found many references on the web, most of them having java applets which are relaxing to watch, but contain little information apart from the rules for each step. You seem to have studied this in some depth.

[simonm]

Check this out:
Cellab
Click on the link and down load the program Cellab.exe

You can load a variety of pre-made patterns and apply different rules on them and watch compexity emerge or self-organise.

[wossname]

Starman, in all my experiments with it, the ant always does it in any shape of container. All 3 stages of its behaviours (outlined in an above posting by me) can be witnessed before the ant leaves a 160 x 160 square grid (thats how big the screen on my Palm IIIx is!). An interesting effect happens when it hits the edges of the screen (this is likely to vary from type to type of computer). The program I posted above uses the pixel values of the screen as the working memory, when it tries to find out the colour of a pixel that doesn't exist (outside the screen) that function always returns 0, so the ant will run up and down the sides of the screen, and it eventually starts another region of chaos in one of the corners. Then it does another highway after a few thousand more iterations. I left my old Atari ST running overnight with this program and the screen was full of chaotic blobs and highways between them!

If you have many ants on the same screen (50 or so) and two of the ant's patterns collide, sometimes the ant will retrace all of his own moves and will destroy all his hard work and will wind up back where he started. Both ants will continue to go back and forth in this looping condition until another ant disturbs the pattern!

Bizarre.