The incompleteness theorem says that a consistent axiomatic formal system satisfying some conditions cannot be complete, so the universe as a formal system (supposed consistent, complete, expressive enough, …) cannot be axiomatized.
external oracles
What do you mean external?
The possibility of using physical phenomena as oracles for solving classically uncomputable problems in the real world is an open question. If you think this is logically as impossible as a four sided triangle you should give sources for this claim, not just some vague statements involving the incompleteness theorem. Prove this logical impossibility or give sources, thats all im asking.
Who says you cant take a first order logic sentence, codify it as a particular arrangement of certain particles and determine if the sentence was valid by observing how the particles behave? Some undiscovered physical phenomenon might make this possible… who knows. It would make possible the making of a real world machine that surpasses the turing machine in computability, no? How is this like a four sided triangle? The four sided triangle is logically impossible, but a hypercomputer is logically possible. The question is whether it is also physically possible, which is an open question.
The incompleteness theorem says that a consistent axiomatic formal system satisfying some conditions cannot be complete, so the universe as a formal system (supposed consistent, complete, expressive enough, …) cannot be axiomatized.
It can also be axiomisable but inconsistent. In principle, that is, but as said you’d annoy a lot of physicists.
What do you mean external?
As in the previously mentioned summation of the results of theoretical hypercomputation: “If uncomputable inputs are permitted, then uncomputable outputs can be produced”. Those oracles would be the input.
The possibility of using physical phenomena as oracles for solving classically uncomputable problems in the real world is an open question.
If they exist, then they can be used. We do that all the time in the sense that we’re pretending they exist, it’s useful to e.g. prove that an algorithm is optimal: We compare an implementable algorithm it with one that can e.g. see the future, can magically make all the right choices, etc. But they don’t exist.
If you think this is logically as impossible as a four sided triangle you should give sources for this claim
I already pointed you to an easy-going explanation of the proof by diagonalization. I’m not going to sit here and walk you through your homework. In fact I have given up explaining it to you because you’re not putting in the work, hence why I resorted to an analogy, the four-sided triangle.
Some undiscovered physical phenomenon might make this possible… who knows.
Are all thinkable phenomena possible? Can there be four-sided triangles?
The four sided triangle is logically impossible, but a hypercomputer is logically possible.
That is an assertion without substantiation, and for what it’s worth you’re contradicting the lot of Computer Science. A hypercomputer is a more involved, not as intuitive, four-sided triangle.
If you think that it’s logically possible, go back to that proof I pointed you to. I will not do so again.
The diagonalization argument you pointed me to is about the uncomputability of the halting problem. I know about it, but it just proves that no turing machine can solve the halting problem. Hypercomputers are supposed to NOT be turing machines, so theres no proof of the impossibility of hypercomputers to be found there.
I know diagonalization proofs, they dont prove what you say they prove.
Cite any computer science source stating that the existence of hypercomputers are logically impossible. If you keep saying it follows from some diagonalization argument without showing how or citing sources ill move on from this.
I know diagonalization proofs, they dont prove what you say they prove.
Not proofs, plural, not the category. This specific one. The details involve a method to enumerate all programs which is the hard part. IIRC the lecturer doesn’t actually get into that, though. Read the original papers if you want nobody found issue with them in nearly 100 years.
Cite any computer science source stating that the existence of hypercomputers are logically impossible.
Church-Turing is a fundamental result of CS, arguably its founding one, and I will not suffer any more denial of it. It’s like asking a physicist to provide a citation for the non-existence of telekinesis: You fucking move something with your mind, then we’ll talk. In the meantime, I’m going to judge you to be nuts.
Feel free to have a look at the criticism section of Wikipedia’s hypercomputation article, though. Feel free to read everything about it but don’t pester me with that nonsense. Would you even have known about it if I didn’t mention off-hand that it was bunk, serves me right I guess.
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.
The incompleteness theorem says that a consistent axiomatic formal system satisfying some conditions cannot be complete, so the universe as a formal system (supposed consistent, complete, expressive enough, …) cannot be axiomatized.
What do you mean external?
The possibility of using physical phenomena as oracles for solving classically uncomputable problems in the real world is an open question. If you think this is logically as impossible as a four sided triangle you should give sources for this claim, not just some vague statements involving the incompleteness theorem. Prove this logical impossibility or give sources, thats all im asking.
Who says you cant take a first order logic sentence, codify it as a particular arrangement of certain particles and determine if the sentence was valid by observing how the particles behave? Some undiscovered physical phenomenon might make this possible… who knows. It would make possible the making of a real world machine that surpasses the turing machine in computability, no? How is this like a four sided triangle? The four sided triangle is logically impossible, but a hypercomputer is logically possible. The question is whether it is also physically possible, which is an open question.
It can also be axiomisable but inconsistent. In principle, that is, but as said you’d annoy a lot of physicists.
As in the previously mentioned summation of the results of theoretical hypercomputation: “If uncomputable inputs are permitted, then uncomputable outputs can be produced”. Those oracles would be the input.
If they exist, then they can be used. We do that all the time in the sense that we’re pretending they exist, it’s useful to e.g. prove that an algorithm is optimal: We compare an implementable algorithm it with one that can e.g. see the future, can magically make all the right choices, etc. But they don’t exist.
I already pointed you to an easy-going explanation of the proof by diagonalization. I’m not going to sit here and walk you through your homework. In fact I have given up explaining it to you because you’re not putting in the work, hence why I resorted to an analogy, the four-sided triangle.
Are all thinkable phenomena possible? Can there be four-sided triangles?
That is an assertion without substantiation, and for what it’s worth you’re contradicting the lot of Computer Science. A hypercomputer is a more involved, not as intuitive, four-sided triangle.
If you think that it’s logically possible, go back to that proof I pointed you to. I will not do so again.
The diagonalization argument you pointed me to is about the uncomputability of the halting problem. I know about it, but it just proves that no turing machine can solve the halting problem. Hypercomputers are supposed to NOT be turing machines, so theres no proof of the impossibility of hypercomputers to be found there.
I know diagonalization proofs, they dont prove what you say they prove. Cite any computer science source stating that the existence of hypercomputers are logically impossible. If you keep saying it follows from some diagonalization argument without showing how or citing sources ill move on from this.
Not proofs, plural, not the category. This specific one. The details involve a method to enumerate all programs which is the hard part. IIRC the lecturer doesn’t actually get into that, though. Read the original papers if you want nobody found issue with them in nearly 100 years.
Church-Turing is a fundamental result of CS, arguably its founding one, and I will not suffer any more denial of it. It’s like asking a physicist to provide a citation for the non-existence of telekinesis: You fucking move something with your mind, then we’ll talk. In the meantime, I’m going to judge you to be nuts.
Feel free to have a look at the criticism section of Wikipedia’s hypercomputation article, though. Feel free to read everything about it but don’t pester me with that nonsense. Would you even have known about it if I didn’t mention off-hand that it was bunk, serves me right I guess.
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.