# 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.

• 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".) Commented Mar 10, 2015 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. Commented Mar 10, 2015 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.) Commented Mar 10, 2015 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. Commented Mar 10, 2015 at 15:59
• @NMO: No, the halting program shows that there are programs that a really smart person with a really big memory and sufficient (but finite) time can't determine if it is going to halt or loop infinitely. There is no mathematical way to do it correctly in all cases, it has nothing to do with how smart you are. The way to see it is by working through the proof by yourself. Commented Mar 10, 2015 at 17:04

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. Commented Mar 10, 2015 at 15:47