Epistemic status: the halting problem may actually still hold for quantum computers, I have no idea. I’m mostly interested in pointing out the sneakiness of assumptions.
The Halting Problem is the following: imagine some class of algorithms A. Can we have an algorithm F which takes as inputs a description of another algorithm A and an input I for that algorithm, and outputs either true, if A(I) halts or false, if A(I) doesn’t.
The original solution (by Alan Turing): no by contradiction. Imagine we have a such an algorithm. Now imagine a reversing algorithm R, which halts if given false as an input, and runs forever if given true as an input. Imagine also a copier algorithm C, which duplicates the input (so C(x)=(x,x), and always halts.
Now imagine we string these algorithms together, R(F(C(x)))=G(x). What happens if we feed G into G? Well C(G)=(G,G), then F(G,G) refers to whether G halts when given the input G. So does G halt when fed G? Think about this for a moment.
Imagine G(G) halts. Then F(G,G)=true, which is passed to R, which runs forever.
Imagine G(G) doesn’t halt. Then F(G,G)=false, which is passed to R, which halts.
So we have a paradox.
This works for any class of algorithm you can imagine, it’s a fantastically general proof which says nothing about the nature of the algorithms at hand.
Or does it!?
Note the hidden assumption. That R and C exist. What if they don’t?
For a string of bits, or a Turing machine (as the problem was originally posed) the existence of C is trivial. But for a string of qubits, it isn’t. The no-cloning theorem states that “it is impossible to create an independent and identical copy of an arbitrary unknown quantum state”. So in fact the standard proof of the halting problem does not apply to quantum computers.
This is possibly the sneakiest assumption I’ve ever seen snuck into an argument! A proof which seems general to any algorithm class falls down because you can’t have a quantum photocopier!
I will repeat that I am not actually making a claim about quantum computers here. I have no idea if the Gödel’s Incompleteness-based proof holds. I am merely pointing out the sneakiness of this assumption.
The Halting Problem and the Impossible Photocopier
Epistemic status: the halting problem may actually still hold for quantum computers, I have no idea. I’m mostly interested in pointing out the sneakiness of assumptions.
The Halting Problem is the following: imagine some class of algorithms A. Can we have an algorithm F which takes as inputs a description of another algorithm A and an input I for that algorithm, and outputs either true, if A(I) halts or false, if A(I) doesn’t.
The original solution (by Alan Turing): no by contradiction. Imagine we have a such an algorithm. Now imagine a reversing algorithm R, which halts if given false as an input, and runs forever if given true as an input. Imagine also a copier algorithm C, which duplicates the input (so C(x)=(x,x), and always halts.
Now imagine we string these algorithms together, R(F(C(x)))=G(x). What happens if we feed G into G? Well C(G)=(G,G), then F(G,G) refers to whether G halts when given the input G. So does G halt when fed G? Think about this for a moment.
Imagine G(G) halts. Then F(G,G)=true, which is passed to R, which runs forever.
Imagine G(G) doesn’t halt. Then F(G,G)=false, which is passed to R, which halts.
So we have a paradox.
This works for any class of algorithm you can imagine, it’s a fantastically general proof which says nothing about the nature of the algorithms at hand.
Or does it!?
Note the hidden assumption. That R and C exist. What if they don’t?
For a string of bits, or a Turing machine (as the problem was originally posed) the existence of C is trivial. But for a string of qubits, it isn’t. The no-cloning theorem states that “it is impossible to create an independent and identical copy of an arbitrary unknown quantum state”. So in fact the standard proof of the halting problem does not apply to quantum computers.
This is possibly the sneakiest assumption I’ve ever seen snuck into an argument! A proof which seems general to any algorithm class falls down because you can’t have a quantum photocopier!
I will repeat that I am not actually making a claim about quantum computers here. I have no idea if the Gödel’s Incompleteness-based proof holds. I am merely pointing out the sneakiness of this assumption.