Can cellular automata be reconcilied with quantum mechanics? CAs are deterministic representations of the universe, which, according to the Bell's inequality are not entirely accurate. Cells interact "locally" (only with the closest neighbours), while quantum entanglement proposes the opposite.
So, in layman terms, what changes should be made in cellular automata in order to -if this is even possible- make them represent the universe realistically?
 A: The main question is how do you map the CA to reality? You need to say how you describe an experimental situation in terms of the CA variables. If the map is such that an atom is described by a local clump of automata variables, and a far-away atom is described by another local clump of automata variables far away, it is flat out impossible to reproduce quantum mechanics, even in a crude way. This type of model is thoroughly ruled out by Bell's inequality violation.
But there is no requirement that the map between atomic observables and CA variables is local. If you imagine that the CA is on the surface of a holographic screen (as t'Hooft often liked to draw), then any one atom can be described by gross properties of essentially all the CA variables, nonlocally, while another atom far away is also described by a different property of all the CA variables together, so that they are always interacting. But it is concievable that statistically, those properties of the CA that describe each atom individually look like they obeying a wavefunction time evolution.
This type of thing is very hard to rule out, at least, I don't know how you would show that this sort of thing can't reproduce quantum mechanics to the extent that it has been measured.
This is something I wonder about off and on. Is it possible, even in principle, to find a CA with a physical number of variables, on the order of the cosmological horizon area divided by the Planck area, which reproduces the observed predictions of quantum mechanics by a horrendously nonlocal identification between the properties of objects and the CA variables?
It is certainly impossible to reproduce all of quantum mechanics with a model of this sort. Shor's algorithm for factoring 10,000 digit numbers will certainly fail, because there aren't enough bits and operations in the CA to do the factoring. But we haven't built a quantum computer of this size yet, so that this may be seen as a safe prediction of all such models--- that quantum computers will fail at a certain not-so-enormous number of qubits.
So it is impossible to reproduce full QM, but it might be possible to reproduce a cheap QM, which matches the cheap QM we have observed to date. You must remember that every time we verify the prediction of QM, we are not in a regime where it is doing an exponential computation of large size, precisely because if it were, we wouldn't be able to compute the consequences to compare with experiment in the first place.
The nonlocality can be in space and time together. For previous answers regarding related stuff, see here: Consequences of the new theorem in QM?
A: One change that in some ways is not a change is to embrace "superdeterminism", to take the cellular automaton to determine the free will of the experimenter. In fact, insofar as random number generators determine the choices of measurement direction in most experiments, not the experimenter, it's only necessary to take the cellular automaton to determine the automated choices of measurement direction.
If one is already committed to deterministic models, superdeterminism may not be such a big step. Try the superdeterminism page at wikipedia or Google for superdeterminism. 
Your Question somewhat prejudges the answer by suggesting that dynamical nonlocality will be necessary. Superdeterminism is all about initial conditions being nonlocal, in which case dynamical nonlocality is not necessary (although it may also be present in specific models). You may already be aware that CAs are rather a different approach to QM than the Bohmian mechanics type of models in that particle trajectories will have to be emergent rather than a fundamental part of the construction of the model.
There is a class of models called random fields that can be considered to be intermediate between CAs and quantum fields. Such models are inherently probabilistic or stochastic, without either deterministic evolution or definite initial conditions, but the probabilities are classical. If you find CAs compelling, I suggest you might add this kind of idea, particularly in lattice variants, to your list of possible worldviews. If you feel like a hard slog, and don't care that I'm blowing a horn, try my http://arxiv.org/abs/cond-mat/?0403692, published as J. Phys. A: Math. Gen. 39 (2006) 7441-7455, however I believe I'm the only person who thinks this is anything like a clear argument, probably including the editors and referees at JPhysA.
