The halting problem¶

We come to one of the most famous and most basic results in computability theory.

Theorem 2

There is no program $p$ such that for all words $x$ and $y$,

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

Here is the 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} \phifn^1_q(a) & = & \left\{ \begin{array}{ll} \uparrow & \mbox{if $\phifn_a(a)\dar$}\\ \downarrow& \mbox{if $\phifn_a(a)\uparrow$} \end{array} \right. \end{array} \end{split}\]

Here’s how this would be done. 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

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

Contradiction!

Tip

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

Invitation to Computability

The halting problem

Contents

The halting problem¶

Corollaries¶

Improvement for one-register programs¶