Hacker News Reader

Comment by 9nGQluzmnq3M | Hacker News Reader

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

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?

View on HN

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

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”).

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?

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.

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.

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.

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).

> 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.

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.

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

Reply on news.ycombinator.com