Open In Colab

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 p such that for all words x and y,

[[p]](x,y)={1if [[x]](y)#if [[x]](y)

Proof. Suppose toward a contradiction that we had such a program p. Modifying p, we get a program q so that for all a,

[[q]](a)={if [[a]](a)#if [[a]](a)

In words, running q on a diverges iff running a on itself converges, and vice-versa. And this holds for all a. So in particular it holds for q. And this leads to a contradiction, as we shall see formally just below.

Here’s how this one would actually get q from p. Assume that p preserves its input. Let p have k instructions. Let

q=copy1,2,3+p+13#5+12#3+1k+2#4

Then q has the property that we want. But now, take a to be q. Then

[[q]](q)iff[[q]](q).

Contradiction!

Tip

Look up this setting of the proof by Geoffrey Pullum in the spirit of Dr. Seuss.

Corollary 3

The set K computably enumerable.

Proof. Suppose towards a contradiction that r is a program whose domain is K. Then just as with q in the proof above, we again have a contradiction: [[r]](r) iff [[r]](r).

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 p as above. Then we easily modify it to get a program q so that

[[q]](x,y)={[[x]](y)+1if [[x]](y)1if [[x]](y)

By Theorem 9, there is some x so that for all y,

[[x]](y)={[[x]](y)+1if [[x]](y)1if [[x]](y)

Now we cannot have [[x]](y), since if we did, we would also have [[x]](y) by the second line above. So, [[x]](y). But then by the first line, [[x]](y)[[x]](y)+1, and this is impossible.

Corollaries#

There are a number of corollaries to the basic undecidability result. Let us begin by recalling the sets of that we mentioned earlier:

Prog=the set of programsTidy=the set of tidy programsK0=the programs which halt when run on all empty registersK=the programs which halt when run on themselvesFin=the programs p such that the domain of [[p]] is finiteInf=the programs p such that the domain of [[p]] is infiniteTot=the program p such that [[p]] is a total functionEquiv=the set of pairs (p,q) of programs which are strongly equivalent

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 snm-Theorem.

Corollary 4

K, the set of programs which halt when run on themselves, is undecidable.

Corollary 5

K0, the set of programs which halt when run on all empty registers, is undecidable.

Exercise 65

For all the sets A in our reference list, Find a subset of A which is infinite and computable.

Then do the same for the complement set A.

Improvement for one-register programs#

There is also an improved version of the basic result.

Let A be the set of programs which are tidy and which only use one register.

Corollary 6

The halting problem is undecidable even for programs in A when run on all emtpy registers.

Exercise 66

The language 1# has infinitely many instructions: the instructions are the words 1k#, where kN and 15.

For each finite set F of 1# instructions, we can consider HF, the set of programs p built using the instructions of F (and no others) such that φp( ).

For example, if F={1#,1##}, then HF is decidable. This is because every program built from these two instructions halts.

Find a finite set F such that HF is undecidable.

Rice’s Theorem#

Theorem 12

Let S be any set of programs, and assume that S is closed under equivalence of words as one-place functions: if xS, and if [[x]] and [[y]] are the same partial function, then yS.

If S is decidable, then S is either the empty set or the set of all programs.

Proof. If not, we can fix programs pS and qS, and we also can fix a program s which computes the characteristic function of S.

Now let

f(x)={[[q]](x)if [[s]](x)1[[p]](x)if [[s]](x)#

Let x be such that [[x]]=[[f(x)]]. If xS, then [[s]](x)1. But by definition of f, [[f(x)]](x)=[[q]](x) for all x. This tells us that [[f(x)]] and [[q]] are the same partial function. So since qS, we have f(x)S. This contradicts S being closed under equivalence. So we have a contradiction in case xS. But we have a similar contradiction in case xS.

Corollary 7

The following sets are undecidable: Fin, Inf, and Tot.

Exercise 67

Show that InfmTot and TotmInf.

Exercise 68

Show that the following set S of programs is undecidable: S is the set of programs p which, when run on all empty registers at some point write 1 into R2.

Exercise 69

What about the set of programs which at some point execute their second instruction? Is that set decidable?