So what are Turing Machines (TM) good for?              (Carol Zander, CSS 343)
------------------------------------------

They are mainly used to prove theoretical results since they are relatively
simple (in operation) and equivalent to the modern day computer for problem
solving. 

Turing machines are used to prove some problems cannot be solved using a computer.
One of the most famous of these kinds of problems is the Halting Problem.

Halting Problem -- Given some arbitrary Turing machine, called T,
     and some arbitrary input, called w, is there an algorithm
     to decide whether T halts when given input w?

At first reading, this may seem like gibberish, but think of T as your program,
w as the data to your program (w is for word), and an algorithm as just another
program (another Turing machine).  This should be familiar to you; a compiler
(a program) takes your program as input and performs a task.  So, the Halting
problem says, given a program with data, can you write another program to
detect if your program normally terminates?  Or, another way of thinking of it,
could you detect an infinite loop by just examining the program and data?

Certainly sometimes, in some situations you could.  Be nice if you always could
run your program and data through T and it pops out and says, buzzzz, infinite
loop.  Unfortunately, there is no such T.  Thus, we get a well known result:

Theorem:  The Halting Problem is not solvable.

Meaning, for example, there does not exist a TM (a program) to detect a problem
like an infinite loop.  

The proof of this is quite nifty.  It assumes there is a TM which can solve the
Halting problem, call it the "Halting Problem Answerer" (HPA).  Since you can
feed the HPA any program and any data, you feed it itself both as T and w,
program and data.  After a bit of algebraic manipulation, we encounter strange
things happening, and get a contradiction.  

As a proof technique, this is called proof by contradiction. Using the
technique, first you assume the opposite of what you're trying to prove.
Then you manipulate whatever it is by only doing legal operations.  When you
get to a contradiction, you conclude you must have made a false assumption,
so therefore the theorem you want to prove is true.

With the Halting Problem, the contradiction ends up saying our proposed
solution, the HPA, halts if it loops, but also loops if it halts.  Thus we
conclude no such TM can exist.