Registered: Nov 2007
Posts: 16

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

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

Registered: Nov 2007
Posts: 16

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

Report this post to a moderator | IP: Logged

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