<p>From the comment: the undecidable questions are related to initial configurations with <strong>infinite support</strong>, whereas the conjecture refers to the behaviour of the ant when starting from a configuration with <strong>finite support</strong> (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.</p>

CC BY-SA 3.0
2012-12-15T18:57:16.240Z
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](http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf) 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
CC BY-SA 3.0
2012-12-15T11:41:21.353Z
2012-12-15T12:54:33.803Z
2012-12-15T12:54:33.803Z
Marzio De Biasi
<p>I was recently reading about <a href="http://en.wikipedia.org/wiki/Langton%27s_ant" rel="nofollow">Langton's ant</a> and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'.</p>

<p>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.</p>

<p>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?</p>

<p>I also read <a href="http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf" rel="nofollow">this paper</a> 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."</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-12-14T22:22:05.143Z
Not a true research question (see [FAQ](http://cstheory.stackexchange.com/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
CC BY-SA 3.0
2012-12-14T23:17:06.393Z
You're right, I should have read the FAQ before posting. Thanks for the answer though :) (should I delete the post?)
marsenis
CC BY-SA 3.0
2012-12-15T10:25:25.490Z
OK. You can convert it to an answer.
marsenis
CC BY-SA 3.0
2012-12-15T18:37:39.483Z
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
CC BY-SA 3.0
2012-12-16T17:13:05.487Z
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](http://en.wikipedia.org/wiki/Rule_110), see also [initial conditions for universal rule 110](http://cstheory.stackexchange.com/questions/11002/initial-conditions-for-universal-rule-110), tcs.se
vzn
CC BY-SA 3.0
2012-12-16T20:02:13.857Z
@Kaveh: I posted the comment as an answer yesterday, and it seems accepted ?!? :-)
Marzio De Biasi
CC BY-SA 3.0
2012-12-16T22:04:48.323Z
@Marzio, ah, sorry, I was [reviewing](http://cstheory.stackexchange.com/review) and didn't see your answer. :)
Kaveh
<computability><turing-machines><cellular-automata>
Langton's ant highway conjecture and undecidability
marsenis
# Langton's ant highway conjecture and undecidability

(Asked by: username_0 on 2012-12-14)

I was recently reading about [Langton's ant](http://en.wikipedia.org/wiki/Langton%27s_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](http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf) 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)?

**Tags:** computability, turing-machines, cellular-automata
> **Comments:**
> **username_1**: Not a true research question (see [FAQ](http://cstheory.stackexchange.com/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).  
> **username_0**: You're right, I should have read the FAQ before posting. Thanks for the answer though :) (should I delete the post?)  
> **username_0**: OK. You can convert it to an answer.  
> **username_2**: 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...  
> **username_2**: 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](http://en.wikipedia.org/wiki/Rule_110), see also [initial conditions for universal rule 110](http://cstheory.stackexchange.com/questions/11002/initial-conditions-for-universal-rule-110), tcs.se  
> **username_1**: @Kaveh: I posted the comment as an answer yesterday, and it seems accepted ?!? :-)  
> **username_3**: @Marzio, ah, sorry, I was [reviewing](http://cstheory.stackexchange.com/review) and didn't see your answer. :)  

---

## 1 answers

### Answer by username_1 on 2012-12-15. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_2**: 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](http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf) 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.  

---

