3 ms·

And neither alone imply computable (or 'digital'). You'd need determinism. Some reply was (improperly?) flagged, but computability requires determinism. All

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.
- someplaceguy 3y ago
  > There are even models of computation where the halting problem is solvable (typically called hyper-computation). BTW, it's not only hyper-computation that can solve the halting problem. The halting problem is decidable in models of computation that have finite state (although the decider machine does need more state than the machine being analyzed).
  - tsimionescu 3y ago
    The term "the halting problem" typically refers to the problem "given a Turing machine and a starting state of the tape, determine if the Turing machine will halt". There are other versions of the halting problem for systems that are more limitted than a Turing machine, such as finite automata ("given a finite automaton and an initial state, determine if the automaton will halt"). Some of these other versions are indeed solvable, such as the one you mention. But these are different problems, not the same problem as THE halting problem. As far as it is known today, all such systems are strictly less powerful than Turing machines (that is, for any system where it is provable if a computation in that system halts, there are problems that it can't solve that a Turing machine can) - this is known as the Church-Turing thesis. Hyper-computation refers to models of computation where THE halting problem (does an arbitrary Turing machine halt) is solvable.
    - someplaceguy 3y ago
      I meant "the halting problem" as in the informal description of the problem, e.g. as in how it is described in Wikipedia: "the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever". If you take that description at face value and consider a model of computation with finite state (like real-world computers have), then it is decidable. If you take the usual formal description of the halting problem, which like you said, is specifically defined over Turing machines (i.e. a theoretical model which assumes you can have a machine with literally infinite state, which is impossible to construct in our universe), then yes, you'd need hyper-computation to solve that.

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.
someplaceguy 3y ago
> There are even models of computation where the halting problem is solvable (typically called hyper-computation). BTW, it's not only hyper-computation that can solve the halting problem. The halting problem is decidable in models of computation that have finite state (although the decider machine does need more state than the machine being analyzed).
- tsimionescu 3y ago
  The term "the halting problem" typically refers to the problem "given a Turing machine and a starting state of the tape, determine if the Turing machine will halt". There are other versions of the halting problem for systems that are more limitted than a Turing machine, such as finite automata ("given a finite automaton and an initial state, determine if the automaton will halt"). Some of these other versions are indeed solvable, such as the one you mention. But these are different problems, not the same problem as THE halting problem. As far as it is known today, all such systems are strictly less powerful than Turing machines (that is, for any system where it is provable if a computation in that system halts, there are problems that it can't solve that a Turing machine can) - this is known as the Church-Turing thesis. Hyper-computation refers to models of computation where THE halting problem (does an arbitrary Turing machine halt) is solvable.
  - someplaceguy 3y ago
    I meant "the halting problem" as in the informal description of the problem, e.g. as in how it is described in Wikipedia: "the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever". If you take that description at face value and consider a model of computation with finite state (like real-world computers have), then it is decidable. If you take the usual formal description of the halting problem, which like you said, is specifically defined over Turing machines (i.e. a theoretical model which assumes you can have a machine with literally infinite state, which is impossible to construct in our universe), then yes, you'd need hyper-computation to solve that.