The Principle of Computational Equivalence
- The notion of universal computation places an upper limit on the sophistication of computations.
- The principle of "computational equivalence" is that almost all processes that aren't obviously simple can be thought of as computations of equivalent sophistication.
- "obviously simple" processes means those consisting of basic repetition and nesting.
- hence there's no hierarchy, just one highest level of computational sophistication, achieved by almost everything.
From chapter 11 / Matthew Cook we know that rule 110 is universal in the sense that with exactly the right initial condition (henceforth "i.c.") it can emulate a universal computer.
The steps leading to the principle would seem to be:
- Rule 110 can achieve universality, given the right i.c..
- Lots of other rules probably can too, given the right i.c..
- almost any system contains lots of rules that can achieve universality, and therefore are of equivalent sophistication, given the right i.c..
- most i.c. lead to computations of equivalent sophistication.
Steps 1-3 are to be taken as read, given
Chapter 11. The last point seems to be an intuition based for example on looking at rule 30 and seeing that it generates all sorts of short sequences at various points in its evolution (e.g. page 725 - note in the caption he seems to imply rule 30 will generate all possible patterns of any given size, but don't we know that there are lots of strings that any given rule can't generate from a previous string..?!). So with some particular i.c. perhaps you can view the later development as producing all sorts of possible alternative i.c.'s and playing them out.
I'm suspicious of this - for example, we know that rule 110 can be a universal computer if we give it just the right starting string, but this starting string may not itself be able to be generated by rule 110. Unless I've missed the point, he's essentially saying "all sorts of rules will generate universality from all sorts of i.c.". I find this very difficult to believe.
- Computational Irreducibility: this is the notion that many systems cannot be predicted in less time than it takes to just "play them out" forward in time. Contrast this with traditional sciences which are much concerned with dynamics of systems that are reducible, because that's what trad-math is good at. But fromthediscoveriesinthisbook there are lots of systems driven by simple rules which nonetheless can't be well described by maths formulae: they're computationally irreducible.
c.f. chaos theory: this pointed out that one must know the i.c. in arbitrarily great detail to be able to
predict successfully. Computational irreducibility is even worse than that: even if you knew the i.c. exactly it could take irreducible time to actually make the prediction.
But this seems unfair: chaos theory says much the same thing as the latter, doesn't it?
The chapter continues with...
- Relating computational irreducibility to intractability and NP completeness.
- Wolfram doesn't think quantum computers will alter his principle at all.
- Implications for maths and its foundations. This was a long section (50 pages) - it looks fascinating but I haven't had time to get through it yet. However it doesn't appear to have that much to say about the principle of computational equivalence directly in any case. Hope to update this (or someone else) later...
- Intelligence in the universe. Surprisingly long blurb on this. Again, tangential I feel.
- Implications for technology: almost anything can compute. e.g. you could grow stuff in CA fashion at atomic scales.
Marcus Frean
back to
Wolframania
EResearch