Undecidability and the Halting Problem
--------------------------------------

   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, does
the turing machine halt when it is run on the input I, or does it run
forever.  The British mathematician Alan Turing gave a fundamental
proof showing that the Halting problem is unsolvable.  He argued by
contradiction.  Suppose that there were an algorithm to solve the
halting problem and that this algorithm were implemented by a Turing
machine H.  Then consider an arbitrary pairing between the infinitely
many inputs a Turing machine can have and the infinitely many Turing
machines one might build.  Thus each and every possible Turing machine
M is paired with an arbitrary input I.  Using this pairing one might
build a new Turing machine N that acts as follows.  N uses H to 
determine whether or not M will halt on input I.  Then N does the
exact opposite of M when given the same input I.  If M halts, then N
goes into an infinite loop.  If M runs forever, N halts.  So N behaves
differently from every single Turing machine on at least one input.
But this is impossible since N itself is a Turing machine and cannot
differ from itself.  Thus the existence of the halting algorithm H,
which is crucial to the construction of N, is impossible. 

   One may notice in the above proof that the only thing proved is
that no Turing machine can solve the halting problem.  There exists a
loophole to the proof; namely something other than a Turing machine
could solve the halting problem.  This loophole is closed by the
Church-Turing thesis, which states that any conceivable computer that
could ever be built, no matter how powerful it may seem, is equivalent
to a Turing machine.  In other words, Turing machines are universal
computers.  Turing's proof, combined with the strength of the
Church-Turing thesis, shows that no computer, or equivalently no
algorithmic process, can ever solve the halting problem. 

   Turing's proof that the halting problem is undecidable has vast
ramifications in mathematics.  For one thing, his proof can be used to
show that other problems are unsolvable in principle.  One does so by
reducing the candidate problem to the halting problem.  For example to
show problem X is unsolvable, one shows that if X could be solved, the
solution could be used to solve the halting problem.  But since the
halting problem is unsolvable, X cannot be unsolvable either.  This
proof technique can also be used to prove one of the celebrated
theorems of modern mathematics, namely Godel's incompleteness theorem,
which states, startlingly enough, that in a finite axiomatic system
there exist many true statements that are impossible to prove using
the finite number of axioms defining the system.