How Random Is Spatiotemporal Chaos of Langton's Ant?¹

In recent years there have been numerous attempts to control chaotic behavior by evolutionary optimization. Most of these attempts were aimed at a study of chaotic systems defined by differential equations, but a few attempts were made also at evolutionary design of initial conditions or rules of cellular automata aimed at performing a specified task. We shall use a simple cellular automaton called Langton's ant after its designer, Christopher Langton. Generally, the ant acts on a 2D grid, where each it’s square can be either black or white. The ant is facing in one of four directions, and its behavior is described by 3 rules: (1) If ant is on a black square, it makes a left turn. (2) If ant is on a white square, it makes a right turn. (3) When ant moves to the next square, the one it was on reverses color. Despite simplicity of these rules, the ant produces extremely complex behavior, but after around 10000 steps the ant begins to construct a diagonal „highway“. This stable attractor has been always achieved regardless of the initial setting of black and white squares, but there is no proof, that it is always so. This behavior can be related to the undecidability of the halting problem. Our goal in this paper is to optimize initial conditions for the ant on a grid, so that it will be maximally “slowed down” in the sense that it should arrive at the preset boundary of the grid as late as possible. By a comparison of greedy stochastic optimization with an optimization by blind search are able to estimate, that is this chaotic system is not reasonably controllable and appears to have no regularity in the “optimal” initial conditions.