# Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a warning saying that my code was going to result in an infinite loop.

My question is, why can't this problem, be solved by using an "Intelligent" program to determine if another program will halt or end in an infinite loop? This hypothetical program could look for repetitive structures, conditions, etc and even predict under which circumstances (possible inputs) will halt, loop infinitely or end. Maybe like looking for the "acceptable range", like the domain of a mathematical function.

• Why is this not answered by the fact that the halting problem is incomputable, which you seem to be aware of (see also our reference question)? Note that "intelligent" has no real meaning; we build algorithms, period. If they are randomized, they do not contradict the halting problem (because its model does not allow for randomness) but also can't solve it, always. – Raphael Mar 10 '15 at 14:52
• See also here, here, here and, most importantly, here. Oh, and here -- yes, the Halting problem is decidable on some classes of programs, which is why IDEs can detect some forms of looping. (Note how they never tell you "terminates always".) – Raphael Mar 10 '15 at 14:57
• I know this problem is not computable. I am looking for someone to prove why my idea is wrong. I am a beginner trying to understand. Sorry if my question is insulting to you. – NMO Mar 10 '15 at 14:58
• @Raphael: In OP's defense, he's not really asking for a computability proof, he's asking about the common logical error (made, for example, by the famous mathematical physicist Roger Penrose) that "intelligence" is a magic property stronger than an algorithm. (Penrose goes so far as to propose that consciousness must be a result of quantum gravitational effects in cellular microtubules. I kid you not.) – Wandering Logic Mar 10 '15 at 15:38
• @NMO Your question certainly isn't insulting: don't worry. The point is that any program that uses artificial intelligence is still a program, so it still can't solve the halting problem. It's certainly possible to write a program that says either "This halts", "This doesn't halt" or "I don't know", but any such program will always say "I don't know" for infinitely many inputs. – David Richerby Mar 10 '15 at 15:59

What the halting problem says is that given any program $I$ ("I" for "intelligent"), (say a really complicated AI program written in Netbeans) that looks for infinite loops we can produce a program that $I$ can't analyze. The way we do this is a clever technique called diagonalization, which is described in the question @Raphael linked: How to show that a function is not computable?, and also in Why, really, is the Halting Problem so important?
• The answers @Raphael linked will show you how to construct a program that will take $I$ and (essentially) run it on itself in such a way that it itself must enter an infinite loop. The proof sketch of the halting problem on Wikipedia is also very clearly written. – Wandering Logic Mar 10 '15 at 15:47