4 ms·

If the universe is finite, does that mean every problem is a constant time algorithm?

deleted 5y ago
[deleted]
emerged 5y ago
We do seem to spend an awful lot of time worrying about infinities when it appears the cosmological horizon is finite. But I guess if we find some way around that we will be prepared.
- raattgift 5y ago
  In an accelerating expanding universe like the one we appear to occupy (and the one modelled by our current "concordance" standard model of comology), the comoving horizon is at constant comoving distance. Cast into more Earth-centric coordinates, it is at a finite spatial distance at all finite times. However, there is no reason to expect that a timelike worldline rooted at "here and now" (converting a chosen comoving coordinate into the origin of spherical coordinates for a Eulerian observer) cannot be extended into the infinite future, and at +infinite time the horizon will be at an infinite spatial distance in this system of coordinates. We don't even need to say anything about the matter content of the Hubble volume at any time, anything about -infinite time, or anything about how various measures of entropy fit in; all of these can generate infinities that defy easy (and possibly any) removal in a universe similar to the concordance model. A taste of this can be found at https://en.wikipedia.org/wiki/Cosmological_horizon#Future_horizon https://en.wikipedia.org/wiki/Cosmological_horizon#Future_ho... More deeply and technically, Baez's "Struggles with the Continuum" is great A smooth manifold tends to generate infinities and infinitesimals, and all our fundamental physical descriptions of the universe we inhabit are (at least at present) defined on a Lorentzian spacetime, which is a smooth manifold. He discusses practical reasons to [a] worry about infinities and [b] to work with them anywhere because they might not be removable. https://arxiv.org/abs/1609.01421 https://arxiv.org/abs/1609.01421 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).
bawolff 5y ago
No,because you don't have to execute a procedure in order to construct it. I.e. we can talk about Turing machines with infinite tapes without actually making one with an infinite tape.
- Hercuros 5y ago
  It's also important to realize that the standard Turing machine doesn't actually have an infinite tape, but rather it has a tape that can grow to hold an arbitrarily long, but still finite, sequence. At any point during the execution of the Turing machine, only a finite part of the tape will be occupied. So we can construct approximations of it in the sense that we can create computers with varying, finite amounts of RAM. This might seem like a pedantic/obvious point to make, but it is actually also possible to design abstract computational machines that operate on truly infinite quantities, like a machine that has random access to an infinite, uncomputable sequence. From a simplicity perspective, it also makes more sense to consider machines with an arbitrarily large amount of RAM (you can always hotplug more RAM), compared to setting some arbitrary limit because that is the most RAM we happen to be able to achieve in this universe.
  - hypertele-Xii 5y ago
    > random access to an infinite, uncomputable sequence. I.e. a (cryptographic) random number generator?
davrosthedalek 5y ago
I think you also need to assume that spacetime is discretized. Otherwise, two particles have already an infinite phase space (their distance). I don't think the uncertainty principle is enough.

deleted 5y ago

[deleted]

We do seem to spend an awful lot of time worrying about infinities when it appears the cosmological horizon is finite. But I guess if we find some way around that we will be prepared.

raattgift 5y ago
In an accelerating expanding universe like the one we appear to occupy (and the one modelled by our current "concordance" standard model of comology), the comoving horizon is at constant comoving distance. Cast into more Earth-centric coordinates, it is at a finite spatial distance at all finite times. However, there is no reason to expect that a timelike worldline rooted at "here and now" (converting a chosen comoving coordinate into the origin of spherical coordinates for a Eulerian observer) cannot be extended into the infinite future, and at +infinite time the horizon will be at an infinite spatial distance in this system of coordinates. We don't even need to say anything about the matter content of the Hubble volume at any time, anything about -infinite time, or anything about how various measures of entropy fit in; all of these can generate infinities that defy easy (and possibly any) removal in a universe similar to the concordance model. A taste of this can be found at https://en.wikipedia.org/wiki/Cosmological_horizon#Future_horizon https://en.wikipedia.org/wiki/Cosmological_horizon#Future_ho... More deeply and technically, Baez's "Struggles with the Continuum" is great A smooth manifold tends to generate infinities and infinitesimals, and all our fundamental physical descriptions of the universe we inhabit are (at least at present) defined on a Lorentzian spacetime, which is a smooth manifold. He discusses practical reasons to [a] worry about infinities and [b] to work with them anywhere because they might not be removable. https://arxiv.org/abs/1609.01421 https://arxiv.org/abs/1609.01421 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).

bawolff 5y ago

No,because you don't have to execute a procedure in order to construct it. I.e. we can talk about Turing machines with infinite tapes without actually making one with an infinite tape.

Hercuros 5y ago
It's also important to realize that the standard Turing machine doesn't actually have an infinite tape, but rather it has a tape that can grow to hold an arbitrarily long, but still finite, sequence. At any point during the execution of the Turing machine, only a finite part of the tape will be occupied. So we can construct approximations of it in the sense that we can create computers with varying, finite amounts of RAM. This might seem like a pedantic/obvious point to make, but it is actually also possible to design abstract computational machines that operate on truly infinite quantities, like a machine that has random access to an infinite, uncomputable sequence. From a simplicity perspective, it also makes more sense to consider machines with an arbitrarily large amount of RAM (you can always hotplug more RAM), compared to setting some arbitrary limit because that is the most RAM we happen to be able to achieve in this universe.
- hypertele-Xii 5y ago
  > random access to an infinite, uncomputable sequence. I.e. a (cryptographic) random number generator?

davrosthedalek 5y ago

I think you also need to assume that spacetime is discretized. Otherwise, two particles have already an infinite phase space (their distance). I don't think the uncertainty principle is enough.