Computation with cellular automata in practice

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

• 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. Oct 13, 2022 at 12:33
• 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. Oct 13, 2022 at 13:40
• @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). Oct 13, 2022 at 21:09
• 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. Oct 14, 2022 at 10:33
• @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? Oct 14, 2022 at 16:02