So Langton's ant is a two dimensional Turing machine of utter simplicity.
It starts out on an infinite square grid. Each square starts off white and can be either white or black. The ant starts on one square facing south and repeats this simple rule:
If on a blank square turn 90degrees clockwise otherwise turn 90degrees counterclockwise, then flip the color of the square from white to black or black to white, then move forward one square.
What it does is quite surprising, taking a long time to create a complex pattern:
http://www.youtube.com/watch?v=1X-gtr4pEBU
It wanders around higgledy piggledy for 9978 steps and then executes a repeating pattern of length 104 which shifts over diagonally each time to produce an endless highway.
We can certainly build a simple mechanical device to do this. I bet we can even build a protein to do it on a regular face of a crystal, or we can maybe even find a medium sized molecule out there that already does this?
At any rate at first i thought it was odd that this seemingly symmetrical rule produces such an asymmetrical pattern. But then i realized that the initial conditions are not symmetrical! They start off all white.
So I decided to try the ant on some different initial conditions. If i start it on a grid that is alternating black and white stripes or checkerboard pattern of black and white (which i suppose we could think of as more symmetrical initial conditions) the ant surprises me. It simply executes a boring straight line! horizontal for horizontal stripes and diagonal for checkerboard. HUH
The other patterns are for other initial conditions. if i start the ant with initial random black and white squares of equal probability it wanders aimlessly faster than on all white and hits the wall rather quickly (at this point my program halts). If I start the ant with a space scattered sparsely with random black squares it tries to do the usual ant thing but keeps getting side tracked!
This is interesting. So the endless highway is not stable to perturbation. It seems it will eventually form from any initial state of a small area of randomness but any non white region larger than that small initial area can perturb it. and of course my stripe, checkerboard and total randomness initial conditions totally negate it.
I think my next step is to watch this ant on toroidal surfaces of various numbers of squares.
Saturday, December 28, 2013
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment