Langton’s ant – a mysterious cellular automaton

There are about 14,000 ant species in the world, each of which has its own name. But, even if you set yourself such a goal, you will not find Langton’s ant in any biological reference book. The point is that this ant is a mathematical abstraction, a model for describing the behavior of a dynamical system. Sometimes it seems that mathematicians are not indifferent to ants at all – let’s recall the already classical ant algorithm. And in all kinds of logical models and problems, ants are quite common.

From chaos to strict order

Let’s get to know Langton’s ant better. He lives on an endless plane of white cells. He has two inexhaustible buckets – one with white paint, the other with black. The ant moves along the cells of the plane from one cell to another. At the same time, he performs a simple algorithm:

  1. If the cage is white, then the ant repaints it black, turns it 90 ° to the right (clockwise) and takes a step forward.

  2. If the cage is black, then the ant repaints it white, rotates it 90 ° to the left (counterclockwise) and takes a step forward.

That, in fact, is all. Langton’s ant has a sad life, but, as we will see, he is not ready to put up with such an outrageous situation and is trying with all his might to escape.

Writing a program that models the behavior of a Langton ant is not difficult. There are many examples of this algorithm implementation on the net: simpler and more difficult – with a set of additional settings.

Try to observe the movements of this ant along its checkered plane. At first glance, his steps are completely chaotic – no order is observed. But, to paraphrase a well-known saying, if you watch an ant for a long time, you can see how it runs away. Somewhere after 10,000 steps, the ant suddenly realizes the futility of being and makes an attempt to escape – it begins to build a periodic structure, every 104 steps move it two squares diagonally. After that, the steps are repeated. The ant’s behavior will never become chaotic – now it will continue to move along a wide diagonal strip-highway, consisting of black and white cells.

Langton's Ant Highway
Langton’s Ant Highway

This very sudden change in the behavior of Langton’s ant makes one wonder – how from a completely chaotic system a strict order is suddenly born ?! But our ant has an even more impressive property. What happens if, before the ant begins to move, paint a finite number of some of the cells adjacent to the starting point black? Will this change the behavior of the ant?

Ian Stewart’s book The Greatest Mathematical Problems gives a fascinating description of this experiment: “We can choose any cells for this: it can be a random set, a black square, or a Mona Lisa. There may be a million, or a billion, or even more, but not an infinite number. “

What will happen in the end? In all the experiments set up, the ant, wandering through the cages, sooner or later again began to build its highway using the same 104 steps. One gets the impression that the ant has a complex self-learning algorithm that eventually leads it to a regular repeating structure of steps. In fact, the algorithm is still the same – the two rules described at the beginning of the article. But the most interesting thing about this whole model is that mathematicians still do not know the answer to the following questions:

  1. Does the ant always move to orderly movement?

  2. If the answer to the previous question is yes, then is the highway of repeated 104 steps the only construction (“attractor”) that the ant eventually starts to build?

The only thing that mathematicians can say with certainty is that, regardless of the initial configuration of the cells, a freedom-loving ant will not remain forever in a closed area. American scientist Christopher Langton invented his ant back in 1984. Since then, no one has been able to explain the strange behavior of this mysterious model.

Langton’s ant modifications

Langton’s ant is essentially a cellular automaton, a regular lattice in which at each step the color of the cells changes according to a certain set of rules, usually depending on the color of neighboring cells. The most famous cellular automaton is the game “Life” by the English mathematician John Conway. Scientists have come up with many different cellular automata, but, perhaps, none of them can compare in mystery to our ant.

By the way, like other cellular automata, Langton’s ant has its own modifications. For example, sometimes our ant is loaded with buckets with additional paints. In this case, separate rotation rules are set for each color. You can also add other ants to the ant (each with a bucket of its own color) and see how they interact. There are also options with a hexagonal latticewhich uses six different turning options: no change, 180 °, 60 ° right, 60 ° left, 120 ° right, and 120 ° left.

Hexagonal Ant Highway
Hexagonal Ant Highway

You can also change the behavior algorithm of each ant in the system. To do this, they came up with a way to encode the algorithm in the form of a string of characters R – turn right and L – turn left. In this entry, each position corresponds to the color of the cell that the ant came to. For the classic Langton ant, the entry would be RL. Also, sometimes two more commands are added: C – to continue moving in the same direction (sometimes the letter F is used), U – to turn 180 ° (sometimes the letter B is used). Ants with altered behavior algorithms begin to behave in a completely different way – they no longer always build highways. Many of them immediately start to make symmetrical patterns. This is how, for example, ants with repeating pairs: LL and RR behave. For example LLRR.

Symmetrical ant pattern with LLRR rule
Symmetrical ant pattern with LLRR rule

You can use one of the ready-made programs or program this wonderful and mysterious system yourself and experiment with different options for its implementation. For ants, you can come up with new algorithms, change their number, the initial direction of movement and starting points on the plane. You can also experiment with the initial coloring of some cells on the plane. For example, a freedom-loving ant with the RL rule can successfully get out of a closed square.

Ant Trunk with RCCU Rule
Ant Trunk with RCCU Rule

For this cellular automaton, you can think of many modifications with different behavior, but the classic Langton ant, which we met, is still one of the unsolved problems of mathematics. I have always been amazed by such systems with the simplest formulations and inexplicable behavior. They remind us of how much we still do not know about the mathematical laws of the structure of our world. Perhaps solving such problems in the future will lead us to understand something more than the behavior of the simplest cellular automaton.

The article was first published on another resource on March 29, 2021.

Similar Posts

Leave a Reply