Slashdot videos: Now with more Slashdot!
A consequence (or more generalized version if you will) of the fact that the halting problem is algorithmically undecidable is that the static analysis problem is also algorithmically undecidable. Static analysis here is the task of deciding whether a program P satisifies a specification S. You can not write an algorithm such that for any combination (S,P) the algorithm will tell you whether the program satisfies the spec or not. That again does not mean that it is impossible to prove that an individual program P1 satisfies an individual specification S1, which appears to be the case here.
To quote wikipedia on the halting problem:
While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack. Given a specific algorithm, one can often show that it must halt for any input, and in fact computer scientists often do just that as part of a correctness proof. But each proof has to be developed specifically for the algorithm at hand; there is no mechanical, general way to determine whether algorithms on a Turing machine halt. However, there are some heuristics that can be used in an automated fashion to attempt to construct a proof, which succeed frequently on typical programs. This field of research is known as automated termination analysis.
It says a lot about the world that no other nation yet has the 1st and 2nd amendment.
Just out of curiosity, is this supposed to say something about the US or about the rest of the world? In the latter case, what exactly is the fact that the other democracies of the world did not choose to make the right to keep firearms in the house a constitutional right supposed to say about them?