It is well known that the [elementary cellular automaton](http://mathworld.wolfram.com/ElementaryCellularAutomaton.html) known as [rule 110](http://en.wikipedia.org/wiki/Rule_110) is Turing complete.


Its cousin [rule 30](http://mathworld.wolfram.com/Rule30.html) also produces complicated behaviour. When I read Wolfram's *a New Kind of Science* (in which these rules are defined), I vaguely recall his opinion being that rule 30 probably isn't Turing complete, because its behaviour is "too chaotic" - you tend not to get the localised regions of order that can be found in the dynamics of Rule 110, which probably makes it impossible for it to simulate a Turing machine in the same way.


If I recall correctly, there was no proof of this in the book. But that was many years ago. I would like to know if this intuition has been proven or disproven yet: has rule 30 been shown to be Turing complete, or is there now a proof that it cannot be?


If there is such a proof (or even if there isn't), I'd be interested to know what form it takes. In the case where something is Turing complete, one usually proves it by simulation: you use the system to implement a universal Turing machine, or some other thing that's known to be Turing complete. In the cases where something is too simple to be Turing complete, there are a number of ways to show this. (For example, you could show that every relevant question about its dynamics can be answered by a Turing machine that always halts.) However, in the case where something fails to be Turing complete because it's "too chaotic" in this way, I have no good intuition about how this could be shown.



Is rule 30 Turing complete? Is there a proof that it isn't?
As far as I know, there is no such proof in either direction.


A proof of computational universality, like you said, would be to show that rule 30 can simulate computation (Turing machine or equivalent), and it would require extreme patience in experimenting with the cellular automaton as well as some creativity.


Proving the opposite would be more problematic, because there is no clear (generally accepted) definition what we consider as a computationally universal cellular automaton. The problem is a cellular automaton configuration can carry an infinite amount of information. If you allow too sophisticated encoding/decoding procedure for input/output of the computation, one might be able to perform all or a significant part of the computation by encoding/decoding and not the cellular automaton itself. If you restrict the form of encoding/decoding too much, you would risk losing some interesting examples. (For example, computation with rule 110 requires preparing a non-uniform periodic (infinite) configuration as the background of your input.)


Some references:


The difficulty is discussed in


* K. Sutner, [Universality and Cellular Automata](http://www.cs.cmu.edu/~sutner/papers.html), MCU'2004,


and mentioned briefly in


* N. Ollinger, [Universalities in Cellular Automata: a (short) survey](http://hal.archives-ouvertes.fr/hal-00271840), JAC'2008.


General notions of computational universality in cellular automata and symbolic dynamical systems are discussed in


* J.-C. Delvenne, P. Kůrka, V. Blondel, [Decidability and Universality in Symbolic Dynamical Systems](http://iospress.metapress.com/content/eyxvfa8pum7qhbe4/), Fundamenta Informaticae, 74, 2006, and
* P. Di Lena, L. Margara, [Computational complexity of dynamical systems: The case of cellular automata](http://dx.doi.org/10.1016/j.ic.2008.03.012), Information and Computation, 206(9-10), 2008.


