[complexity <=> universality] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
complexity <=> universality
(Click here to view the original thread with full colors/images)
Posted by: Mike Lin
The Principle of Computational Equivalence asserts a strong correlation between observed complexity and computational universality. Rule 110 is universal, which shows that you do not need especially complicated rules to achieve universality. This does not mean that every complex phenomena is universal.
In particular, it is difficult to accept that Rule 30 or anything that exhibits "class 3" behavior is universal, simply because the "intrinsic generation of randomness" seems to destroy information about the input very rapidly.
Wolfram anticipates this objection on pp.734-735. His defense is what I think is a questionable "argument by analogy" to intermediate degrees of computability (also discussed on pp. 1130-1131). Although the input-output functions of such systems are not universal, the computations that underlie them certainly are. This is clear because they are constructed via diagonalization on universal machines, and to actually perform that diagonalization you would need a universal machine.
I think this is a misleading analogy because there is no obvious similar way to argue that the computations underlying Rule 30 (rather than just its input-output function) must be universal. There is no explicit invocation of another universal system going on in applying Rule 30, as there is in the analogy.
So even though I am ready to accept that Rule 30 contains no nesting or repetition, I don't have much evidence that it or any other class 3 system is universal itself, or otherwise requires universal computation to simulate.
As I understand the earlier chapters, class 3 behavior is more common than class 4, so this is an important question to answer.
Posted by: Jason Cawley
I moved this topic and another similar one to "way of thinking" because I think the method and reasoning questions it raises fit that category rather than the Pure NKS category, which is meant for detailed investigation of particular formal systems.
Whether class 3s are universal or something else is an open question in NKS, and an important one. The Principle of Computational Equivalence (hereafter "PCE") asserts that they will prove to be, but that is clearly a conjecture at this stage. It is not meant to be taken as proved. On the contrary, proving results about it one way or another would be a definite new contribution.
At first, it may seem the class 3s are something fundamentally simpler than the universality seen in 4s. Statistical reasoning might have its appropriate area of application to systems of this kind, where uncontrolled spread of information results in large scale "mixing" that perhaps washes out any sort of real structure. One could hypothesize that barriers to such uncontrolled information flow are essential to true complexity.
Why doesn't the NKS book come out here? What is there to suggest that instead even the class 3s will eventually be found to be universal? Two main points. First, in class 3 systems one occasionally encounters the phenomenon of random looking behavior for most initial conditions, but behavior of another sort - nested or simple e.g. - from highly specialized initial conditions. For example, repetitive blocks of cells of a specific pattern (or "key"). This suggests that at least sometimes, the supposedly uncontrolled mixing can be manipulated by programming the initial condition in sufficient detail.
Second there is the general point that suggests PCE in the first place - the "ratchet" effect of chained emulations. It becomes easier to prove additional systems are universal, whenever one drives the threshold of proven universality lower. Because the strategy for proving universality is typically to show that a system of type A can emulate members of type B, known to contain universal cases, the simpler B gets the easier it is to find ways for A to emulate that type. Turing machine universality can establish cyclic tag system universality. Those combined can establish elementary CA universality. When all you have to emulate is CA 110, it becomes straightforward e.g. to prove that the Spencer-Brown form can support universality.
There is a definite progression here. The lower you drive the known universality threshold, the fewer resources a candidate system needs to emulate a class known to contain universal members. The emulation options are also expanding in variety, as well as declining in inherent complexity at the level of the rule.
So what is behind the conjecture that class 3s will eventually prove universal? The idea is that special initial conditions can be found to make particular class 3s do unusual things - unusual for a class 3. That the requirement to prove universality will drop to "get those unusual things to emulate any of a large class of simpler and simpler systems". Clearly, this is a sketch of a possible research program, not an established result. But it explains why Wolfram believes universal class 3s will eventually be found.
Of course, particular class 3 systems might be proven capable of universality, without it proving all or most class 3 behavior is that complex. It would only suggest it. The problem could also be attacked from the other end, by trying to prove that certain class 3s are not capable of supporting universality. Now, ask yourself how easy that might be to do. You can't predict the behavior of the center column of rule 30 from a known seed. But you are supposed to show restrictions on the possible behavior of rule 30, allowing the other guy any imaginable initial condition.
It is possible class 3s have some underlying simplicity of a statistical character, in general or from all but a "measure zero" set of specialized initial conditions. If so, it would be a qualification to PCE, showing it was not true as originally formulated, and needs to be narrowed. Wolfram's conjecture is that this will not be found to be the case, but it is a conjecture and it might be shown to be wrong. That is what hypotheses are for. They are supposed to be falsifiable, it is what gives them logical content.
If you've got an idea about how to prove a given class 3 can't support universality, it is a subject worth investigating. PCE is a challenge. Show it is wrong. Or, follow the research program sketch discussed above, and find a key-like repetitive special initial condition for some system with class 3 behavior, that allows it to emulate some other type of system. And thereby be the first to show, rather than conjecture, that some class 3 system is universal. Either way, it would be an important contribution to NKS.
I hope this is helpful.
Posted by: Mike Lin
I think this would be more than an "important contribution" to NKS. It seems to me that the vast majority of the usefulness of the PCE hinges very directly on this conjecture, that class 3 behavior is universal. When we see behavior analagous to class 4 in nature, we are not "afraid" of it - it is exactly the kind of phenomena that current mathematics, science and engineering is very well suited to understanding. Class 3 behavior - overwhelming randomness and unpredictability - is what makes modern science run away, and what we desperately need new intuition for understanding.
If the PCE had to be narrowed to state that natural phenomena which support localized structures that interact in predictable ways are universal, I think this would be vastly - vastly - less interesting. We are already very good at understanding that kind of phenomena.
That stated, demonstration of one universal class 3 system would be an extremely convincing triumph for NKS. I made these two posts - this one about universality, and the other one about observing irreducibility - because I think they are, by far, the two most important open problems for NKS. The usefulness of the entire enterprise hinges on them.
Jason, do you know of active efforts to write secondary source accounts of NKS in a more conventional expository style, as you have written your post? I would be interested in helping with or starting such an effort. I feel the important perspective you have provided on the validity of the PCE can be gained from the NKS book only in spite of the way it is written.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings