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.