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\),

\[\begin{split}\begin{array}{lcl} [\![p]\!](x,y) & = & \left\{ \begin{array}{ll} \one & \mbox{if $[\![x]\!](y)\dar$}\\ \hash & \mbox{if $[\![x]\!](y)\uparrow$} \end{array} \right. \end{array} \end{split}\]

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

\[\begin{split} \begin{array}{lcl} [\![q]\!](a) & = & \left\{ \begin{array}{ll} \uparrow & \mbox{if $[\![a]\!](a)\dar$}\\ \hash & \mbox{if $[\![a]\!](a)\uparrow$} \end{array} \right. \end{array} \end{split}\]

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 \quadeq \copyprog_{1,2,3} + p + \one^3\hash^5 + \one^2 \hash^3 + \one^{k + 2} \hash^4 \]

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

\[ [\![q]\!](q)\dar \quadiff [\![q]\!](q)\uparrow. \]

Contradiction!

Tip

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

Corollary 3

The set \(\overline{K}\) computably enumerable.

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

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

\[\begin{split} \begin{array}{lcl} [\![q]\!](x,y) & = & \left\{ \begin{array}{ll} [\![x]\!](y) + 1 & \mbox{if $[\![x]\!](y)\dar$}\\ {\tt 1} & \mbox{if $[\![x]\!](y)\uparrow$} \end{array} \right. \end{array} \end{split}\]

By Theorem 9, there is some \(x^*\) so that for all \(y\),

\[\begin{split} \begin{array}{lcl} [\![x^*]\!](y) & = & \left\{ \begin{array}{ll} [\![x^*]\!](y) + 1 & \mbox{if $[\![x^*]\!](y)\!\!\downarrow$}\\ {\tt 1} & \mbox{if $[\![x^*]\!](y)\!\!\uparrow$} \end{array} \right. \end{array} \end{split}\]

Now we cannot have \([\![x^*]\!](y)\!\!\uparrow\), since if we did, we would also have \([\![x^*]\!](y)\!\!\downarrow\) by the second line above. So, \([\![x^*]\!](y)\!\!\downarrow\). But then by the first line, \([\![x^*]\!](y)\simeq [\![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:

\[\begin{split} \begin{array}{lcl} \mbox{Prog} & = & \mbox{the set of programs} \\ \mbox{Tidy} & = & \mbox{the set of tidy programs} \\ K_0 & = & \mbox{the programs which halt when run on all empty registers}\\ K & = & \mbox{the programs which halt when run on themselves} \\ \textit{Fin} & = & \mbox{the programs $p$ such that the domain of $[\![p]\!]$ is finite} \\ \textit{Inf} & = & \mbox{the programs $p$ such that the domain of $[\![p]\!]$ is infinite} \\ \textit{Tot} & = & \mbox{the program $p$ such that $[\![p]\!]$ is a total function} \\ \textit{Equiv} & = & \mbox{the set of pairs $(p,q)$ of programs which are strongly equivalent}\\ \end{array} \end{split}\]

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 \(s^m_n\)-Theorem.

Corollary 4

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

Corollary 5

\(K_0\), 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 \(\overline{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 \(\one\hash\) has infinitely many instructions: the instructions are the words \(\one^k \hash^{\ell}\), where \(k\in \N\) and \(1\leq \ell\leq 5\).

For each finite set \(F\) of \(\one\hash\) instructions, we can consider \(H_F\), the set of programs \(p\) built using the instructions of \(F\) (and no others) such that \(\phifn_p(\ )\dar\).

For example, if \(F = \set{\one\hash, \one\hash\hash}\), then \(H_F\) is decidable. This is because every program built from these two instructions halts.

Find a finite set \(F\) such that \(H_F\) 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 \(x\in S\), and if \([\![x]\!]\) and \([\![y]\!]\) are the same partial function, then \(y\in S\).

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

Proof. If not, we can fix programs \(p\in S\) and \(q\notin S\), and we also can fix a program \(s\) which computes the characteristic function of \(S\).

Now let

\[\begin{split} \begin{array}{lcl} f(x) & = & \left\{ \begin{array}{ll} [\![q]\!](x) &\mbox{if $ [\![s]\!](x)\simeq 1$} \\ [\![p]\!](x) &\mbox{if $ [\![s]\!](x)\simeq \#$} \end{array} \right. \end{array} \end{split}\]

Let \(x^*\) be such that \([\![x^*]\!] = [\![f(x^*)]\!]\). If \(x^*\in S\), then \( [\![s]\!](x^*)\simeq 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 \(q\notin S\), we have \(f(x^*)\notin S\). This contradicts \(S\) being closed under equivalence. So we have a contradiction in case \(x^*\in S\). But we have a similar contradiction in case \(x^*\notin S\).

Corollary 7

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

Exercise 67

Show that \(Inf \leq_m Tot\) and \(Tot \leq_m Inf\).

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?