Intuitively speaking, the connection between physics and computability arises because the coarse-grained dynamics of our Universe are believed to have computational capabilities equivalent to a universal Turing machine [19–22].
I can see how this is a reasonable and useful assumption, but the universe seems to be finite in both space and time and therefore not a UTM. What convinced you otherwise?
Note that being finite in spatial extent is different from being finite in number of possible states. A Turing machine needs the latter but not the former. Finite spatial extent isn’t a blocker if your states can have arbitrarily fine precision. As an intuition pump, you could imagine a Turing machine where the nth cell of the tape has a physical width of 1/2^n. Then the whole tape has length 1 (meter?) but can fit arbitrarily long binary strings on it.
Separately, when I’ve looked into it, it seemed far from consensus whether the universe was likely to be spatially infinite or not, as in the global curvature was still consistent with being flat (= infinite space). Although, I think the “accessible” universe has finite diameter.
Lastly, I claim that whether or not something is best modeled as a Turing machine is a local fact, not a global one. A Turing machine is something that will compute the function if you give it enough tape. If the universe is finite (in the state space way) then it’s a Turing machine that just didn’t get fed enough tape. In contrast, something is better modeled as a DFA if you can locally observe that it will only ever try to access finitely many states.
Good point! My intuition was that the Berkenstein bound (https://en.wikipedia.org/wiki/Bekenstein_bound) limits the amount of information in a volume. (Or more precisely the information surrounded by an area.)
Therefore the number of states in a finite volume is also finite.
I must add: since writing this comment, a man called george pointed out to me that, when modeling the universe as a computation one must take care, to not accidentally derive ontological claims from it.
So today I would have a more ‘whatever-works-works’-attitude; UTMs, DFAs both just models, neither likely to be ontologically true.
Thanks. Obviously this claim needs some interpretation, but a UTM still seems a better model of the Universe than, say, any lower automation in the Chomsky hierarchy. For the purposes of defining entropy, it’s important that we can use a small base machine, plus a memory tape that we may think of as expanding in an online fashion.
Very good work, thank you for sharing!
I can see how this is a reasonable and useful assumption, but the universe seems to be finite in both space and time and therefore not a UTM. What convinced you otherwise?
Note that being finite in spatial extent is different from being finite in number of possible states. A Turing machine needs the latter but not the former. Finite spatial extent isn’t a blocker if your states can have arbitrarily fine precision. As an intuition pump, you could imagine a Turing machine where the nth cell of the tape has a physical width of 1/2^n. Then the whole tape has length 1 (meter?) but can fit arbitrarily long binary strings on it.
Separately, when I’ve looked into it, it seemed far from consensus whether the universe was likely to be spatially infinite or not, as in the global curvature was still consistent with being flat (= infinite space). Although, I think the “accessible” universe has finite diameter.
Lastly, I claim that whether or not something is best modeled as a Turing machine is a local fact, not a global one. A Turing machine is something that will compute the function if you give it enough tape. If the universe is finite (in the state space way) then it’s a Turing machine that just didn’t get fed enough tape. In contrast, something is better modeled as a DFA if you can locally observe that it will only ever try to access finitely many states.
Good point! My intuition was that the Berkenstein bound (https://en.wikipedia.org/wiki/Bekenstein_bound) limits the amount of information in a volume. (Or more precisely the information surrounded by an area.) Therefore the number of states in a finite volume is also finite.
I must add: since writing this comment, a man called george pointed out to me that, when modeling the universe as a computation one must take care, to not accidentally derive ontological claims from it.
So today I would have a more ‘whatever-works-works’-attitude; UTMs, DFAs both just models, neither likely to be ontologically true.
Thanks. Obviously this claim needs some interpretation, but a UTM still seems a better model of the Universe than, say, any lower automation in the Chomsky hierarchy. For the purposes of defining entropy, it’s important that we can use a small base machine, plus a memory tape that we may think of as expanding in an online fashion.