19
$\begingroup$

Given the proven halting problem for Turing machines, can we infer limits on the ability of strong Artificial Intelligence?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
11
$\begingroup$

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. (Certainly there are pieces of code that a human can look at and say "yes" or "no" definitely, but we're talking about the ones that are actually quite difficult to analyze.)

The halting problem means that there are types of code analysis that no computer could do, because it's mathematically impossible. But the realm of possibility is still large enough to allow strong artificial intelligence (in the sense of code that can understand itself well enough to improve itself).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Halting problem means that no single ( finite) method can decide if any program will stop at finite time. It doesn't mean there are problems which cannot be solved ( which of course exists but the causes are usually different) $\endgroup$
    – kakaz
    Commented Dec 10, 2017 at 19:12
13
$\begingroup$

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 that it is undecidable whether a Turing Machine satisfies some non-trivial property P, called Rice's theorem.

First note that the halting problem applies only if the Turing machine takes arbitrarily long input. If the input is bounded, it is possible to enumerate all possible cases and the problem is no longer undecidable. It might still be inefficient to calculate it, but then we are turning to the complexity theory, which should be a separate question.

Rice's theorem implies that an intelligence (a human) cannot be able to determine whether another intelligence (such as an AGI) possesses a certain property, such as being friendly. This does not mean that we cannot design a Friendly AGI, but it does mean that we cannot check whether an arbitrary AGI is friendly. So, while we can possibly create an AI which is guaranteed to be friendly, we also need to ensure that IT cannot create another AI which is unfriendly.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .