EDIT (much later than original answer): MarkCC of Good Math, Bad Math recently wrote up an excellent discussion of the Halting problem with concrete examples.
The halting problem is basically a
formal way of asking if you can tell
whether or not an arbitrary program
will eventually halt.In other words, can you write a
program called a halting oracle,
HaltingOracle(program, input), which
returns true if program(input) would
eventually halt, and which returns
false if it wouldn’t?The answer is: no, you can’t.
Following up on questions about whether the input to the Halting problem is relevant or a red herring: Yes, the input is important. Also, there seems to be some confusion in that I see “infinite” being used where “arbitrary” is more correct.
Practical example: Imagine that you are working in a QA position and you are to write a halting checker program (aka an oracle) that will confirm that for any arbitrary program written by the development team (D) and any arbitrary input provided by the end-user (I), program D will eventually halt when given input I.
Cue manager voice: “Ho ho, those goofy users, let’s make sure that no matter what garbage they type, our server tasks will never end up in an endless loop. Make it so, code monkey!”
This seems like a great idea, right? You don’t want your server to hang, right?
What the halting problem is telling you is that you are being handed an unsolvable task. Instead, in this particular case, you need to plan for tasks that run past a threshold time and be ready to cancel them.
Mark uses code instead of input to illustrate the problem:
def Deciever(i):
oracle = i[0]
in = i[1]
if oracle(Deceiver, i):
while True:
continue
else:
return i
In my discussion in the comments, I went the route of malicious input manipulation to force an unsolvable problem. Mark’s example is far more elegant, using the halting oracle to defeat itself:
So, the input to Deceiver is actually
a list of two elements: the first one
is a proposed halting oracle. The
second is another input. What the
halting killer does is ask the Oracle:
“Do you think I’ll halt for input i?”.
If the oracle says, “Yes, you’ll
halt”, then the program goes into an
infinite loop. If the oracle says “No,
you won’t halt”, then it halts. So no
matter what the oracle says, it’s
wrong.
Said another way, without cheating, reformatting inputs, countable / uncountable infinities or anything other distractions, Mark has written a piece of code that can defeat any halting oracle program. You cannot write an oracle that answers the question of whether Deceiver ever halts.
Original answer:
From the great Wikipedia:
In computability theory, the halting
problem is a decision problem which
can be stated as follows: given a
description of a program and a finite
input, decide whether the program
finishes running or will run forever,
given that input.Alan Turing proved in 1936 that a
general algorithm to solve the halting
problem for all possible program-input
pairs cannot exist. We say that the
halting problem is undecidable over
Turing machines. Copeland (2004)
attributes the actual term halting
problem to Martin Davis.
One of the critical points is that you have no control over either the program or the input. You are handed those and it’s up to you to answer the question.
Note also that Turing machines are the basis for effective models of computability. Said another way, everything that you do in modern computer languages can be mapped back to these archetypical Turing machines. As a result, the halting problem is undecidable in any useful modern language.