Registered: Jul 2006
Posts: 13

On page 666 it is shown how neighbor independent substitution systems can emulate Rule 90 and Rule 30.

Following the theme of the rest of the section I take this as evidence that a neighbor independent substitution system can be made to emulate any cellular automaton. Is this true? It's not obvious to me from the book.

In particular, has one been found that emulates Rule 110?

Last edited by Sean Lynch on 07-26-2006 at 06:41 AM

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

On p.666, it actually says that neighbor dependent substitution systems can easily emulate cellular automata.

Those that are neighbor independent are always nested or repetitive, which in itself is of interest because that is a whole system on the other side of the border of universality.

The code for ECA to neighbor dependent substitutions is oddly missing from the Notes, but it makes a good exercise in emulation.

Report this post to a moderator | IP: Logged

Registered: Jul 2006
Posts: 13

I'm sorry, I meant to say dependent - not independent.

I'm going to try to find one that emulates rule 110.

Report this post to a moderator | IP: Logged