3

On page 648 of A New Kind of Science, there's a definition of a "universal" cellular automaton, which can emulate Wolfram's 256 elementary cellular automata. Furthermore, it emulates them in a "cell-by-cell" manner: one cell of the elementary automaton is represented by 20 consecutive cells in this cellular automaton.

Elsewhere, on page 437, there's a definition for a family of reversible 2-color cellular automata. I expect that in a family like this, but with more colors, you can construct a cellular automaton that is "universal" in the exact same sense as the one on page 648: one that can emulate all 256 elementary cellular automata, and which represents them on a "cell-by-cell" level, using consecutive cells to represent one cell.

I feel sure someone has made something like this, but I don't know the cellular automata literature. Could someone point me to it?

user54038
  • 367
  • 1
  • 9
  • Of course, there's a trivial way to do this using 512 states per cell (and an only slightly less trivial one using 32 + 2 = 34 states). It's even quite efficient, running as fast as the emulated automaton and representing each emulated cell by one emulator cell. But I assume you're looking for something a little less trivial and more "universal" than this. – Ilmari Karonen Feb 10 '19 at 06:34
  • Are you sure that your 512 states solution is reversible? If one removes the requirement of reversibility, I agree with you. – user148606 Feb 10 '19 at 10:58
  • @user148606: I originally read the question as asking for a reversible CA rule that emulates all the 256 elementary reversible (2nd order) CA rules. However, on a closer look, I see that it doesn't actually say that. – Ilmari Karonen Feb 11 '19 at 09:32
  • In theory rule $110$ can emulate all other Elementary Cellular Automata, because it is universal. But rule $110$ is not reversible, so that one is out of luck. –  Mar 05 '19 at 15:45

1 Answers1

2

There is no precise definition of what "emulating" means in the book of Wolfram, but it looks like intrinsic simulations (like in the notion of intrinsic universality, see this survey on universality in CA). In this case, the answer is NO, because there is no reversible CA that can emulate an irreversible CA.

user148606
  • 410