I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. Is there another method or information that would still prove the universality of rule 110? In other words, is there another way to to do that without considering tag systems, and if so, can you explain the proof or give a reference to it?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ The answer is certainly "yes", so I guess you are really asking for references to other proofs? $\endgroup$– Raphael ♦Oct 29, 2015 at 18:35
-
$\begingroup$ Yes, exactly ... or even materials to read about it, i keep reading on Complex systems journal to find something similar but no luck (complex-systems.com/archives.html). $\endgroup$– Henry akpoOct 29, 2015 at 18:38
-
4$\begingroup$ Tag systems were there so he used them. Otherwise he would have used something else. If you really care, you can come up with an alternative proof yourself. I'm not sure anyone else has bothered doing it so far, though it's certainly a meaningful exercise. $\endgroup$– Yuval FilmusOct 29, 2015 at 18:47
-
2$\begingroup$ the proof was extremely difficult, took huge research & many pages, and has not been simplified. such simplifications sometimes happen after a lot of related work/ theoretical development in the area. there is not much related work in the area... "yet" $\endgroup$– vznOct 29, 2015 at 19:02
-
2$\begingroup$ Please use proper capitalization and grammar (with sentence breaks) -- your origianl question was a stream of words with no sentence breaks anywhere and no capitalization. That makes your question unnecessarily difficult to read. $\endgroup$– D.W. ♦Oct 29, 2015 at 22:04
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
More a bunch of references than an answer .... :-)
As said by @vzn in its comment Cook's proof is very complex and required a lot of work; nevertheless the universality of rule 110 renewed the interest on small model of computations.
Among the most notable results was the proof that rule 110 can simulate a deterministic Turing machine efficiently, i.e. with only a polynomial-time slowdown:
- Turlough Neary, Damien Woods: P-completeness of Cellular Automaton Rule 110. ICALP (1) 2006: 132-143
- Damien Woods, Turlough Neary: On the time complexity of 2-tag systems and small universal Turing machines. FOCS 2006: 439-448
Along the direction of a simplified/different proof of the universality of rule 110, you can find some work, e.g.:
For a good survey on universality in cellular automata and other ideas for proving universality:
Finally a *personal* idea on an alternative approach that could be investigated:
- Proving universality of larger CAs (with larger neighbourhood or more states) is much easier and you can even get rid of the intermediate tag-system simulation, so you could investigate if using rule 110 gliders it is possible to simulate an arbitrary larger CA; a slightly similar approach has been used by Nicolas Ollinger and Gaétan Richard in A Particular Universal Cellular Automaton to prove the universality of colliding particles systems (they prove that a particular system can simulate an arbitrary CA)
And don't forget that instead of working on a different proof for rule 110 universality, you can work on the open problem regarding rule 54 ... is it (weakly) universal ? :-)
-
$\begingroup$ Actually i am building a new cellular automaton structure (simpler than ECA) and i found it easy to simulate almost all the ECA rules & even Conway's Game of Life from the same structure ... so i can easily simulate rule 110 and i assume also that simulating rule 110 makes the system universal, right ??? the problem is i want an extra proof of universality and i cannot implement the tag system in it, thats why i asked for another way to prove universality ... i might post it as a question though. But thanks for your time ... really ! $\endgroup$ Oct 31, 2015 at 19:19
-
2$\begingroup$ @Henryakpo: yes, simulating Rule 110 should be enough (I don't know the details of your CA structure) to consider it weakly univesal (weakly because it needs an infinite repeated support pattern). But if you are able to simulate Rule 110 or a 2D CA like Conway's life without needing an infinite repeated support-pattern, then it is universal. You can also try to simulate a CA with larger neighbourhood, or simulate a Turing machine, or a rewrite system. $\endgroup$– VorOct 31, 2015 at 20:16