[lacker]

It is pretty hard in general to prove that calculating things takes at least O(n) time, so I wouldn't expect that one to be solved any time soon.

Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. If our universe can be described by a cellular automaton, it isn't obvious to me how such a symmetry could arise, but I wouldn't be surprised if someone figured it out.

[nswanberg]

For what it's worth, Stephen decided that network was a better model for the universe than a cellular automaton, and thought that space might emerge as a property of that network rather than be "defined in", as in a cellular automaton.

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)

[jkp56]

I can't open this link for some reason (uBO?), but the title reminds me one very clever Wolfram's article where he brags about (as usual) about how he derived GTR equations from his graph model. That article had a bunch of comments with and one of them stating that in such a graph model there is always a reference frame. Wolfram didn't respond to that comment.

[mikhailfranco]

I think SW became too obsessed with the mathematical and computational approach to CA, while (as usual) 't Hooft pursued his physics intuitions to create a candidate CA theory:

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

[mikhailfranco]

I haven't followed this closely, but did SW provide a paper showing how he derived GTR from the graph?

[sokrates85]

He made the claims but not sure if that paper ever appeared.

[singingboyo]

> It is pretty hard in general to prove that calculating things takes at least O(n) time

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).

[fnrslvr]

That would be a refutation of the claim that the calculation takes O(n) (or more correctly Omega(n)) time. If the center column turned out to be periodic, then yeah, you're basically on the right track: you would get an algorithm that runs in time polynomial in log(n).

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.

[GistNoesis]

>any cellular automaton that has something like 3-dimensional rotational symmetry

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.

[mietek]

> Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry.

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

https://arxiv.org/abs/1206.2060

[lacker]

I haven't seen that, but the fact that you posted this interesting link makes me glad I commented! Will check it out

[Iv]

I think the challenge is more of a quest to find a way to compute it in less than O(n). The proof for that would just be a working algorithm.

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?