3

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?
Improve this question
4
  • 1
    Related: Digital Physics and A New Kind of Science
    – user3164
    Commented Jun 4, 2013 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 ?
    – user3814
    Commented Jun 5, 2013 at 21:42
  • Digital Physics, I think it just put every single thought I've had about life on one wikipedia page.
    – KDecker
    Commented Jun 6, 2013 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
    Commented Jun 17, 2013 at 21:00

1 Answer 1

Reset to default
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.

Improve this answer
1
  • The memory of a Turing machine is unbounded, not infinite.
    – Bob
    Commented Dec 30, 2018 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .