church-turing is a a thesis, not a logical theorem.
You pointed me to a proof that the halting problem is unsolvable by a Turing Machine, not that hypercomputers are impossible.
The critic Martin Davis mentioned in wikipedia has an article criticizing a kind of attempt at showing the feasibility of hypercomputers. Thats fine. If there was a well-known logical proof of its unfeasibility, his task would be much simpler though. The purely logical argument hasnt been made as far as i know and as far as you were able to show.
You would need to invent a complexity class larger than R, one that contains more than countably infinite programs. Those, too, can be diagonalised, there would still be incomputable functions. Our whole argument would repeat with that complexity class instead of R. Rinse and repeat. By induction, nothing changes, Q.E.D.
You know what? I’m going to plant a nuke under your ass: Turing machines can’t exist, either. Any finite machine can be expressed as a DFA. We’re nothing but a bunch of complicated regexen.
This whole time we were talking about potentiality, not reality; in terms that are convenient theory, not physics. I see no reason to extend potentiality to uncountable infinities when we can’t even exploit countable infinity.
Side note, and this might actually change my mind on things regarding “Is R all that we’ll ever need”: If people manage to get an asymptotic speedup out of quantum computers. The question is whether the parallelism inherent in operations on qbits is eaten up by noise, more or less the more states you load onto the qbits, the more fuzzy the results get, because the universe has a maximum amount of computational oomph it spends on a particle or per unit volume or whatever the right measure is. Of course, before we’d need to move past R we’d first have to load an actually infinite number of states into a qbit and I don’t really see that happening. A gazillion? Doubtful, but thinkable. An infinite number in finite time? Not while we have fat fingers typing away on macroscopic keyboards.
Why do you need uncountable infinities for hypercomputers, though?. I see that Martin Davis criticism has to do with that approach, and I agree this approach seems silly. But, it doesnt seem to cover all potential fronts for hypercomputers. Im not talking about current approaches to quantum computing either. What if some yet unknown physical law makes arrangements of particles somehow solve the first order logic validity problem, which is also not in R? Doesnt involve uncountable infinity at all.
Again, im not saying its possible, just that theres no purely logical proof of impossibility, thats all.
Validity is RE (semidecidable), Satisfiability is undecidable.
How do we figure out that your fancy new law is actually the oracle you claim it is? It could be lying to us, to establish the thing as an oracle we’d have to be able to either inspect it or unit-test it over the whole infinite range.
Right, validity is semidecidable, just like the halting problem.
We might never know for certain that any natural law is true, we might never be certain that that oracle actually solves validity. But that doesnt prevent the oracle from working. My point is that its existence is possible, not that we will ever be able to trust it.
Besides, we dont know that the physical laws we work with today are true, but we nevetheless use them for practical purpuses all the time.
Not my point… and you know it.
My point is that even if we consider that proven theorems are known facts, we still dont know if hypercomputers are infeasible. We know, however, that i’ll never write python code that decides Validity because it is not (classically) decidable. But we have no theorems on the impossibility of hypercomputation.
church-turing is a a thesis, not a logical theorem. You pointed me to a proof that the halting problem is unsolvable by a Turing Machine, not that hypercomputers are impossible.
The critic Martin Davis mentioned in wikipedia has an article criticizing a kind of attempt at showing the feasibility of hypercomputers. Thats fine. If there was a well-known logical proof of its unfeasibility, his task would be much simpler though. The purely logical argument hasnt been made as far as i know and as far as you were able to show.
You would need to invent a complexity class larger than R, one that contains more than countably infinite programs. Those, too, can be diagonalised, there would still be incomputable functions. Our whole argument would repeat with that complexity class instead of R. Rinse and repeat. By induction, nothing changes, Q.E.D.
A hypercomputer has its own class of unsolvable problems, I agree. That doesnt mean that a hypercomputer cannot exist.
You know what? I’m going to plant a nuke under your ass: Turing machines can’t exist, either. Any finite machine can be expressed as a DFA. We’re nothing but a bunch of complicated regexen.
This whole time we were talking about potentiality, not reality; in terms that are convenient theory, not physics. I see no reason to extend potentiality to uncountable infinities when we can’t even exploit countable infinity.
Side note, and this might actually change my mind on things regarding “Is R all that we’ll ever need”: If people manage to get an asymptotic speedup out of quantum computers. The question is whether the parallelism inherent in operations on qbits is eaten up by noise, more or less the more states you load onto the qbits, the more fuzzy the results get, because the universe has a maximum amount of computational oomph it spends on a particle or per unit volume or whatever the right measure is. Of course, before we’d need to move past R we’d first have to load an actually infinite number of states into a qbit and I don’t really see that happening. A gazillion? Doubtful, but thinkable. An infinite number in finite time? Not while we have fat fingers typing away on macroscopic keyboards.
Oh no! You got me there!
Why do you need uncountable infinities for hypercomputers, though?. I see that Martin Davis criticism has to do with that approach, and I agree this approach seems silly. But, it doesnt seem to cover all potential fronts for hypercomputers. Im not talking about current approaches to quantum computing either. What if some yet unknown physical law makes arrangements of particles somehow solve the first order logic validity problem, which is also not in R? Doesnt involve uncountable infinity at all. Again, im not saying its possible, just that theres no purely logical proof of impossibility, thats all.
Validity is RE (semidecidable), Satisfiability is undecidable.
How do we figure out that your fancy new law is actually the oracle you claim it is? It could be lying to us, to establish the thing as an oracle we’d have to be able to either inspect it or unit-test it over the whole infinite range.
Right, validity is semidecidable, just like the halting problem.
We might never know for certain that any natural law is true, we might never be certain that that oracle actually solves validity. But that doesnt prevent the oracle from working. My point is that its existence is possible, not that we will ever be able to trust it.
Besides, we dont know that the physical laws we work with today are true, but we nevetheless use them for practical purpuses all the time.
I mean if the point is that we know that we know nothing then I’ll agree.
Not my point… and you know it. My point is that even if we consider that proven theorems are known facts, we still dont know if hypercomputers are infeasible. We know, however, that i’ll never write python code that decides Validity because it is not (classically) decidable. But we have no theorems on the impossibility of hypercomputation.