The Langton’s Ant

By Anupum Pant

Think of a cell sized ant sitting on a huge grid of such white cells. The thing to note about this ant is that it follows a certain sets of simple rules. The main rule is that when the ant exits a cell, it inverts the colour of the cell it just left. Besides that:

  1. If the ant enters a white square, it turns left.
  2. If it enters a black square, it turns right.

Here’s what happens if the ant starts out in the middle and moves to the cell on the right, as a starting step (this can be on any side).

First step, it goes to the right.
First step, it goes to the right.
Enters a white cell and rule 1 kicks in. The exited cell is inverted in colour and it turns left.
Enters a white cell and rule 1 kicks in. The exited cell is inverted in colour and it turns left.
Enters a white cell and rule 1 kicks in. The exited cell is inverted in colour and it turns left. (Again)
Enters a white cell and rule 1 kicks in. The exited cell is inverted in colour and it turns left. (Again)
Enters a white cell and rule 1 kicks in. The exited cell is inverted in colour and it turns left. (Again)
Enters a white cell and rule 1 kicks in. The exited cell is inverted in colour and it turns left. (Again)
Enters a black cell and rule 2 kicks in. The exited cell is inverted in colour and it turns right.
Enters a black cell and rule 2 kicks in. The exited cell is inverted in colour and it turns right.
Rule 1 again and so on...
Rule 1 again and so on…

Now as this continues, a seemingly random figure starts taking shape. The black cells are in total chaos, there seems to be no specific order to how they appear on the canvas. (of course the pattern is always the same chaos, considering the ant starts on a blank array of cells).

And yet, after about 10,000 steps are completed by the turing ant, it starts creating a very orderly highway kind of figure on the canvas. It enters an endless loop consisting of 104 steps which keeps repeating for ever and creates a long highway kind of structure.

Suppose, initially you take a configuration of black spots on a canvas (not a blank white canvas). Take an array of cells with randomly arranged black spots, for instance. If given enough time, the ant ultimately always ends up making the looped highway. However, before it starts doing it, it might take a significant amount of steps less, or more, than the ~10,000 steps it took to reach the loop in a blank array of cells.

No exception has ever been found. A computer scientist Chris Langton discovered this in the year 1986.