4 ms·

I'm not going to claim I understand the complexity class discussion here, but what I find most surprising is the claim that this would make the halting problem

I'm not going to claim I understand the complexity class discussion here, but what I find most surprising is the claim that this would make the halting problem solvable. There's a fairly straightforward proof by contradiction that it's not: https://en.wikipedia.org/wiki/Halting_problem#Proof_concept https://en.wikipedia.org/wiki/Halting_problem#Proof_concept So how would the new finding override this? Or is it just <wiggles fingers> quantum magic that's running the proof in parallel in infinite entangled multiverses or something?

scythe 7y ago
There are plenty of oracle solutions to the halting problem. The simplest one uses the bits of Chaitin’s constant, an incomputable number, to solve Halting in polynomial time. Of course, these solutions cannot be physically implemented (eg. calculating N bits of Chaitin’s constant requires solving the halting problem for all N-bit machines, so the algorithm is “circular”).
- 9nGQluzmnq3M 7y ago
  Yes, but my layman's understanding is that the oracle is a theoretical construct that knows in advance what programs halt and what don't -- but as you note, the real-world issue is that such oracles don't exist. My question remains, how does this tie back to the proof? Is there a path to building such an oracle now?
  - dwohnitmok 7y ago
    No there is still no path to constructing such an oracle. The paper basically presents a result built off of a less trustworthy oracle (or set of oracles) that can potentially lie, but that still has unlimited computational power.
deleted 7y ago
[deleted]
jimhefferon 7y ago
Godel's Lost Letter suggests that these are not finite machines
lidHanteyk 7y ago
What this means is that, if you are confronted by a group of people, traditionally called provers, and you limit their collaboration in a certain way (here, by entangling some qubits and only using the entangled state for "communication"), then they can nonetheless prove to you in an interactive discussion that they know how to solve some Halting-equivalent problem. This does not give provers any new tricks for solving hard problems. This puts a ceiling on the power of this sort of prover-and-verifier proof and what it can show. There are problems harder than Halting (that is, that are hard even with oracles for Halting [0]) and MIP* doesn't contain them. [0] https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Turing_jump
hansdieter1337 7y ago
making the halting problem solvable if you have quantum entangled oracles that know everything. Welcome to complexity theory :) Reminds me of the proof that time traveling turing machines can solve the halting problem.
- sterlind 7y ago
  are those the Turing machines which can send an unlimited number of qubits back through a closed timelike curve? that result was mind-blowing. It only required classical computers, however, at least in the formulation I saw. Reversible computing in general seems weird when it comes to time.
dwohnitmok 7y ago
I have absolutely no knowledge of quantum mechanics beyond a pop-sci understanding, and I've only briefly skimmed the abstract and intro of the paper, but my impression is that it doesn't override this. Rather the direction of significance runs the other way; we now have strict limits on what kind of things in "quantum magic" are computable. Also note that this result still ultimately involves oracles with unlimited computational power (it does not construct these oracles). The interesting part is that these oracles are potentially malicious and can lie and it is the verifier's job to come up with a strategy to play an interactive game with these oracles to tease out the real answer (with a high probability of correctness).
pron 7y ago
I don't think the claim is that such a device with a finite amount of information could decide halting. As far as I understand, it could replace the infinite time required to classically decide halting with infinite information entanglement, neither can be put into real physical use.
naasking 7y ago
> but what I find most surprising is the claim that this would make the halting problem solvable. I don't think this is correct. I believe that it only makes the Halting Problem verifiable to a simple verifier dealing with two entangled verifiers. So a verifier typically has to rely on an oracle to solve the Halting Problem, but this new proof eliminates the need for that trust by a verification procedure using two entangled oracles.

scythe 7y ago

There are plenty of oracle solutions to the halting problem. The simplest one uses the bits of Chaitin’s constant, an incomputable number, to solve Halting in polynomial time. Of course, these solutions cannot be physically implemented (eg. calculating N bits of Chaitin’s constant requires solving the halting problem for all N-bit machines, so the algorithm is “circular”).

9nGQluzmnq3M 7y ago
Yes, but my layman's understanding is that the oracle is a theoretical construct that knows in advance what programs halt and what don't -- but as you note, the real-world issue is that such oracles don't exist. My question remains, how does this tie back to the proof? Is there a path to building such an oracle now?
- dwohnitmok 7y ago
  No there is still no path to constructing such an oracle. The paper basically presents a result built off of a less trustworthy oracle (or set of oracles) that can potentially lie, but that still has unlimited computational power.

deleted 7y ago

[deleted]

jimhefferon 7y ago

Godel's Lost Letter suggests that these are not finite machines

lidHanteyk 7y ago

What this means is that, if you are confronted by a group of people, traditionally called provers, and you limit their collaboration in a certain way (here, by entangling some qubits and only using the entangled state for "communication"), then they can nonetheless prove to you in an interactive discussion that they know how to solve some Halting-equivalent problem. This does not give provers any new tricks for solving hard problems. This puts a ceiling on the power of this sort of prover-and-verifier proof and what it can show. There are problems harder than Halting (that is, that are hard even with oracles for Halting [0]) and MIP* doesn't contain them. [0] https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Turing_jump

hansdieter1337 7y ago

making the halting problem solvable if you have quantum entangled oracles that know everything. Welcome to complexity theory :) Reminds me of the proof that time traveling turing machines can solve the halting problem.

sterlind 7y ago
are those the Turing machines which can send an unlimited number of qubits back through a closed timelike curve? that result was mind-blowing. It only required classical computers, however, at least in the formulation I saw. Reversible computing in general seems weird when it comes to time.

dwohnitmok 7y ago

I have absolutely no knowledge of quantum mechanics beyond a pop-sci understanding, and I've only briefly skimmed the abstract and intro of the paper, but my impression is that it doesn't override this. Rather the direction of significance runs the other way; we now have strict limits on what kind of things in "quantum magic" are computable. Also note that this result still ultimately involves oracles with unlimited computational power (it does not construct these oracles). The interesting part is that these oracles are potentially malicious and can lie and it is the verifier's job to come up with a strategy to play an interactive game with these oracles to tease out the real answer (with a high probability of correctness).

pron 7y ago

I don't think the claim is that such a device with a finite amount of information could decide halting. As far as I understand, it could replace the infinite time required to classically decide halting with infinite information entanglement, neither can be put into real physical use.

naasking 7y ago

> but what I find most surprising is the claim that this would make the halting problem solvable. I don't think this is correct. I believe that it only makes the Halting Problem verifiable to a simple verifier dealing with two entangled verifiers. So a verifier typically has to rely on an oracle to solve the Halting Problem, but this new proof eliminates the need for that trust by a verification procedure using two entangled oracles.