# Langton's ant highway conjecture and undecidability

I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'.

I also read that it has been shown that Langton's ant can be used to simulate any boolean circuit thus the ant is capable of universal computation.

But I am confused by those two facts because if the conjecture is true, then every computation performed by the ant will eventually end up to a highway which is easily detectable thus making any problem related to Langton's ant decidable. But how can this be true if Langton's ant is computationaly equivalent to a Turing machine for which there exist many undecidable problems?

I also read this paper and it specifically says in section 1.2: "If the conjecture is true, then any problem associated to the ant, whose input is an initial configuration with finite support, is decidable" whereas in section 1.3 it states: "There are undecidable problems associated to the behavior of the ant."

I suspect that my confusion on the matter has something to do with the finiteness/infiniteness of the input since in section 4 of the previous paper it says that Langton's ant universality is "a rather weak notion of universality (which requires an infinite - but finitely described - configuration)" which I'm not entirely sure I understand.

So my question is what's wrong with the above reasoning which suggests that the highway conjecture should be false (otherwise there would be no undecidable problems)?

• Not a true research question (see FAQ); however the undecidable questions are related to initial configurations with infinite support, whereas the conjecture refers to the behaviour of the ant when starting from a configuration with finite support (all but a finite number of cells are in the same initial state). If the conjecture is true then there are no undecidable problems starting from a finite support (just stop when the ant starts building the highway towards empty space). Dec 14, 2012 at 22:22
• You're right, I should have read the FAQ before posting. Thanks for the answer though :) (should I delete the post?) Dec 14, 2012 at 23:17
• OK. You can convert it to an answer. Dec 15, 2012 at 10:25
• to me this question is research level & also feel the wikipedia writeup is not very good/precise right now leading to reasonable confusion. simulating any circuit is not the same as Turing completeness ("universal computation") because circuits are finite size & can simulate any Recursive fns and Turing completeness equals computation of Recursively Enumerable fns & the current wikipedia article doesnt distinguish this distinction very well...
– vzn
Dec 15, 2012 at 18:37
• fyi also note this issue of Turing-completeness wrt finite vs infinite initial configurations also shows up in cellular automata research & the Cook proof of the Turing completeness of rule 110, see also initial conditions for universal rule 110, tcs.se
– vzn
Dec 16, 2012 at 17:13