What Willie's answer shows is that, for some non-trivial Lorentz-translatable cellular automaton, every cell would need an infinite number of neighbors, a contradiction. There's a way of getting around this, though. You could make each cell correspond to a point in space-time and also a boost (a boost is essentially a velocity in the Lorentz group). Then, cells would interact with cells both close to them in space-time and also close in boost. I don't know whether anybody has considered cellular automata like this.
In order for this to have a correspondence to realityrealistic quantum field theories, it would have to be the case that when two particles interact at a high boost, the interaction strength goes to 0 as the boost goes to infinity. I don't know whether this is true, although the thought experiment of considering particles falling into a black hole through a sea of Hawking radiation seems makes it seem like it might be.
