Suppose I have a grid of black/white squares (not necessarily all white). How can I prove that Langton's ant is unbounded when it runs on this initial condition?

It seems as though the way to go about this is noting that if it were bounded, it's periodic and achieving a contradiction by looking at the neighbours of the initial square. However, this approach hasn't worked so far for me.

  • $\begingroup$ So why don't you explain what Langton's ant is? Do you honestly believe everyone who could answer this question here knows about it? $\endgroup$ Oct 26 '19 at 1:34
  • 1
    $\begingroup$ Wikipedia suggests that the unboundedness of Langton's ant is known as the Cohen–Kong theorem or the Cohen–Kung theorem. $\endgroup$ Oct 26 '19 at 1:45
  • $\begingroup$ Hint: if a configuration was periodic, there would be a cell that the ant visits, but doesn't visit any cell to the north or east of it. $\endgroup$ Oct 26 '19 at 10:03
  • $\begingroup$ A simple proof is given [here] (angelfire.com/ms/tushar/chtheorem.html). I've just read through it quickly, but it feels correct. $\endgroup$
    – saulspatz
    Oct 18 '20 at 18:24

Using dimensionality reduction Turn the lattice into a single dimensional array, iterate the "Langtons ant wave equation" and observe that a) Langtons ant is created and b) $\Psi_\vartriangle$ is indeed a 1D array and look at the variable $k$, a plot of this can be seen in my group on linkedin 104 unbounded highway since this highway is a recurrence relation you can show by telescoping the index $t$ into the index $k$ into the array $\Psi_\vartriangle$ is unbounded in the limit as long as the size of the lattice $E^2$ is taken to the limit of infinity (Calculus).


  • 1
    $\begingroup$ This could be a fine answer if more details were given and you used MathJax to render the variables appropriately. $\endgroup$
    – Integrand
    Oct 3 '20 at 21:18

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.