There are several papers that propose that the universe itself is analogous to a cellular automata. Obviously, these papers assume that the universe is computable.

But is it there any cosmological cellular automata models that would allow uncomputable laws/processes/functions/numbers/things...etc to exist in that universe? For example, cellular automata universes where there would be truly black hole-singularities (which are uncomputable)?

Maybe Konrad Zuse's cellular automata could do the job?


Or maybe some variation of Conway's game of life? https://en.m.wikipedia.org/wiki/Conway%27s_Game_of_Life

Or maybe we could build one using 't Hooft's cellular automata frameworks

https://arxiv.org/abs/gr-qc/9903084 https://arxiv.org/abs/1405.1548

  • $\begingroup$ CAs already admit several uncomputable problems. For example, the reversibility of 2D (standard) CA is undecidable. What exactly do you wish to achieve? $\endgroup$ – dkaeae Dec 31 '18 at 15:29
  • $\begingroup$ If the "CA Universe" is bounded then everything is computable. If it is infinite then there can be parts of it that behave like a Turing machine and (by the undecidability of the Halting problem) no other part would be able to "calculate" if those parts will stop evolving. $\endgroup$ – Marzio De Biasi Dec 31 '18 at 20:38
  • 1
    $\begingroup$ I do not doubt there are research-level papers about mathematical modelling of the universe using cellular automata. What I was trying to communicate is that this particular question is not research-level until it is made sufficiently precise. For instance, you say "true black hole singularities are uncomputable". What is that supposed to mean, precisely? Do you have a precise definition of "black hole" that is applicable outside of the general theory of relativity, so that we can apply it to a model based on cellular automata? $\endgroup$ – Andrej Bauer Jan 13 at 10:44
  • 1
    $\begingroup$ To continue: What is the difference between "true black hole" and "black hole"? What does it mean for a black hole to be uncomputable? Can a star, or a galaxy by "uncomputable" and what does that mean? You can't just say these things without being mathematically precise, not on this forum. $\endgroup$ – Andrej Bauer Jan 13 at 10:46
  • 1
    $\begingroup$ Consider Conway's game of life on an infinite plane. It is known that it can simulate a Turing machine. On the sixth day of creation, put in the universe a Turing machine whose halting problem is undecidable, and start the universe. Ergo, you have got yourself a game-of-life universe in which a non-computable phenomenon "exists" (namely, we can't compute whether the machine will halt). This quesiton is not research-level because it's either unclear or trivial, depending on which way you want to take it. $\endgroup$ – Andrej Bauer Jan 13 at 10:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.