3
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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). $\endgroup$
    – Marzio De Biasi
    Dec 14, 2012 at 22:22
  • $\begingroup$ You're right, I should have read the FAQ before posting. Thanks for the answer though :) (should I delete the post?) $\endgroup$
    – marsenis
    Dec 14, 2012 at 23:17
  • 1
    $\begingroup$ OK. You can convert it to an answer. $\endgroup$
    – marsenis
    Dec 15, 2012 at 10:25
  • 1
    $\begingroup$ 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... $\endgroup$
    – vzn
    Dec 15, 2012 at 18:37
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Dec 16, 2012 at 17:13

1 Answer 1

Reset to default
4
$\begingroup$

From the comment: 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ in other words/other way of looking at it: the undecidable versions of langtons ant mentioned in Gajardo et als paper complexity of Langton's ant set up an infinite initial configuration that creates an infinite array of cells repesenting a CA/cellular automata that the ant visits/computes. this special configuration guarantees the ant is locked into computing the contents of the infinite size CA cell array forever and provably never enters the "highway" state referred to in the conjecture for finite initial configurations. $\endgroup$
    – vzn
    Dec 15, 2012 at 18:57

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.