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?
$\begingroup$
$\endgroup$
5
-
$\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 PlatonCommented Aug 3, 2016 at 6:37
-
3$\begingroup$ Isn't (2) already answered by ai.stackexchange.com/questions/148/… ? $\endgroup$– wythagorasCommented Aug 3, 2016 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 PlatonCommented Aug 3, 2016 at 10:12
-
$\begingroup$ @EricPlaton Please feel free to suggest edits. I'll also think about how to improve it. $\endgroup$– WilliamKFCommented Aug 3, 2016 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 PlatonCommented Aug 4, 2016 at 7:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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. $\endgroup$– KelvinCommented Apr 19, 2022 at 6:34