Prior1986
Langton’s ant
Christopher Langton — two lines, and an open problem
Published in 1986 inside a paper on cellular automata by the man who a year later gave the field of artificial life its name. The rule is two lines long and there is nothing else in it.
the rule, entire
white: turn right, flip the square, step black: turn left, flip the square, step
One ant. An unbounded grid, every square white. No randomness anywhere — not in the rule, not in the start, not in the order of anything. Run the same setup twice and you get the same picture, to the square, forever.
For about five hundred steps it makes small symmetrical figures. Then it stops doing that, and for something near ten thousand steps it produces a spreading region that no one has been able to describe as anything but noise. Then, with nothing marking the transition, the ant begins building a corridor: a repeating pattern of one hundred and four steps, laid diagonally, which it travels outward along and never leaves.
The corridor is not in the two lines. It has appeared from every starting configuration anyone has tried, including ones seeded with black squares scattered at random, and it has never been proved that it must. That the ant’s path is unbounded was settled in 1992. The road was not.
The rule contains no chaos and no road. The only way to find out what it does is to let it run.