Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is well known that the elementary cellular automaton known as rule 110 is Turing complete.

Its cousin rule 30 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.

share|improve this question
1  
The "Turing completeness" of rule 110 is a complicated issue (and too long for this comment). The Wikipedia article may be a little too eager to accept the claims of "Turing completeness" at face value. –  Carl Mummert Apr 27 at 15:29
    
If there's a notable objection, you could point me towards a paper, and/or edit the Wikipedia page if you felt so inclined. –  Nathaniel Apr 28 at 1:36
add comment

1 Answer 1

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

and mentioned briefly in

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

share|improve this answer
    
Thank you for your answer. Regarding your last paragraph, the same worry had occurred to me as well, while thinking about this stuff recently. I think it can probably be solved with some care about definitions, though. If you stipulate that the encoding has to be primitive recursive, for example (in some sense whose details have to be worked out) then at least it guarantees that some non-trivial component of some computations has to be done by the system itself and not by the encoding. Is the lack of an accepted definition something that people have commented on in the literature? –  Nathaniel Apr 27 at 10:17
    
The initial configuration of the cellular automaton is an infinite object. The encoding should therefore transform a finite string into an infinite string. A primitive recursive function alone will not do, unless you add a non-trivial interpretation its output. But then that interpretation is also part of your encoding. –  Algernon Apr 27 at 10:31
    
Some years ago, there was a discussion about this. For example, Matthew Cook gave a non-conclusive talk about this in AUTOMATA 2006. There were also a couple of nice articles, but I have to check my large stacks of papers before giving you the references ... :-) –  Algernon Apr 27 at 10:41
    
I meant something along the lines of, the initial state of each cell $i$ has to depend upon the input program $P$ according to a primitive recursive function $f(i,P)$. I'm not sure if that exact idea works or not (partly because it's much less clear how you do the decoding), but my intuition was that something like it should do the job. I look forward to those references if you get a chance to dig them out! –  Nathaniel Apr 27 at 11:43
    
But still, one could just stipulate that the initial state has to be periodic (apart from a finite number of cells, which depend on the input program), and ask whether rule 30 is computationally reversible given that constraint (i.e. if it's universal in the same sense as rule 110). I'm still curious to know whether there would be a way to prove that this isn't the case. (If indeed it isn't.) –  Nathaniel Apr 27 at 11:45
show 4 more comments

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.