Why can't we solve the Halting Problem by using Artificial Intelligence?

Problem Detail: 

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.

Asked By : NMO

Answered By : Wandering Logic

The halting problem is not a statement about intelligence (human or artificial) it is a statement about the limits of mathematics. It is an historically important example of an undecidable problem.

An artificial (or human) intelligence can certainly look for and find many sorts of different infinite loops in real programs. And the halting problem doesn't say that such a thing is impossible or even very hard.

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 important?

The halting problem is similar to the Liar's Paradox in that it demonstrates the limits of mathematical and logical definitions of "truth", and "provability". The Liar's Paradox is: suppose I say "this statement is a lie." Is that statement true or false? If it is true then it must be a lie, so must be false. If it is false, then it is not a lie, so must be true. Writing a complicated artificial intelligence (or relying on a really smart person) won't make the question about whether I lied or not any more meaningful.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40283