Answers.Body: <p>The halting problem is an example of a general phenomenon known as <a href="https://en.wikipedia.org/wiki/Undecidable_problem" rel="noreferrer">Undecidability</a>, 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 <a href="https://en.wikipedia.org/wiki/Rice%27s_theorem" rel="noreferrer">Rice's theorem</a>.</p>
  
  <p>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.</p>
  
  <p>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 <a href="https://en.wikipedia.org/wiki/Friendly_artificial_intelligence" rel="noreferrer">friendly</a>. 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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-03T06:21:45.740Z
Answers.Text: I've broken out the quantum question aspect out to a new question at: http://ai.stackexchange.com/q/186/55
Answers.UserDisplayName: WilliamKF
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-03T04:22:28.030Z
Answers.LastActivityDate: 2016-08-03T18:25:39.313Z
Answers.LastEditDate: 2016-08-03T18:25:39.313Z
Answers.UserDisplayName: Harsh
Answers.Body: <p>Does the halting problem imply any limits on human cognition?</p>
  
  <p>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.)</p>
  
  <p>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 <em>possibility</em> is still large enough to allow strong artificial intelligence (in the sense of code that can understand itself well enough to improve itself).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-10T19:12:55.823Z
Answers.Text: 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)
Answers.UserDisplayName: kakaz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-03T02:17:01.983Z
Answers.LastActivityDate: 2016-08-03T02:17:01.983Z
Answers.UserDisplayName: Matthew Gray
Body: <p>Given the proven <a href="https://en.wikipedia.org/wiki/Halting_problem">halting problem</a> for <a href="https://en.wikipedia.org/wiki/Turing_machine">Turing machines</a>, can we infer limits on the ability of strong Artificial Intelligence?</p>
  
Tags: <agi><theory-of-computation><halting-problem><turing-machine>
Title: What limits, if any, does the halting problem put on Artificial Intelligence?
UserDisplayName: WilliamKF
ThreadText: # What limits, if any, does the halting problem put on Artificial Intelligence?
  
  (Asked by: username_0 on 2016-08-02)
  
  Given the proven [halting problem](https://en.wikipedia.org/wiki/Halting_problem) for [Turing machines](https://en.wikipedia.org/wiki/Turing_machine), can we infer limits on the ability of strong Artificial Intelligence?
  
  **Tags:** agi, theory-of-computation, halting-problem, turing-machine
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2016-08-03. Score: 11 | Accepted answer
  
  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).
  
  > **Comments:**
  > **username_3**: 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)  
  
  ---
  
  ### Answer by username_1 on 2016-08-03. Score: 13
  
  The halting problem is an example of a general phenomenon known as [Undecidability](https://en.wikipedia.org/wiki/Undecidable_problem), 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](https://en.wikipedia.org/wiki/Rice%27s_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](https://en.wikipedia.org/wiki/Friendly_artificial_intelligence). 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.
  
  > **Comments:**
  > **username_0**: I've broken out the quantum question aspect out to a new question at: http://ai.stackexchange.com/q/186/55  
  
  ---
  
  