<blockquote>
<p>To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task.</p>
</blockquote>
<p>Game of life is <em>intrinsically universal</em> meaning that it can simulate any 2D CA with a constant runtime (and spatial) scaling. See
<a href="https://doi.org/10.1007/978-94-015-9153-9_2" rel="nofollow noreferrer">Durand, B., Róka, Z. (1999). The Game of Life: Universality Revisited.</a></p>
<p>It is not difficult to design an intrinsically universal CA with larger alphabet/radius (in the 2D or 1D case). Rule 110 however is not known to be intrinsically universal.</p>

CC BY-SA 4.0
2022-10-29T14:17:05.470Z
Oh wow, thanks for pointing that out, I wasn't aware of that! I think the tricky part is finding a compiler from some high-level human-programmable language to some CA. One could then in principle switch to the (simpler) game of life, but I suspect the constant overhead in doing so from some mildly complicated CA might be huge, and the mapping between them might be hard to find? Is the universality proof actually constructive?
Andi Bauer
CC BY-SA 4.0
2022-10-29T14:22:53.470Z
Also a very basic question about the definition of "intrinsically universal": For this we need an encoder and decoder between the configurations of the game of life and the CA we with to emulate. Are those encoders and decoders assumed to be 1) computable without any runtime restrictions, 2) computable in something like polynomial time, or 3) computable by a constant-time layer of CA? (Hoping for the third.)
Andi Bauer
CC BY-SA 4.0
2022-10-29T15:48:21.180Z
Just had a look into [the paper you reference](https://www.phil.uu.nl/~iemhoff/College/LogCom/2010/gameoflife.pdf), and I'm surprised how accessible this is. So the encoding is constructive, finding it is just as hard as finding a boolean circuit representing the transition rules of the emulated CA, and it is "UL-defined" which means 3) is indeed the case. The constant overhead does however seem very bad and comes from the circuit complexity of the emulated transition rules (which is unavoidable), times a very large prefactor coming from the specific construction used. Would you agree?
Andi Bauer
CC BY-SA 4.0
2022-10-29T21:14:03.760Z
Yes, there is a large constant factor to pay in the case of Game of Life, but you can choose another intrinsically universal CA. It's like designing new hardware to better fit your needs.
user148606
CC BY-SA 4.0
2022-10-28T09:12:44.230Z
2022-10-28T09:12:44.230Z
user148606
<p>It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate Turing machines even with only a polynomial overhead. However, this doesn't yet make them at all practically useful computers.</p>
<p>In practice, we do very much care about whether an algorithm runs in <span class="math-container">$O(n^2)$</span> or <span class="math-container">$O(n^7)$</span>. If we would compile a complicated C program to a Turing machine, the runtime scaling would be different (slower) from what we expect from running it on a real-life random-access computer. The same is true for the two universal CAs mentioned in the first paragraph (together with the encoding used in the universality proof). Hence the question:</p>
<p><strong>Are there any 2D universal CA (plus compiler from a practical programming language such as C) such that the runtime scaling of any task is equal to what we expect from a practical computer?</strong></p>
<p>To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task. Those runtime exponents are slightly different from the ones of random-access computers. On the one hand, parallelization is for free in CAs, so for example, sorting in a CA has runtime <span class="math-container">$O(n)$</span>. On the other hand, information in a CA propagation can only propagate at a finite speed, so for example, searching a list takes time <span class="math-container">$O(n)$</span> as well (however, we can run multiple searches in parallel, and also reduce to <span class="math-container">$O(n^{1/2})$</span> if we arrange the list into a 2-dimensional array).</p>
<p>(Actually, if you know a little bit about physics then you'll see that CAs are a much better model for the real world than random-access computers. So if you really care about scaling not only in some intermediate regime, then the CA runtime scalings are the correct ones, and the ones for random-access computers are wrong.)</p>

CC BY-SA 4.0
2022-10-13T12:33:57.613Z
Your statement about the sorting time for a universal 2-D CA is incorrect. SHEARSORT can sort $n$ numbers in $O(\sqrt{n} \log n)$ time.
Peter Shor 
CC BY-SA 4.0
2022-10-13T13:40:05.570Z
I vaguely recall a paper by L. Levin about a model of asymptotic computation that accounted for the need to embed computation in three dimensions, in which he argued that, due to the need to dissipate heat, the computer would essentially have to be laid out in two dimensions.  The focus was on how this requirement constrained how quickly computations could be done.  I think he proposed a model that was intended to be universal subject to this constraint.  Perhaps that model captures part of what you are after.  Unfortunately I could not find the paper with a quick search.
Neal Young
CC BY-SA 4.0
2022-10-13T21:09:18.993Z
@NealYoung Yes, the reason why I specifically ask about 2D CAs is precisely that if we scale in 3D there's nowhere for the heat to go  (and the intuition that in 1D CAs fast universal computation is unrealistic).
Andi Bauer
CC BY-SA 4.0
2022-10-14T10:33:35.793Z
I think that the modern parallel computing architectures (CUDA language + GPUs) are a good "real-world" approximation of a CA computation. You can view a single CPU core as a "complex" CA cell capable of performing local computation in parallel with other cells.
Marzio De Biasi
CC BY-SA 4.0
2022-10-14T16:02:36.127Z
@MarzioDeBiasi I don't know much about GPUs at all, but I would guess that they are not efficiently universal on their own, and they do have some amount of non-local communication in each clock cycle. The main reason why I think CAs would be more natural for computation is that in theory, restricting to local communication could allow to increase the clock frequency by many orders of magnitude, but I'd guess that the clock frequency of a GPU is similar to that of a CPU? Are these guesses correct?
Andi Bauer
CC BY-SA 4.0
2022-10-14T16:04:26.950Z
Anyways, what I'm looking for is an efficiently universal uniform CA with very simple cells (maybe not quite as simple as the game of life, but much simpler than a CPU).
Andi Bauer
CC BY-SA 4.0
2022-10-15T11:15:31.303Z
@MarzioDeBiasi I don't think modern GPUs are conceptually close to CAs, because they have complex cache hierarchies and schedulers switching between tasks. Also the GPU cores are programmable, albeit in an essentially SIMD manner. That's extremely powerful, unlike CA nodes.
Martin Berger
CC BY-SA 4.0
2022-10-17T12:52:47.897Z
@AndiBauer: ok, but how do you deal with "compiling" a language such as C using very simple cells? You should add/hide in the compiler a higher level of abstraction in which you somewhat "group" (a lot of) cells together to accomplish a basic task such as performing a multiplication on a variable.  But you would end up in a higher level "computing" cell units and switch the problem to efficient (new?) usage of parallelization. In this sense I said that if you need something concrete a GPU could approximate CAs. Or you can stay on the theoretical aspect and think about a new language for CAs.
Marzio De Biasi
CC BY-SA 4.0
2022-10-17T12:57:52.597Z
@MartinBerger: I agree, but the OP asked for a "practical programming language" and I actually don't see a way to use very basic cell rules without hiding a big layer of abstraction in the compiler (grouping portions of cells to accomplish a particular task such as "multiply two values"), but in this case the focus will be switched only to using parallelization efficiently (hence the GPU approximation). If you want to stay with simple cell structure/rules then there is a need of a new (theoretical) approach (I'll say a new programming paradigm :-) to "program them".
Marzio De Biasi
CC BY-SA 4.0
2022-10-17T16:39:39.013Z
@MarzioDeBiasi I do believe that there is a programming language which is as high-level and as practical as C, and which can be efficiently compiled to a simple cellular array. I have some ideas in this direction and was wondering whether anyone has worked on this before. Of course, C itself is very directly designed for random-access machines and doesn't support notions of parallelization. It would be very hard for a compiler to find out which tasks can be parallelized in order to efficiently run them on a CA. So in that sense I agree that the language we compile from should...(continued)
Andi Bauer
CC BY-SA 4.0
2022-10-17T16:55:56.183Z
incorporate a new "programming paradigm". The idea would *not* be to explicitly group cells (physically or in the compiler) to accomplish subtasks. Rather, both the data and the code would be represented as some kind of "wobbly tree of bits" encoded into the CA state, and the code would be executed by deforming this tree according to local rules. For example, two bit-strings representing two integers can be encoded as two "worms of bits" in the CA state, and they can be added using local rules by running a "zipper" along them.
Andi Bauer
CC BY-SA 4.0
2022-10-18T12:21:31.507Z
@AndiBauer: mmm ... I think that every "bit of computation" coming from the procedural paradigm is dooomed to fail (in your sum example, if you want the addition to stay local and parallelized with simple cells structure you should add "instructions" to move the result in other areas and prevent other cells to do damages, otherwise the only way is to move the "control"). Perhaps most interesting ideas could be picked from the declarative paradigms. In every case I don't know research in these directions (except for the "rush for minimal universal CAs"), but I'm not an expert of the field :-)
Marzio De Biasi
<complexity-classes><polynomial-time><physics><universal-computation><cellular-automata>
Computation with cellular automata in practice
Andi Bauer
# Computation with cellular automata in practice

(Asked by: username_0 on 2022-10-13)

It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate Turing machines even with only a polynomial overhead. However, this doesn't yet make them at all practically useful computers.

In practice, we do very much care about whether an algorithm runs in $O(n^2)$ or $O(n^7)$. If we would compile a complicated C program to a Turing machine, the runtime scaling would be different (slower) from what we expect from running it on a real-life random-access computer. The same is true for the two universal CAs mentioned in the first paragraph (together with the encoding used in the universality proof). Hence the question:

**Are there any 2D universal CA (plus compiler from a practical programming language such as C) such that the runtime scaling of any task is equal to what we expect from a practical computer?**

To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task. Those runtime exponents are slightly different from the ones of random-access computers. On the one hand, parallelization is for free in CAs, so for example, sorting in a CA has runtime $O(n)$. On the other hand, information in a CA propagation can only propagate at a finite speed, so for example, searching a list takes time $O(n)$ as well (however, we can run multiple searches in parallel, and also reduce to $O(n^{1/2})$ if we arrange the list into a 2-dimensional array).

(Actually, if you know a little bit about physics then you'll see that CAs are a much better model for the real world than random-access computers. So if you really care about scaling not only in some intermediate regime, then the CA runtime scalings are the correct ones, and the ones for random-access computers are wrong.)

**Tags:** complexity-classes, polynomial-time, physics, universal-computation, cellular-automata

> **Comments:**
> **username_1**: Your statement about the sorting time for a universal 2-D CA is incorrect. SHEARSORT can sort $n$ numbers in $O(\sqrt{n} \log n)$ time.  
> **username_2**: I vaguely recall a paper by L. Levin about a model of asymptotic computation that accounted for the need to embed computation in three dimensions, in which he argued that, due to the need to dissipate heat, the computer would essentially have to be laid out in two dimensions.  The focus was on how this requirement constrained how quickly computations could be done.  I think he proposed a model that was intended to be universal subject to this constraint.  Perhaps that model captures part of what you are after.  Unfortunately I could not find the paper with a quick search.  
> **username_0**: @NealYoung Yes, the reason why I specifically ask about 2D CAs is precisely that if we scale in 3D there's nowhere for the heat to go  (and the intuition that in 1D CAs fast universal computation is unrealistic).  
> **username_3**: I think that the modern parallel computing architectures (CUDA language + GPUs) are a good "real-world" approximation of a CA computation. You can view a single CPU core as a "complex" CA cell capable of performing local computation in parallel with other cells.  
> **username_0**: @MarzioDeBiasi I don't know much about GPUs at all, but I would guess that they are not efficiently universal on their own, and they do have some amount of non-local communication in each clock cycle. The main reason why I think CAs would be more natural for computation is that in theory, restricting to local communication could allow to increase the clock frequency by many orders of magnitude, but I'd guess that the clock frequency of a GPU is similar to that of a CPU? Are these guesses correct?  
> **username_0**: Anyways, what I'm looking for is an efficiently universal uniform CA with very simple cells (maybe not quite as simple as the game of life, but much simpler than a CPU).  
> **username_4**: @MarzioDeBiasi I don't think modern GPUs are conceptually close to CAs, because they have complex cache hierarchies and schedulers switching between tasks. Also the GPU cores are programmable, albeit in an essentially SIMD manner. That's extremely powerful, unlike CA nodes.  
> **username_3**: @AndiBauer: ok, but how do you deal with "compiling" a language such as C using very simple cells? You should add/hide in the compiler a higher level of abstraction in which you somewhat "group" (a lot of) cells together to accomplish a basic task such as performing a multiplication on a variable.  But you would end up in a higher level "computing" cell units and switch the problem to efficient (new?) usage of parallelization. In this sense I said that if you need something concrete a GPU could approximate CAs. Or you can stay on the theoretical aspect and think about a new language for CAs.  
> **username_3**: @MartinBerger: I agree, but the OP asked for a "practical programming language" and I actually don't see a way to use very basic cell rules without hiding a big layer of abstraction in the compiler (grouping portions of cells to accomplish a particular task such as "multiply two values"), but in this case the focus will be switched only to using parallelization efficiently (hence the GPU approximation). If you want to stay with simple cell structure/rules then there is a need of a new (theoretical) approach (I'll say a new programming paradigm :-) to "program them".  
> **username_0**: @MarzioDeBiasi I do believe that there is a programming language which is as high-level and as practical as C, and which can be efficiently compiled to a simple cellular array. I have some ideas in this direction and was wondering whether anyone has worked on this before. Of course, C itself is very directly designed for random-access machines and doesn't support notions of parallelization. It would be very hard for a compiler to find out which tasks can be parallelized in order to efficiently run them on a CA. So in that sense I agree that the language we compile from should...(continued)  
> **username_0**: incorporate a new "programming paradigm". The idea would *not* be to explicitly group cells (physically or in the compiler) to accomplish subtasks. Rather, both the data and the code would be represented as some kind of "wobbly tree of bits" encoded into the CA state, and the code would be executed by deforming this tree according to local rules. For example, two bit-strings representing two integers can be encoded as two "worms of bits" in the CA state, and they can be added using local rules by running a "zipper" along them.  
> **username_3**: @AndiBauer: mmm ... I think that every "bit of computation" coming from the procedural paradigm is dooomed to fail (in your sum example, if you want the addition to stay local and parallelized with simple cells structure you should add "instructions" to move the result in other areas and prevent other cells to do damages, otherwise the only way is to move the "control"). Perhaps most interesting ideas could be picked from the declarative paradigms. In every case I don't know research in these directions (except for the "rush for minimal universal CAs"), but I'm not an expert of the field :-)  

---

## 1 answers

### Answer by username_5 on 2022-10-28. Score: 3

> To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task.

Game of life is *intrinsically universal* meaning that it can simulate any 2D CA with a constant runtime (and spatial) scaling. See
[Durand, B., Róka, Z. (1999). The Game of Life: Universality Revisited.](https://doi.org/10.1007/978-94-015-9153-9_2)

It is not difficult to design an intrinsically universal CA with larger alphabet/radius (in the 2D or 1D case). Rule 110 however is not known to be intrinsically universal.

> **Comments:**
> **username_0**: Oh wow, thanks for pointing that out, I wasn't aware of that! I think the tricky part is finding a compiler from some high-level human-programmable language to some CA. One could then in principle switch to the (simpler) game of life, but I suspect the constant overhead in doing so from some mildly complicated CA might be huge, and the mapping between them might be hard to find? Is the universality proof actually constructive?  
> **username_0**: Also a very basic question about the definition of "intrinsically universal": For this we need an encoder and decoder between the configurations of the game of life and the CA we with to emulate. Are those encoders and decoders assumed to be 1) computable without any runtime restrictions, 2) computable in something like polynomial time, or 3) computable by a constant-time layer of CA? (Hoping for the third.)  
> **username_0**: Just had a look into [the paper you reference](https://www.phil.uu.nl/~iemhoff/College/LogCom/2010/gameoflife.pdf), and I'm surprised how accessible this is. So the encoding is constructive, finding it is just as hard as finding a boolean circuit representing the transition rules of the emulated CA, and it is "UL-defined" which means 3) is indeed the case. The constant overhead does however seem very bad and comes from the circuit complexity of the emulated transition rules (which is unavoidable), times a very large prefactor coming from the specific construction used. Would you agree?  
> **username_5**: Yes, there is a large constant factor to pay in the case of Game of Life, but you can choose another intrinsically universal CA. It's like designing new hardware to better fit your needs.  

---

