15
$\begingroup$

Cellular automata provide interesting models of physics: Google Scholar gives more than 25,000 results when searching for "cellular automata" physics.

Google Scholar still gives more than 2,000 results when searching for "quantum cellular automata".

But it gives only 1 (one!) result when searching for "relativistic cellular automata", i.e. cellular automata with a (discrete) Minkoswki space-time instead of an Euclidean one.

How can this be understood?

Why does the concept of QCA seem more promising than that of RCA?

Are there conceptual or technical barriers for a thorough treatment of RCA?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Hans, when A New Kind of Science came out, the most compelling reason I had heard of why CA couldn't reflect physics was because no one had ever successfully modeled Minkoswki space-time with them. Sorry, this isn't a real answer because I can provide neither a citation nor a technical explanation. I can just verify that there is a difficulty here. $\endgroup$
    – user37691
    Nov 16, 2010 at 9:12
  • 7
    $\begingroup$ As for "A New Kind of Science" and plausibility of modelling Minkowski spacetime with cellular automata, also check out: arxiv.org/abs/quant-ph/0206089 (book review by Scott Aaronson) $\endgroup$
    – Marcin Kotowski
    Nov 16, 2010 at 9:51
  • 1
    $\begingroup$ So has this question then doubled the number of google hits to "relativistic cellular automata"? :) $\endgroup$
    – José Figueroa-O'Farrill
    Nov 17, 2010 at 2:09
  • $\begingroup$ No, since MO is not indexed by Google Scholar. (Maybe it should be?) $\endgroup$
    – Hans-Peter Stricker
    Nov 17, 2010 at 7:22
  • $\begingroup$ @Hans: Good point. Perhaps it should. Who decides that? Google? $\endgroup$
    – José Figueroa-O'Farrill
    Nov 18, 2010 at 1:29

3 Answers 3

Reset to default
14
$\begingroup$

One of the reasons that it may be difficult to model Minkowski space based on cellular automata is that there are no "non-trivial" finite sub-groups of $O(3,1)$, where non-trivial means that it doesn't just reduce to just a finite sub group of $O(3)$ via conjugation. So while cellular automata can be manifestly be homogeneous and isotropic (so admits a discrete $O(3)$ symmetry), it becomes conceptually difficult to imagine some cellular automata capturing Lorentz symmetry.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ Why Galilean? Shouldn't the result be that any finite subgroup of $O(3,1)$ is conjugate to $O(3) \times O(1)$? If so, then you don't need any Galilean transformations (e.g., translations or Galilean boosts): up to conjugation your subgroup is generated by reflections and time reversal. Strictly speaking these are Galilean, to be sure, but saying Galilean is slightly misleading. $\endgroup$
    – José Figueroa-O'Farrill
    Nov 16, 2010 at 20:13
  • 1
    $\begingroup$ A second comment is that this group-theoretical fact might be a red herring. There are certainly discrete approaches (albeit not based on cellular automata, AFAIK) to try to capture lorentzian geometry. One particularly interesting one is that of causal sets (en.wikipedia.org/wiki/Causal_sets), for example. $\endgroup$
    – José Figueroa-O'Farrill
    Nov 16, 2010 at 20:20
  • 1
    $\begingroup$ ... involved can be captured locally (at least all the versions I have seen), which suggests to me that the grid must have some sort of homogeneity assumption. Which is why I think the group argument is compelling for why there isn't a bona fide discrete and homogeneous model of Minkowski space, and hence also a lack of relativistic CA. $\endgroup$
    – Willie Wong
    Nov 17, 2010 at 0:43
  • 1
    $\begingroup$ @Hans Stricker: what I had in mind is a totalistic CA like Life, where the central state depends only on the number of nearest neighbors that are alive. More precisely, you can imagine a CA being a map locally from the $3^n$ box of 0,1s to the value of the next center. An isotropy condition will require invariance under suitable rotations of this $3^n$ box. In other words, isotropy is not so much about invariance under "ambient directions", but about the directions allowed in the system. $\endgroup$
    – Willie Wong
    Nov 17, 2010 at 11:43
  • 1
    $\begingroup$ ... invariant (this doesn't exhaust all rotation invariant rules, by the way). For any such notion of istropy, my objection will stand. Of course, this is not a theorem that says it is impossible to model Minkowski space dynamics in this way, it is just, from my point a view, an indication that something a lot more complicated needs to be in play if you want to consider relativity in a CA framework. A key point is that whereas "quantum" is a condition on the "laws of physics/dynamics", "relativistic" really is a condition on "geometry of space-time". $\endgroup$
    – Willie Wong
    Nov 17, 2010 at 11:53
11
$\begingroup$

What Willie's answer shows is that, for some non-trivial Lorentz-translatable cellular automaton, every cell would need an infinite number of neighbors. This cellular automaton couldn't work if any cell had an infinite number of live neighbors. As was pointed out in the comments (2018), it could work if there were only a finite number of live neighbors of any cell. One would need to impose constraints on which kinds of configurations are allowed to ensure this, though.

There's a way of getting around this, however. 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 realistic 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 makes it seem like it might be.

Improve this answer
$\endgroup$
8
  • $\begingroup$ For those (like me) to whom "boost" is a new term: en.wikipedia.org/wiki/Lorentz_transformation helps. $\endgroup$
    – Joseph O'Rourke
    Nov 17, 2010 at 22:27
  • $\begingroup$ Joseph: Sorry. I guess I could have used "velocity," but that sounds wrong to ears that have been listening to too many physicists. $\endgroup$
    – Peter Shor
    Nov 18, 2010 at 19:54
  • $\begingroup$ @PeterShor Why is it contradictory for a cell to have an infinite number of neighbours? It's certainly possible to define an automaton where each cell $(x, t)$ depends on (say) the set of points $(y, s)$ satisfying $(t - s)^2 = 2(y - x)^2 + 1$ and $s < t$ (the latter 'orthochronous' condition making everything into a DAG as required a la causality). $\endgroup$
    – Adam P. Goucher
    Aug 28, 2018 at 22:29
  • $\begingroup$ @Adam: In a non-trivial Lorentz-translatable cellular automaton, each cell would have to depend on an infinite number of other cells. $\endgroup$
    – Peter Shor
    Aug 28, 2018 at 22:35
  • $\begingroup$ @PeterShor I understand entirely, but I don't see why that's contradictory. Having an infinite neighbourhood $N$ doesn't prevent one from defining a function $f : S^N \rightarrow S$ (where $S$ is the state space); indeed, there are uncountably many from which to choose. $\endgroup$
    – Adam P. Goucher
    Aug 28, 2018 at 22:50
2
$\begingroup$

I asked this very same question at physics.stackexchange, too (do the policies of MO have anything against this?), and got an interesting hint, which I leave to your attention:

Cellular automata methods in mathematical physics

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.