https://www.wolframscience.com/nks/p475--space-as-a-network/

(In the preceding section he discussed some constraints that a cellular automaton would put on the universe model, but didn't dismiss the idea for that reason)

https://arxiv.org/abs/1405.1548

I say as usual, because G'tH had already formulated the holographic principles that would allow space-time (hence GTR) to be encoded non-locally over a graph.

https://arxiv.org/abs/gr-qc/9310026

There need not be a preferred reference frame if the space-time events do not occur at individual nodes in the graph, but emerge at scales much larger than the graph, with some holographic or permutation symmetry that can reproduce the diffeomorphism invariance of GTR. It is also plausible that the position-momentum duality of space-time could emerge from such a theory.

Space-time would be created by the events that occur, not the other way around, hence the aphorism spooky distance at an action, because the events are primary, and distance is the strange phenomenon that emerges from them.

There has been much recent progress in making space emerge from entanglement, which also implies that locality emerges from non-locality:

https://arxiv.org/abs/1005.3035

https://phys.org/news/2015-05-spacetime-built-quantum-entang...

https://www.scientificamerican.com/article/tangled-up-in-spa...

Note that LQG has produced a nice discretization of space, based on graphs that have observable quanta of area and volume, but not length. Directions and lengths are defined as normals to areas, which is reminiscent of Clifford Algebra. Having derived (emergent) lengths also makes diffeomorphism easier.

https://arxiv.org/abs/gr-qc/9411005

It's much simpler depending on the answer to the first question, right?

It's been a while since I've touched big-O, but I'm pretty sure that if the center column is periodic (period of P cells), then it follows that you just have to compute the P cells and then index into them, which makes it O(1).

I'm not sure how hard it would be to prove a lower bound on time for this problem, but if a polynomial space lower bound were proven (i.e. computing the nth square of the central column requires a Turing machine with access to Omega(n^a) space for some a > 0), then you'd have a sparse language in P that's not in L, which would be a huge advance for computational complexity theory. So definitely don't expect that anytime soon.

Kind of cheating : but a differentiable 3d field of real numbers following a local Hamiltonian evolution is a kind of cellular automaton : it has a lot of states 2^32 and local evolution rules are the mathematical ones for differentiable calculus so they encode the rotational symmetry, you can approximate to any levels of desired precision.

Have you seen the Miller-Fredkin paper on circular motion of strings in cellular automata?

https://arxiv.org/abs/1206.2060

IIRC cellular automaton are Turing-complete? We have proven we can implement simulations of 3d rotational symmetry using regular computers, so that one is straightforward, isn't it?