Does the MIP*=RE presentation imply that the Turing Halting Problem is solvable?

197 Views Asked by At

I noticed an article where the author seemed to imply the halting problem was solved so I found the paper he was referencing but it is over my level of knowledge.

Was hoping someone in the community would be so kind to make a brief comment. The first link below is the article in quanta magazine and the second link is the article that is under discussion.

https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/

https://arxiv.org/abs/2001.04383

1

There are 1 best solutions below

1
On BEST ANSWER

No, it doesn't.

What it does do is reduce the halting problem to a different type of problem, which on the face of it doesn't seem particularly related. But this doesn't mean that the halting problem is solvable, only that it's solvable relative to a different problem (which consequently is itself unsolvable).

There is in fact a rich structure of "degrees of unsolvability," more commonly called the Turing degrees. It's worth noting that in contrast with complexity theory where many-one reductions are standard, the default notion of reducibility in the context of computability theory is Turing reducibility. To see the difference, note e.g. that we trivially have a polynomial-time Turing equivalence between $\mathsf{NP}$ and $\mathsf{coNP}$ while it's open whether they are polynomial-time many-one equivalent.