<AI>Devspace

Does a quantum computer resolve the halting problem and would that advance strong AI?

clock icon
asked 3 weeks ago
message icon
2
eye icon
4.6K

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?

2 Answers

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.

1

Write your answer here