0

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.

Peter Kagey
  • 5,052
mtheorylord
  • 4,274
  • 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? – David G. Stork Oct 26 '19 at 01:34
  • 1
    Wikipedia suggests that the unboundedness of Langton's ant is known as the Cohen–Kong theorem or the Cohen–Kung theorem. – Peter Kagey Oct 26 '19 at 01:45
  • 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. – Ilkka Törmä Oct 26 '19 at 10:03
  • A simple proof is given [here] (http://www.angelfire.com/ms/tushar/chtheorem.html). I've just read through it quickly, but it feels correct. – saulspatz Oct 18 '20 at 18:24

1 Answers1

-2

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).

Graham

Community
  • 1
graham medland
  • 27
  • 4
  • 1
    This could be a fine answer if more details were given and you used MathJax to render the variables appropriately. – Integrand Oct 03 '20 at 21:18