4
$\begingroup$

I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

$\endgroup$
8
$\begingroup$

The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

  1. The path of the ant is (ultimately) periodic if and only if it is bounded. (Clearly, an unbounded path cannot be periodic. Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)
  2. Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical. To return to a particular square after once leaving it, the ant must travel an even number of steps. Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path. (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can. Since the ant's path is, by assumption, bounded, this process will always terminate.) Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left. But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.

$\endgroup$
  • 1
    $\begingroup$ @ruakh: To do that, the ant would have to make an odd number of turns between entering that square the first time and entering it the next time. But to return to the same square, the ant must travel an even number of vertical steps and an even number of horizontal steps, making an even number of steps in total. And the ant turns exactly once after every step. $\endgroup$ – Ilmari Karonen Jul 23 at 4:37
  • $\begingroup$ Oh, oops, I get it now -- you explained that in your point #2. Thanks! $\endgroup$ – ruakh Jul 23 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.