**Problem:** Given the encoding of
a Turing machine *T* and an input *t* for that Turing machine, determine
whether or not *T* over input *t*, eventually halts.

**We will show that the Halting Problem is unsolvable.**
That is, we will show that there is no Turing machine that solves the Halting
Problem.

The proof will be by **contradiction**,
that is, we will show that the existence of a Turing machine that solves the
Halting Problem leads to a logical fallacy.

CS1104 Main Page

Last Updated 01/05/2000

© L.Heath, 2000