4

I just read the Wikipedia article on Rule 110 and there was a short remark that the simplicity of that rule might imply that it can exist in physical systems in nature. "Physical systems may also be capable of universality— meaning that many of their properties will be undecidable, and not amenable to closed-form mathematical solutions." I have two questions:

  1. On which scales could such a system occur? Could parts of our brains be turing complete? Could movements of stars and galaxies follow simple rules like that?
  2. What kind of properties wouldn’t we be able to decide and what would be the implications of it?
  • 1
    Related: Digital Physics and A New Kind of Science – user3164 Jun 4 '13 at 12:48
  • 3
    The formal definition of a Turing machine includes an infinite amount of memory, so in that sense the answer to #1 is no. But in reality, the theoretical idealization represented by Turing completeness often matches up well with facts about non-idealized, finite systems such as computers. Turing machines are also supposed to be deterministic, which the brain probably is not. Re #2, have you read, e.g., en.wikipedia.org/wiki/Turing_completeness ? – Ben Crowell Jun 5 '13 at 21:42
  • Digital Physics, I think it just put every single thought I've had about life on one wikipedia page. – KDecker Jun 6 '13 at 14:27
  • @Gugg: I think Digital Physics goes further than my question. I only asked about systems that just happen to be universal within the laws of the universe. Thanks for the very interesting links, though. – Lenar Hoyt Jun 17 '13 at 21:00
3

As Ben Crowell points out, any physical implementation of a Turing machine in a finite universe can only be an approximation because a Turing machine is defined as having infinite memory. And it is also true that a finite approximation to a Turing machine often behaves just like a Turing machine. But there's one difference that is important to your questions. On a finite approximation to a Turing machine the halting problem is decidable. That means that the presence of a rule 110 system (or any other Turing complete system) in a finite universe would not imply the existence of undecidable properties.

  • The memory of a Turing machine is unbounded, not infinite. – Bob Dec 30 '18 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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