4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Adam P. Goucher Jan 3 '18 at 16:33
  • $\begingroup$ @AdamP.Goucher Thanks. Can you describe your intuition in more detail? $\endgroup$ – user76284 Jan 3 '18 at 19:49
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, I meant to ask whether the intermediate conjecture has been proven. I'll edit the question to make this clear. $\endgroup$ – user76284 Jul 22 '17 at 22:52
0
$\begingroup$

Not sure if this helps but there is a wave equation for langtons ant on a bounded surface, you could apply complex calculus to the lattice size 'E' in the equation and evaluate it over the limit of infinity. google 'langtons ant wave equation'

| cite | improve this answer | |
$\endgroup$

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.