Langton's ant (and turmites)

Parent: famous-machines

A 2-D Turing machine with almost no rules, famous for emergent order out of chaos.

The rules. An "ant" sits on a grid of white/black cells:

• on a white cell: turn 90° right, flip the cell to black, step forward;
• on a black cell: turn 90° left, flip the cell to white, step forward.

The behaviour. From a blank grid the trajectory looks chaotic for ~10,000 steps, then — unexpectedly — settles into a periodic "highway": a repeating 104-step pattern that marches off to infinity forever. Nobody has a simple proof of why the highway always emerges; it's a striking case of order you can't predict except by running it (cf. the uncomputable-in-general behaviour).

It's universal. With suitable initial cell configurations you can build logic gates and wires from ant paths, so Langton's ant is Turing-complete — full computation from a two-line rule. Turmites generalize it to more states/colours and arbitrary turn-tables (a genuine 2-D read-write-move machine).