This question already has an answer here:

Have there been proposed extensions to go beyond a Turing machine that solve the halting problem and if so, would those proposed extensions have value to advance strong Artificial Intelligence? For example, does quantum computing go beyond the definition of a Turing machine and resolve the halting problem, and does that help in creating strong AI?


marked as duplicate by Mark, kenorb, wythagoras, Henry WH Hack v2.1.3, Dom Aug 15 '16 at 3:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You are asking two things here :-D (1) relation between QuantC and halting problem, (2) relation between "solving" the halting problem and making a AGI. I think (1) is out of scope here (and the answer is no). Perhaps need to move this split to another SE site. (2) should lead to interesting answers, unfortunately revolving around "maybe" (speed matters, as several AI researchers have shown). $\endgroup$ – Eric Platon Aug 3 '16 at 6:37
  • 3
    $\begingroup$ Isn't (2) already answered by ai.stackexchange.com/questions/148/… ? $\endgroup$ – wythagoras Aug 3 '16 at 6:47
  • $\begingroup$ Yes, that's a reason why I was proposing to split the question: It is convoluted... In short, I would just like to see better quality phrasing for such kind of (to me interesting) questions. $\endgroup$ – Eric Platon Aug 3 '16 at 10:12
  • $\begingroup$ @EricPlaton Please feel free to suggest edits. I'll also think about how to improve it. $\endgroup$ – WilliamKF Aug 3 '16 at 17:32
  • $\begingroup$ Sorry for the lack of straightforwardness. (1) seems out of scope, and (2) is actually now in the linked question. Do we need this question, then? My conclusion is that we don't. So the "rewriting" would be to close this question. $\endgroup$ – Eric Platon Aug 4 '16 at 7:52

It depends a bit on what you mean by 'quantum computer'. The 'conventional' notion is that quantum computation buys a (in some cases, exponential) speedup - it doesn't change what can be computed, just how quickly.

In contrast, advocates of hypercomputation claim that quantum effects may make it possible to do infinite computations in finite time. Note, however, that this is not a mainstream belief - the reknowned logician Martin Davis has written an article claiming that hypercomputation is a myth.

Roger Penrose has also claimed that quantum vibrations in neural microtubules may be responsible for consciousness.


No, quantum computers (as understood by mainstream scientists) cannot solve the halting problem. We can already simulate quantum circuits with normal computers; it just takes a really long time when you get a decent number of qubits involved. (Quantum computing provides exponential speedups for some problems.) Therefore, if quantum computers could solve the halting problem, we could solve the halting problem with classical computers by simulating a quantum one, but it's impossible to solve the halting problem with classical computers, so we can't do it with quantum ones either.

There are proponents of hypercomputation - infinite speedups using quantum computers - but the evidence put forward so far is mostly conjecture. Further reading: Can quantum computing solve classically unsolvable problems? (PDF), References on comparison between quantum computers and Turing machines (at CS.SE).

Solving the halting problem would make a computer exceptionally powerful. It would conceivably be able to check whether complex theorems are true without necessarily needing to product a mathematical proof. Solving that problem isn't necessary for strong AI, though. Going with the definition of "strong AI" as "where the machine's intellectual capability is functionally equal to a human's" (source), a computer could be able to learn like a human despite not being able to look at a program and see if it halts. I can't magically determine the halting properties of any arbitrary program, yet I'd like to think I'm an intelligent being.


Not the answer you're looking for? Browse other questions tagged or ask your own question.