4
$\begingroup$

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

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Oct 13, 2022 at 12:33
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Oct 13, 2022 at 13:40
  • 1
    $\begingroup$ @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). $\endgroup$
    – Andi Bauer
    Oct 13, 2022 at 21:09
  • $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Oct 14, 2022 at 10:33
  • $\begingroup$ @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? $\endgroup$
    – Andi Bauer
    Oct 14, 2022 at 16:02

1 Answer 1

Reset to default
3
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Andi Bauer
    Oct 29, 2022 at 14:17
  • $\begingroup$ 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.) $\endgroup$
    – Andi Bauer
    Oct 29, 2022 at 14:22
  • $\begingroup$ Just had a look into the paper you reference, 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? $\endgroup$
    – Andi Bauer
    Oct 29, 2022 at 15:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – user148606
    Oct 29, 2022 at 21:14

Your Answer

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

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