It seems to me that all CAs (cellular automata) are inherently incompatible with the spirit of Special Relativity, at least in the current formalism. CAs have what we might call a One True Space of Simultaneity, the prohibition of which was the entire point of having Special Relativity in the first place. The whole problem with CAs, that the speed of light will appear different to different observers, derives from the fact that there are absolute positions (the cells) and thus absolute velocities. Maybe you could alter the formalism so that the cells didn't have absolute positions, but you'd still have the problem that the number of cells between cell A and cell B, and thus the time for light to go between them at one tick per cell, is absolute; and thus the speed of light (relative to your own speed) is NOT. In Special Relativity, a fast-moving observer would have to see fewer cells and slower ticks.
Maybe you could alter the formalism to fix that. Frankly, I don't think so. CAs separate space and time into neat little independent Newtonian coordinates. I don't see how you can have one objectively correct universal separation into discrete cells and not have neat little Newtonian coordinates. In Special Relativity spacetime is continuous, and the transformation of some axis from space into time is also continuous.
One might say that Special Relativity says that "real" things occupy a
continuum between rules and data, while in Turing machines things are
separated into rules and data. Another of the many reasons to
best-guess that the physical Universe is noncomputable. And also a
rationale for Power-class technologies like Greg Bear's "descriptor
theory", or being able to change the laws of physics: I think we'll
find that there's no rigid distinction between substance, law, and
metalaw, and that all three can be changed. Well, now I'm getting
Eganic, so I better sign off.
firstname.lastname@example.org Eliezer S. Yudkowsky http://pobox.com/~sentience/AI_design.temp.html http://pobox.com/~sentience/singul_arity.htmlDisclaimer: Unless otherwise specified, I'm not telling you everything I think I know.