The halting problem is an profound bit of theoretical CS well-explained on this thread.
However, the actual halting problem is moot in most of the references I see to it, as the halting problem is usually misused by the half-educated to make claims that 'nothing useful can ever be inferred about the behavior of any program, ever'.
For example, we built a tool to either estimate a reasonable ceiling on the stack usage (whole-program) or give up; it works very well and can detect when the structure of the program prevents this tool from operating correctly (nasty stack mischief or stack adjustments appearing in 'unusual' places). Quite useful for us, especially because we control the source code and know that we don't do naughty things to our own stack.
Entertainingly, on the way to build this tool, we encountered at a couple screeds about how this problem just plain can't be solved because it's equivalent to 'solving the halting problem'. Well, yes - in theory, but no - in practice.
My undergraduate thesis tackled static analysis in Ruby. One of the problems I attacked was "does a given method yield to its block?" I broke methods into a few classes, two of which are "Block-Required" and "Block-Optional."
I had to write software which proved a method optionally yielded, which isn't just undecidable, but unrecognizable. For non-CS folks, that means it's actually harder than the halting problem. Yet my software works on nearly all Ruby code I throw at it - it only really has difficulty on complex delegation patterns. Unsurprisingly, the code people write to create Block-Optional methods is highly structured.
We control the source code in question, so we deal with it by detecting unexpected recursion and screaming bloody murder.
We have a 'little bit' of recursion where we know that we won't go around the recursion more than once and we've hand-hacked that it. We have similar hacks to deal with indirect calls.
I'm not saying we've solved the problem for arbitrary code; I'm saying that solutions that fall very far short of solving problems for arbitrary codes are still enormously useful. Many compiler optimizations don't work for 'arbitrary code' either, for example, and know just enough to bail out when they see an irreducible flowgraph or a bizarre indirect jump, etc.
However, the actual halting problem is moot in most of the references I see to it, as the halting problem is usually misused by the half-educated to make claims that 'nothing useful can ever be inferred about the behavior of any program, ever'.
For example, we built a tool to either estimate a reasonable ceiling on the stack usage (whole-program) or give up; it works very well and can detect when the structure of the program prevents this tool from operating correctly (nasty stack mischief or stack adjustments appearing in 'unusual' places). Quite useful for us, especially because we control the source code and know that we don't do naughty things to our own stack.
Entertainingly, on the way to build this tool, we encountered at a couple screeds about how this problem just plain can't be solved because it's equivalent to 'solving the halting problem'. Well, yes - in theory, but no - in practice.