Langton’s Ant is a simple non-trivial example of a class of machines called Cellular Automata (CA)1. CA exhibit surprising behaviours from the application of simple rules, and as such are an excellent test case for research into emergence and complexity. For an excellent description of this class of CA, see Further Travels With My Ant (Gale et al.). The ant traverses one cell of the lattice at a time and does two actions 1) increment/flip the state of the cell and 2) turn left/right depending on the state of the cell.
The algorithm for the ant can be generalized to a lattice with cells that have more than two states. Each state can then be visualized as a different colour.
We have written a simple application that runs a generalized Langton-like Ants with an arbitrary rule string. The simplest machine is one has a rule-string of 10, which is Langton’s Ant itself. For a K-state machine successive states of cells are shown as darker shading. You can type in any rule string of any length K to run a new K-state ant machine and see what it does.
An ant with rule 1111110 building a "road"
Try out a few different rule strings. Most of them produce a kind of random movement and produce no patterns, but even within those machines you’ll sometimes observe periods of regular behaviour when the ant will seem to exhibit some order (even “intent”?) in its movements. And then sometimes you’ll stumble upon a rule that produces beautifully ordered behaviour that persists over long times. Above is a screenshot of a 7-state Ant machine with rule string 1111110 that builds a diagonal road.
You can run the Ant Machine application from http://symmetri.com/flash/AntMachines.html.
1Actually it is a Turing machine, maybe not strictly a CA.