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$
1
  • $\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$ Jan 3, 2018 at 16:33

2 Answers 2

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.

$\endgroup$
0
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'

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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