Skip to main content
13 votes

What limits, if any, does the halting problem put on Artificial Intelligence?

The halting problem is an example of a general phenomenon known as Undecidability, which shows that there are problems no Turing machine can solve in finite time. Let's consider the generalization ...
Harsh's user avatar
  • 1,315
11 votes
Accepted

What limits, if any, does the halting problem put on Artificial Intelligence?

Does the halting problem imply any limits on human cognition? Yes, absolutely--that there are pieces of code a human could look at and not be sure whether or not it will halt in finite time. (...
Matthew Gray's user avatar
  • 4,272
4 votes

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

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 ...
Ben N's user avatar
  • 2,609
4 votes

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

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, ...
NietzscheanAI's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible