The halting problem is the prototypical example of an undecidable problem, or a well posed problem that requires a yes or no answer that is impossible to solve. It should be stressed that the class of undecidable problems are impossible to solve not merely because of practical reasons such as time or memory requirements. The class of NP, or non polynomial time problems is an example a class of problems, which cannot be solved easily only because the algorithm required to find a solution is too computationally intensive. Rather, undecidable problems are more serious; they cannot be solved even in principle, regardless of the amount of computational power available.

As a prototypical example of an undecidable problem, the halting problem sheds light on the fundamental phenomenon of undecidability. The halting problem asks the following question. Given an arbitrary turing machine M, and an arbitrary input I...