patternMinor
Langton's Ant Periodic Behavior
Viewed 0 times
periodiclangtonbehaviorant
Problem
I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?
Solution
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:
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.
The proof is fairly simple, as the result follows directly from the following observations:
- 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.)
- 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.
Context
StackExchange Computer Science Q#112075, answer score: 8
Revisions (0)
No revisions yet.