8
$\begingroup$

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. Code Warning

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.

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ 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".) $\endgroup$
    – Raphael ♦
    Mar 10 '15 at 14:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – NMO
    Mar 10 '15 at 14:58
  • 3
    $\begingroup$ @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.) $\endgroup$
    – Wandering Logic
    Mar 10 '15 at 15:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Mar 10 '15 at 15:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – Wandering Logic
    Mar 10 '15 at 17:04
17
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer! I am finally starting to understand this problem. When you said we can always make a program that "I" is not able to analyse, why is this? I mean, aren't finite repetition structures we can find in a program? Because the problem seems to arise here. $\endgroup$
    – NMO
    Mar 10 '15 at 15:21
  • 3
    $\begingroup$ 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. $\endgroup$
    – Wandering Logic
    Mar 10 '15 at 15:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.