With a caveat added: "... in general". As mentioned by sokoloff, the halting problem is solved routinely by people in software engineering research groups. This does not invalidate the Halting Theorem simply because the Halting Theorem talks about the impossibility of a single Turing Machine FOR ALL programs.
If there is a proven theorem that something is impossible, either the theorem is wrong or it's impossible.
> the halting problem is solved routinely by people in software engineering research groups
I'm not sure how I'm meant to read this.
If it is that people do the solving of the halting problem (that is, people read the source of the program and say "this will halt" or "this will not halt"), then they have not solved the halting problem: the halting problem states there is no way to do this by algorithm.
If it is that people write software which solves the halting problem, then you are wrong, and you explain to yourself why you are wrong. They are solving a different problem, namely, whether some very small class of computable functions halts.
Your two sentences "the halting problem is solved routinely" (assuming you mean the latter case, as above) and "this does not invalidate the Halting Theorem" do not logically work.
> If there is a proven theorem that something is impossible, either the theorem is wrong or it's impossible.
It can get a lot more subtle than that. I do not want to elaborate, but there are classes of problems for which we can only guarantee SOME hard problems (or undecidable ones) but MOST of which are easy. There are other classes of problems where MOST problems are hard.
> Your two sentences "the halting problem is solved routinely" (assuming you mean the latter case, as above) and "this does not invalidate the Halting Theorem" do not logically work.
I agree it sounds illogical, but my phrasing was poor. I meant, if problem instances that arise in real life are easy to solve, yet there is a theorem that states that NOT ALL problems are easy, these two are not mutually exclusive. I agree "routinely solving the halting problem" is an exaggeration on my part.
Technically, the theorem doesn't apply. Actually built computers aren't Turing machines: their memory is finite.
The algorithm to answer if a program running on a deterministic finite-memory machine is trivial: Run until it either halts or repeats a state. Halting means it halts (duh); repeating a state means it doesn't halt. This algorithm is, of course, not implementable.
On these lines, there's lots of sharp restrictions and heuristics you can use to get problems out of NP into something manageable. And a lot of the time a decent approximation is good enough.
