2
$\begingroup$

I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless. So that is why I'm asking.

1) Is there a mathematical proof that the Langton's ant will stay forever on the highway once it's enter in it ?

2) Is there a proof that for only one initial condition the Langton's ant will always build the highway ?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 1) a quite informal proof is by "induction on the shape of the highway": after some steps (104 according to Mathworld site) the last portion of the highway is cloned (+2 pixels horizontally and +2 pixels vertically) and the ant is in the same relative position; so if there are no "obstacles" it will grow forever. 2) It is false: many initial conditions we can test generate a highway ...and -indeeed- the conjecture is "Does every finite initial configuration generates a highway?" (we only know, by the Cohen-Kung theorem, that for every finite initial configuration its trajectory is unbounded) $\endgroup$
    – Marzio De Biasi
    Apr 2, 2016 at 15:26
  • $\begingroup$ hi, thanks a lot for replying, in the 2nd question I'm referring to the basis of induction for proving the conjecture. If someone already proof if you put one square black anywhere the ant will make the highway.thanks again ;) $\endgroup$
    – Porufes
    Apr 2, 2016 at 18:26
  • 1
    $\begingroup$ ok! (you can specify that you're asking if it is known whether the ant always builds a highway if it is started on a board with another active "cell" at an arbitrary position) I'm not aware of such result ... and IMO it could be a nice "intermediate" result by itself; probably there are cases in which when the highway "hits" a block the ant goes back to the "root" of the highway (and the highway itself is messed up) ... I just made a few simulations with a short highway and it happens :-) $\endgroup$
    – Marzio De Biasi
    Apr 2, 2016 at 19:46
  • $\begingroup$ It's a few years old now, but Ian Stewart discusses a possible approach in 'Figments of Reality'. $\endgroup$
    – NietzscheanAI
    Apr 17, 2016 at 18:35

1 Answer 1

Reset to default
-1
$\begingroup$

There is an article on Langtons ant, published in the SCTPLS Newsletter ( Society for Chaos Theory in Psychology & Life Sciences Vol. 26, No. 2 February 2019 ) It introduces a first order recurrence relation for the cellular automata 'Langtons ant' A copy can be downloaded from

http://buzwordsalad.com/lit/SCTPLS_LAWE_bw.pdf

Improve this answer
$\endgroup$

Your Answer

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

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