Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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). –  Marzio De Biasi Dec 14 '12 at 22:22
    
You're right, I should have read the FAQ before posting. Thanks for the answer though :) (should I delete the post?) –  marsenis Dec 14 '12 at 23:17
1  
if you want I convert my comment to an answer and you can accept it. –  Marzio De Biasi Dec 15 '12 at 0:38
1  
OK. You can convert it to an answer. –  marsenis Dec 15 '12 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 '12 at 18:37
show 3 more comments

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  vzn Dec 15 '12 at 18:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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