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.
sentience@pobox.com Eliezer S. Yudkowsky
http://pobox.com/~sentience/AI_design.temp.html
http://pobox.com/~sentience/singul_arity.html
Disclaimer: Unless otherwise specified, I'm not telling you
everything I think I know.