A New Kind of Science: The NKS Forum > Pure NKS > PCE and universality of rule 30
Author
RLamy

Paris, France

Registered: Nov 2007
Posts: 16

PCE and universality of rule 30

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.

Report this post to a moderator | IP: Logged

12-13-2007 06:11 PM
tomjones

Registered: Not Yet
Posts: N/A

"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

Report this post to a moderator | IP: Logged

12-13-2007 06:20 PM
RLamy

Paris, France

Registered: Nov 2007
Posts: 16

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.

Report this post to a moderator | IP: Logged

12-13-2007 07:39 PM
tomjones

Registered: Not Yet
Posts: N/A

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

Report this post to a moderator | IP: Logged

12-14-2007 02:44 AM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us