The Halting Problem

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