Quantization does not imply discreteness: https://physics.stackexchange.com/questions/206790/differenc...
You'd need determinism.
Some reply was (improperly?) flagged, but computability requires determinism.
All computable functions are functions from the integers to the integers
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.
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. 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.
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.
Few people really think of that as computation.
But I agree that there are real examples of physically possible computation which are not deterministic. The most widely used being true random number generators. And so theoretical computability is not necessarily the right model for the real world.
Hyper-computation is much more exotic, though, I'll give you that.
The question of P vs NP is not whether we haven't determined if we can do a particular computation (either at all or in polynomial time). It's whether a deterministic Turing machine could solve in polynomial time the same class of problems that we _know_ a nondeterministic Turing machine could solve in polynomial time.
Of course, the nondeterministic Turing machine is not a physically realistic model of computation.
If the latter, please be specific about what misunderstanding you think I might have.
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).
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.
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.
If instead you are simply referring to the observation that physical computers have a finite amount of memory and thus we can solve the halting problem in finite time by simply iterating over all possible configurations, that is a somewhat uninteresting observation - since if we are already talking about real physical constraints, that algorithm is entirely useless for even the simplest computers from the 50s and 60s. It's basically equivalent to saying "any program will halt, because the sun will destroy all computers on Earth when it goes supernova".
More interestingly, it turns out that there are some finitist versions of the halting problem for finite-tape Turing machines, and they act as a similar kind of limit. That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states (and this also requires a finite-state Turing machine with a larger tape than the one under analysis).
This result can actually be used in a very similar way to the infinite-tape halting problem: it 100% guarantees that, if your system is equivalent to a Turing machine with tape length N and M possible symbols, it will take more than N^M computational steps to check whether an arbitrary program holds. This can be used to prove that it is effectively impossible to check if a program halts, much the same as the "true" halting problem is used to prove that it is actually impossible to check.
For an example, an arbitrary program for a computer with as much memory as the infamous "640KB is enough for anyone" quote would require at least 640,000^255 (~10^1480) computational steps to check if it halts. So, we can just as easily say it is impossible to check and we wouldn't be far off.
This is very different from something like a total language (e.g. Idris) or a DFA, where it is actually possible to relatively quickly verify whether a program halts.
It is, but that's not the observation I was making. You only mentioned one way of solving the problem, but that's not the only way.
> That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states
What do you mean by all possible states? If you mean literally all possible states, that's not true. I mean, yes, you could iterate over all possible states to solve that problem, but that's probably the least efficient way to solve it.
There are already-known algorithms which always solve the Halting problem for machines with finite state, and they don't need to iterate over all possible states. They do, however, need to iterate over all state transitions that the machine actually goes through (multiple times, even). However, these algorithms that I'm mentioning (i.e. cycle detection algorithms) are also quite dumb. They don't exploit any knowledge about the state transitions in order to analyze whether the machines halt or not, they just simulate the machine step by step (this is due to the definition of the cycle detection problem itself, which does not allow inspecting the program).
In principle, and even in practice, it's possible to make those algorithms significantly more efficient, at least for many of the machines (i.e. programs) that we care about.
I suspect it is not possible to make such a (fully automatic) algorithm significantly more efficient for all possible programs (even the nonsensical ones), although I don't think such a proof exists (if it does, I would like to see it). The closest I've been pointed to is a paper possibly implying that such an algorithm would have to be EXPTIME-complete, although even the person that pointed me to that paper had some difficulty interpreting it -- and even if that were true, that says nothing about its real-world efficiency.
> That is, it turns out that the only way to verify whether an arbitrary finite-state Turing machine will halt on a specific input is to check all possible states
Can you point me to a source that proves this claim? Not only I'm doubting it, but even if you are right, I'd be really interested in reading such a proof.
> For an example, an arbitrary program for a computer with as much memory as the infamous "640KB is enough for anyone" quote would require at least 640,000^255 (~10^1480) computational steps to check if it halts.
Again, I'm wondering why you are claiming that the only possible algorithms which can check whether arbitrary finite-state programs halt have to iterate over all possible states (or even all the actual state transitions).
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.