6
$\begingroup$

Just curious about this article I read today in the Google News. I am not a mathematician but enjoy the history of mathematics and the article seems to suggest the Halting problem has been disproven. I always thought once a theorem is proven it would never be disproven but again I am not an expert.

The article is the following: https://gizmodo.com/remarkable-mathematical-proof-describes-how-to-solve-se-1841003769

I do not know what the rules are for allowing me to enter a link so maybe I will write the part of the article in quotes to illustrate the point as follows:

Computer scientists are buzzing about a new mathematical proof that proposes a quantum-entangled system sort of like the one described above. It seems to disprove a 44-year-old conjecture and details a theoretical machine capable of solving the famous halting problem, which says a computer cannot determine whether it will ever be able to solve a problem it’s currently trying to solve.

The 150-page proof, titled simply “MIP*=RE,” deals in the esoteric subject of computational complexity. If it holds under scrutiny, it demonstrates a profound connection between quantum physics, computation, and mathematics. It shows that a theoretical class of computing devices—a verifier interrogating the quantum-entangled oracles—can check some of the most complex computer problems imaginable.

The last paragraph is beyond my understanding with the level of math that I have but what disturbes me is that I always believed once a proof was shown to be true it could not be disproven. The halting problem is related to Godel's incompeteness theorem and I know Godel's Theorem has also been proven to be true.

I thought perhaps someone who is expert could comment on this. Thank you.

$\endgroup$
1
  • 7
    $\begingroup$ There is a theorem that the halting problem cannot be solved by a Turing machine. That theorem has been proved, and of course, remains true. The machine described in this paper is more powerful than a Turing machine, and can, apparently, solve the halting problem. There is no contradiction here. $\endgroup$
    – saulspatz
    Jan 17, 2020 at 22:13

3 Answers 3

Reset to default
8
$\begingroup$

A theorem, once (correctly) proven, cannot be disproven. That said, there are two qualifiers here.

  • The theorem's proof must be genuinely correct. But proofs can be quite complicated, and mistakes in them can be very subtle. See this MathOverflow question for a number of examples of theorems which were widely believed to be proven but later shown to be false. This is not likely to be the case with the unsolvability of the Halting Problem, the proof of which is quite simple.
  • The theorem must be correctly stated. In particular, theorems are often summarized inexactly for general use; in this case, the inexact but popular summary of the Halting Problem is "no computer program can detect whether or not a given computer program will halt on a given input". But this is an incorrect statement of the theorem, which relies on the Church-Turing thesis - which states, essentially, that anything a person would call a "computer" is fundamentally equivalent to a Turing machine. The article you read suggests that quantum computers do not abide by the Church-Turing thesis, and are not equivalent to Turing machines - the unsolvability of the Halting Problem isn't incorrect, it just doesn't apply to those computers.

As a side note: The standard proof that the Halting Problem is unsolvable is very flexible, and could likely be modified to apply to anything that functions remotely like a Turing machine. The reasonable conclusion here is that a quantum computer is simply not remotely like a Turing machine.

$\endgroup$
3
  • 3
    $\begingroup$ It might be worth making contact with the well-known result that "quantum computers do abide by the Church-Turing thesis". $\endgroup$
    – spaceisdarkgreen
    Jan 18, 2020 at 5:54
  • $\begingroup$ @Reese I accept your answer but would like to ask you. For quantum computers is it the case that there has to exist some statement that we know is true but the computer does not? Assuming the quantum computer is consistent. Which is another question unto itself. Are quantum computers consistent? Thank you. $\endgroup$
    – Sedumjoy
    Jan 18, 2020 at 15:41
  • 1
    $\begingroup$ @Sedumjoy Well, as spaceisdarkgreen points out, a Turing machine can simulate a quantum computer; the article you linked to claims only that a quantum computer could solve the halting problem when augmented with an "all-knowing oracle", which is certainly more power that a Turing machine can have. As for consistency: "consistent" is a thing that sets of sentences can be. I don't know what it means for a computer to be "consistent". Certainly a quantum computer will not give contradictory answers to the same question, and (if correctly implemented) will not answer questions incorrectly. $\endgroup$
    – Reese Johnston
    Jan 18, 2020 at 16:00
1
$\begingroup$

Conjectures are propositions that are not proven but thought to be true.

$\endgroup$
3
  • 3
    $\begingroup$ The Gizmodo article does imply that the halting problem can be solved (in addition to refuting Connes embedding conjecture). However, it looks that they employ some sort of quantum computer, which is therefore presumably not equivalent to a Turing machine. $\endgroup$
    – Stinking Bishop
    Jan 17, 2020 at 22:06
  • 2
    $\begingroup$ In fact, as they note in the penultimate paragraph, the solver they contemplate for this class of problems cannot exist in our universe. $\endgroup$
    – user694818
    Jan 17, 2020 at 22:09
  • $\begingroup$ @Matthew Daly which paragraph? 2nd from the end of my question written paragraph of 2nd from the end of the article. And in what way does it show what you are saying? Please explain because I am interested in your comment. $\endgroup$
    – Sedumjoy
    Jan 18, 2020 at 0:36
1
$\begingroup$

The halting problem is still uncomputable, even with quantum computers, which can still be modeled by Turing Machines.

The article mentions an oracle, which is a theoretical-but impossible to create- program that can solve the halting problem.

Reasoning with these oracles is useful when studying the theory of computation.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .