5 ms·

Maybe the universe is digital after all.

layer8 3y ago
Quantization does not imply discreteness: https://physics.stackexchange.com/questions/206790/difference-between-discretization-and-quantization-in-physics https://physics.stackexchange.com/questions/206790/differenc...
- finite_depth 3y ago
  To give a concrete example, a free particle can have any energy it likes - it's only bound states that have discrete spectra. Mathematically, this corresponds to solutions to a particular differential equation existing for particular values of energy (which appears as a constant in the equation). To use a simpler DE for an example: dx/dt = kx has solutions Ce^kt for all k, but a more complicated DE might only have solutions for some k.
- mjburgess 3y ago
  And neither alone imply computable (or 'digital'). You'd need determinism. Some reply was (improperly?) flagged, but computability requires determinism. All computable functions are functions from the integers to the integers
  - MrRolleyes 3y ago
    [dead]
  - tsimionescu 3y ago
    One of the most famous problems in computer science, P vs NP, is about non-deterministic computation. So no, computation does not require determinism - there are in fact plenty of models of non-deterministic computation. There are even models of computation where the halting problem is solvable (typically called hyper-computation). Now, it is true that computation does require some amount of determinism - if the universe were entirely non-deterministic, i.e. if there was no kind of causality and events were completely unrelated to each other, there could be no notion of computation. But no one believes in that type of universe. Adding some source of rare non-deterministic events to an otherwise deterministic universe does not hurt computation.
    - pyinstallwoes 3y ago
      By the standards of our times, our computers require a halt, so it’s arguably deterministic by today’s implementation.
      - tsimionescu 3y ago
        Halting has little to do with determinism. Our physical computers are also decidedly undeterministic, at least for practical purposes: TLS itself greatly relies on an RNG for example.
    - btilly 3y ago
      I think you picked a bad example, because the "computation" in NP is not really a computation to most of us. Most programmers think that computation means "something that can be done on a Turing machine or equivalent". It isn't hard to extend this idea to things like a true random number generator, or a quantum computer. This shows your basic point that computation need not be deterministic. But the "nondeterministic" in NP doesn't speak to an actual computation that programmers think can be done. It speaks to a computation that we'd like to be able to do, but most of us think can't be done. (There is a prize for proving that impossibility.) And while there might be models of computation where said computation can be done, few programmers would think of them as modeling an actual computation. Here alert readers might jump up and say, "Quantum computers might be able to solve NP complete problems!" True, we don't have a proof that it is impossible. But at the present time, there is no reason to believe that it is possible either. See, for instance, https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf. And so it appears that for actual computers that can be built, there is no computation matching how we'd like to solve NP complete problems.
      - tsimionescu 3y ago
        I was mainly trying to point out that the mathematical term "computation" is not limited to deterministic computers. Since the GP was mentioning computable functions as something requiring determinism, I believe they were also talking more about the mathematical notion of computation rather than physical computers. I should also note that our computers can very much solve NP-complete problems. They can't implement NP-complete algorithms to solve them, but all NP problems can be solved by a deterministic computer or a quantum computer - it just takes [much] more compute time (assuming P != NP, otherwise it may even take the same time). This is very relevant to this discussion, because in fact it is well known and proven that the non-determinism in the NP model does not give any amount of extra computational power beyond a Turing machine. That is, a non-determinstic Turing machine can solve exactly the same set of problems as a deterministic Turing machine (but, as far as it is known today, faster). The same is true of Quantum computers. Hyper-computation refers to even more fanciful mathematical models which are actually able to solve problems that a Turing machine can't solve, even with infinite time. They involve things like performing an infinite amount of Turing machine steps in one Hyper-Turing machine step, or having access to an oracle which tells you if a computation halts etc.
tlogan 3y ago
The current mainstream says that it is really not. However, they might be wrong. Hilbert space in quanum field theory is infinite-dimensional (otherwise the theory will just not work). Some physics are saying that Hilber space is not infinite-dimensional: Holography principle might imply that finite amount of information in a given region of space, potentially implying a finite-dimensional Hilbert space. And that might be some kind of pixilation.

Quantization does not imply discreteness: https://physics.stackexchange.com/questions/206790/difference-between-discretization-and-quantization-in-physics https://physics.stackexchange.com/questions/206790/differenc...

finite_depth 3y ago
To give a concrete example, a free particle can have any energy it likes - it's only bound states that have discrete spectra. Mathematically, this corresponds to solutions to a particular differential equation existing for particular values of energy (which appears as a constant in the equation). To use a simpler DE for an example: dx/dt = kx has solutions Ce^kt for all k, but a more complicated DE might only have solutions for some k.
mjburgess 3y ago
And neither alone imply computable (or 'digital'). You'd need determinism. Some reply was (improperly?) flagged, but computability requires determinism. All computable functions are functions from the integers to the integers
- MrRolleyes 3y ago
  [dead]
- tsimionescu 3y ago
  One of the most famous problems in computer science, P vs NP, is about non-deterministic computation. So no, computation does not require determinism - there are in fact plenty of models of non-deterministic computation. There are even models of computation where the halting problem is solvable (typically called hyper-computation). Now, it is true that computation does require some amount of determinism - if the universe were entirely non-deterministic, i.e. if there was no kind of causality and events were completely unrelated to each other, there could be no notion of computation. But no one believes in that type of universe. Adding some source of rare non-deterministic events to an otherwise deterministic universe does not hurt computation.
  - pyinstallwoes 3y ago
    By the standards of our times, our computers require a halt, so it’s arguably deterministic by today’s implementation.
    - tsimionescu 3y ago
      Halting has little to do with determinism. Our physical computers are also decidedly undeterministic, at least for practical purposes: TLS itself greatly relies on an RNG for example.
  - btilly 3y ago
    I think you picked a bad example, because the "computation" in NP is not really a computation to most of us. Most programmers think that computation means "something that can be done on a Turing machine or equivalent". It isn't hard to extend this idea to things like a true random number generator, or a quantum computer. This shows your basic point that computation need not be deterministic. But the "nondeterministic" in NP doesn't speak to an actual computation that programmers think can be done. It speaks to a computation that we'd like to be able to do, but most of us think can't be done. (There is a prize for proving that impossibility.) And while there might be models of computation where said computation can be done, few programmers would think of them as modeling an actual computation. Here alert readers might jump up and say, "Quantum computers might be able to solve NP complete problems!" True, we don't have a proof that it is impossible. But at the present time, there is no reason to believe that it is possible either. See, for instance, https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf. And so it appears that for actual computers that can be built, there is no computation matching how we'd like to solve NP complete problems.
    - tsimionescu 3y ago
      I was mainly trying to point out that the mathematical term "computation" is not limited to deterministic computers. Since the GP was mentioning computable functions as something requiring determinism, I believe they were also talking more about the mathematical notion of computation rather than physical computers. I should also note that our computers can very much solve NP-complete problems. They can't implement NP-complete algorithms to solve them, but all NP problems can be solved by a deterministic computer or a quantum computer - it just takes [much] more compute time (assuming P != NP, otherwise it may even take the same time). This is very relevant to this discussion, because in fact it is well known and proven that the non-determinism in the NP model does not give any amount of extra computational power beyond a Turing machine. That is, a non-determinstic Turing machine can solve exactly the same set of problems as a deterministic Turing machine (but, as far as it is known today, faster). The same is true of Quantum computers. Hyper-computation refers to even more fanciful mathematical models which are actually able to solve problems that a Turing machine can't solve, even with infinite time. They involve things like performing an infinite amount of Turing machine steps in one Hyper-Turing machine step, or having access to an oracle which tells you if a computation halts etc.

tlogan 3y ago

The current mainstream says that it is really not. However, they might be wrong. Hilbert space in quanum field theory is infinite-dimensional (otherwise the theory will just not work). Some physics are saying that Hilber space is not infinite-dimensional: Holography principle might imply that finite amount of information in a given region of space, potentially implying a finite-dimensional Hilbert space. And that might be some kind of pixilation.