Langton’s Ant

An ant moves on a regular grid of squares that are coloured either black or white.
The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves from square to adjacent square according to the following rules:
– if it is on a black square, it flips the colour of the square to white, rotates $90$ degrees counterclockwise and moves forward one square.
– if it is on a white square, it flips the colour of the square to black, rotates $90$ degrees clockwise and moves forward one square.

Starting with a grid that is entirely white, how many squares are black after $10^{18}$ moves of the ant?

This is actually the question of Langton’s Ant, a cellular automaton. However, it’s a bit tricky to solve for a huge number of moves like 10^18 directly.

First, some known aspects about Langton’s Ant:

1. The ant initially seems to move in a seemingly random pattern for about 10,000 steps until it starts building a ‘highway’ or a repeated pattern (a ‘caterpillar’) which leads it to move in a looping pattern.

2. After the initial chaos, the ant aligns itself into the highway mode, in which it follow a cycle of 104 steps which could be visualized like a tube.

Now let’s disassemble the problem.

10^18 moves are too big to consider directly. But we can reduce it into pieces, by knowing that the ant will enter the cyclic ‘highway’ mode after approximately 10,000 steps. So we subtract this from our initial number of steps, leaving us with approximately 10^18 steps.

But these are not all moving in random. A large amount of these will be in the ‘highway’ pattern. Every 104 steps, the pattern or the ‘highway’ repeats. Therefore, out of the remaining ~10^18 steps, we can segregate ~(10^18 / 104) ‘highways’.

This calculation gives us ~9.615 * 10^15 cycles and a remainder of 64. With each cycle, it’s known that the ant adds 12 new black cells to the configuration. Therefore, the total count of black cells after it finishes the highway cycles should be ~1.153 * 10^17.

Now the only concern remains the first ~10,000 steps and the remaining 64 events that aren’t part of a complete cycle of the highway.

We have no other option than to simulate these steps as there is no known pattern. But common algorithms can simulate thousands of steps quite quickly.

Now to answer this question exactly, we would need to find out exactly when does the ant first start building the ‘highway’. It is very difficult to compute the exact number of black squares, due to the chaotic nature of the ant’s movement, but if you have a computational simulation, you can run it for the first few thousand steps to get an empirical answer.

That answer would be approximated, as the real answer mathematically is probably not computable in a reasonable time due to the nature and scale of the problem.

More Answers: