Answers.Body: <p>No, quantum computers (as understood by mainstream scientists) cannot solve the halting problem. We can already <a href="http://algorithmicassertions.com/2016/05/22/quirk.html" rel="nofollow noreferrer">simulate quantum circuits with normal computers</a>; 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.</p>
  
  <p>There are proponents of hypercomputation - infinite speedups using quantum computers - but the evidence put forward so far is mostly conjecture. Further reading: <a href="https://arxiv.org/ftp/quant-ph/papers/0512/0512248.pdf" rel="nofollow noreferrer">Can quantum computing solve classically
  unsolvable problems?</a> (PDF), <a href="https://cs.stackexchange.com/q/6296">References on comparison between quantum computers and Turing machines</a> (at CS.SE).</p>
  
  <p>Solving the halting problem would make a computer exceptionally powerful. It would conceivably be able to <a href="https://blogs.msdn.microsoft.com/ericlippert/2011/02/24/never-say-never-part-two/" rel="nofollow noreferrer">check whether complex theorems are true</a> 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" (<a href="https://www.ocf.berkeley.edu/~arihuang/academic/research/strongai3.html" rel="nofollow noreferrer">source</a>), 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-19T06:34:16.050Z
Answers.Text: This proof doesn't work because you can't simulate arbitrary qubits with classical bits. Qubits on a quantum computer are points on a Bloch sphere which at the very least can be three arbitrary irrational numbers (possibly, even incomputable numbers). Thus this simulation only works in a very limited sense.
Answers.UserDisplayName: Kelvin
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-07T23:34:29.837Z
Answers.LastActivityDate: 2016-08-07T23:34:29.837Z
Answers.LastEditDate: 2017-04-13T12:48:38.883Z
Answers.UserDisplayName: Ben N
Answers.Body: <p>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 <em>what</em> can be computed, just how quickly.</p>
  
  <p>In contrast, advocates of <em>hypercomputation</em> 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 href="http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf" rel="nofollow">a myth</a>.</p>
  
  <p>Roger Penrose has also claimed that quantum vibrations in neural microtubules may be <a href="https://en.wikipedia.org/wiki/Quantum_mind" rel="nofollow">responsible for consciousness</a>.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-03T07:36:08.923Z
Answers.LastActivityDate: 2016-08-03T07:36:08.923Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-08-03T06:37:52.803Z
Comments.Text: 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](https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory)). 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).
Comments.UserDisplayName: Eric Platon
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-08-03T06:47:44.710Z
Comments.Text: Isn't (2) already answered by http://ai.stackexchange.com/questions/148/what-limits-if-any-does-the-halting-problem-put-on-artificial-intelligence?noredirect=1&lq=1 ?
Comments.UserDisplayName: wythagoras
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-08-03T10:12:13.397Z
Comments.Text: 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.
Comments.UserDisplayName: Eric Platon
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-08-03T17:32:02.793Z
Comments.Text: @EricPlaton Please feel free to suggest edits.  I'll also think about how to improve it.
Comments.UserDisplayName: WilliamKF
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-08-04T07:52:20.767Z
Comments.Text: 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.
Comments.UserDisplayName: Eric Platon
Tags: <quantum-computing><halting-problem><agi>
Title: Does a quantum computer resolve the halting problem and would that advance strong AI?
UserDisplayName: WilliamKF
ThreadText: # Does a quantum computer resolve the halting problem and would that advance strong AI?
  
  (Asked by: username_0 on 2016-08-03)
  
  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?
  
  **Tags:** quantum-computing, halting-problem, agi
  
  > **Comments:**
  > **username_1**: 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](https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory)). 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).  
  > **username_2**: Isn't (2) already answered by http://ai.stackexchange.com/questions/148/what-limits-if-any-does-the-halting-problem-put-on-artificial-intelligence?noredirect=1&lq=1 ?  
  > **username_1**: 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.  
  > **username_0**: @username_1 Please feel free to suggest edits.  I'll also think about how to improve it.  
  > **username_1**: 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2016-08-07. Score: 4
  
  No, quantum computers (as understood by mainstream scientists) cannot solve the halting problem. We can already [simulate quantum circuits with normal computers](http://algorithmicassertions.com/2016/05/22/quirk.html); 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?](https://arxiv.org/ftp/quant-ph/papers/0512/0512248.pdf) (PDF), [References on comparison between quantum computers and Turing machines](https://cs.stackexchange.com/q/6296) (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](https://blogs.msdn.microsoft.com/ericlippert/2011/02/24/never-say-never-part-two/) 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](https://www.ocf.berkeley.edu/~arihuang/academic/research/strongai3.html)), 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.
  
  > **Comments:**
  > **username_4**: This proof doesn't work because you can't simulate arbitrary qubits with classical bits. Qubits on a quantum computer are points on a Bloch sphere which at the very least can be three arbitrary irrational numbers (possibly, even incomputable numbers). Thus this simulation only works in a very limited sense.  
  
  ---
  
  ### Answer by username_5 on 2016-08-03. Score: 4
  
  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](http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf).
  
  Roger Penrose has also claimed that quantum vibrations in neural microtubules may be [responsible for consciousness](https://en.wikipedia.org/wiki/Quantum_mind).
  
  
  ---
  
  