# Intermediate results for Langton's ant highway conjecture

This paper states the following theorem about Langton's ant:

The set of cells that are visited infinitely often by the ant (for a given initial configuration) has no corners. A corner of a set is a cell where at least two neighbors are not in the set, and these are not opposite to each other.

This would imply that every cell that is visited infinitely often has at least 3 neighbors that are visited infinitely often. The paper cites the following source:

S. Troubetzkoy, Lewis–Parker Lecture 1997 The Ant, Alabama Journal of Mathematics.21(2) (1997).

I have not been able to find this source anywhere. Does anyone have access to the proof?

Furthermore, has the following extension of this theorem been proven?

The set of cells that are visited infinitely often by the ant is empty.

The theorem that the ant's trajectory is unbounded implies

$$\limsup_{t \rightarrow \infty} r_t = \infty$$

where $r_t$ is the distance of the ant from the origin. The above conjecture would imply that

$$\liminf_{t \rightarrow \infty} r_t = \infty$$

as well.

EDIT: Langton's ant conjecture appears to be comparable in difficulty to the famous Collatz conjecture. Has any relationship between these two problems been proven?

• In response to your post-scriptum: Langton's ant conjecture and the Collatz conjecture are both $\Pi^0_2$ statements: for all inputs $X$, there exists a time $T$ at which the process 'halts'. If you generalise these two problems appropriately, they're both $\Pi^0_2$-complete. I intuitively suspect Langton's ant is the easier of the two problems. – Adam P. Goucher Jan 3 '18 at 16:33
• @AdamP.Goucher Thanks. Can you describe your intuition in more detail? – user76284 Jan 3 '18 at 19:49

Yes that is a conjecture which follows from a more specific one: For any initial conguration with finite support, the ant eventually starts building the periodic highway, in some unobstructed direction. Here "the highway" is a certain periodic pattern with a drift. If that is true then there are integers $M,N$ so that only finitely many cells are visited more than $M$ times and none are visited more than $N$ times.