The halting problem#
We come to one of the most famous and most basic results in computability theory, the undecidability of the halting problem, first proved by Turing in 1936.
Theorem 11
There is no program
Proof. Suppose toward a contradiction that we had such a program
In words, running
Here’s how this one would actually get
Then
Contradiction!
Tip
Look up this setting of the proof by Geoffrey Pullum in the spirit of Dr. Seuss.
Corollary 3
The set
Proof. Suppose towards a contradiction that
Tip
If you have read the section on the Recursion Theorem, you might enjoy a slightly different proof of Theorem 11.

Assume towards a contradiction that there is a program
By Theorem 9, there is some
Now we cannot have
Corollaries#
There are a number of corollaries to the basic undecidability result. Let us begin by recalling the sets of that we mentioned earlier:
Of these the first two are computable, easily. But all of the others are not. These are all corollaries of Theorem 11, sometimes with additional points provided by the
Corollary 4
Corollary 5
Exercise 65
For all the sets
Then do the same for the complement set
Improvement for one-register programs#
There is also an improved version of the basic result.
Let
Corollary 6
The halting problem is undecidable even for programs in
Exercise 66
The language
For each finite set
For example, if
Find a finite set
Rice’s Theorem#
Theorem 12
Let
If
Proof. If not, we can fix programs
Now let
Let
Corollary 7
The following sets are undecidable:
Exercise 67
Show that
Exercise 68
Show that the following set 1
into R2.
Exercise 69
What about the set of programs which at some point execute their second instruction? Is that set decidable?