[PCE and universality of rule 30] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


PCE and universality of rule 30

(Click here to view the original thread with full colors/images)


Posted by: RLamy

From the information I have gleaned on this forum and elsewhere, I have understood that the validity of the Principle of Computational Equivalence is practically indexed on the truth of the assertion that rule 30 is universal. What I don't understand is why Wolfram believes in this conjecture.

To me, it seems that universal systems are those for which any questions concerning their long-time evolution is decidable for almost any initial condition, except for a tiny (measure 0?) but dense subset. For rule 30, I would rather think that it's the converse: almost any initial condition is undecidable.

Are there arguments against my characterisation, or counter-examples? Is it possible that rule 30 actually obeys it? If the answer to both questions is no, I cannot believe that the PCE holds.


Posted by: tomjones

"To me, it seems that universal systems are those for which any questions concerning their long-time evolution is decidable for almost any initial condition, except for a tiny (measure 0?) but dense subset. For rule 30, I would rather think that it's the converse: almost any initial condition is undecidable."

This is actually the idea of reducible vs irreducible not universal or not universal. What universality means is that if a system is universal it can be made to emulate many other systems. So if you take for example the universal rule 110 it can be made to emulate other computational systems.

In fact PCE is not dependent or rule 30 being or not being universal, while it may be evidence; it is not proof of the principle. In fact the relation of PCE to universality is that once a system reaches universality it can then emulate any other computational system, and thus can be claimed as being of equivalent computational sophistication since once you reach that level other states are not necessary. In fact without such a low level for universality one could not have PCE.

I hope this makes sense...

Thanks


Posted by: RLamy

Originally posted by tomjones
This is actually the idea of reducible vs irreducible not universal or not universal.

I think you have misunderstood me: what I claim is that universal systems (or at least universal CAs) are those systems which are quasi-reducible yet irreducible, thus in a sense at the border between reducibility and irreducibility.

In fact PCE is not dependent or rule 30 being or not being universal, while it may be evidence; it is not proof of the principle.

I didn't say that it was logically equivalent, just that a proof one way or the other concerning the universality of rule 30 would have vast implications on the status of the PCE. This is because the PCE claims that any complex system should be universal, and rule 30 is supposed to be an undistinguished representative of the class of complex systems.


Posted by: tomjones

On the first point your right I did not catch the converse part.

On the second you are still mistaken, nothing about PCE hinges on Rule 30 nor is Rule 30 significant in the grand-scope of PCE, if it is or isn't universal is only evidence for or against PCE and nothing more. Wolfram uses Rule 30 because it produces very complex behavior from very simple rules and it is almost completely random, as far as computers go. I never denied any implications, just that they are no larger then showing some-other CA as universal.

Thanks




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