I am looking at the following proof that the halting problem is not recursive.

We suppose that it is recursive, i.e., for the given universal turing machine $U$ and the produced enumeration of all the turing machines as $T_1, \dots , T_n$, there is a turing machine $M$ such that $M$ with input $(n,x)$ gives output $1$ if $T_n$ with input $x$ halts and output $0$ if $T_n$ with input $x$ does not halt. It is obvious that we can convert $M$ to a turing machine $M'$ with the following property: $M'$ with input $(n,x)$ halts iff $M$ with input $(n,x)$ halts with output $0$. We check what $M'$ does with input $(n,n)$ and we get a contradiction.

We have the following:

$M(n,x)=\left\{\begin{matrix} 1 \ \ \text{ if } T_n(x)\downarrow \\ 0 \ \ \text{ if } T_n(x)\uparrow \end{matrix}\right.$


$M'(n,x)=\left\{\begin{matrix} \downarrow \ \ \text{ if } M(n,x)=0 \Leftrightarrow T_n(x)\uparrow \\ \uparrow \ \ \text{ if } M(n,x)=1 \Leftrightarrow T_n(x)\downarrow \end{matrix}\right.$

Why do we get a contradiction for $x=n$ ?


For this to work properly, we need to define $M'$ as $$M'(n) = \begin{cases} \downarrow \text{ if } M(n,n) = 0 \iff T_n(n) \uparrow \\ \uparrow \text{ if } M(n,n) = 1 \iff T_n(n) \downarrow\end{cases}$$

Now, since $M'$ is a Turing machine, it must have correspond to one of the Turing machines in our enumeration $T_1, T_2, \dots$, say $M' = T_m$. Then if we run $M'$ with input $m$ we get $$M'(m) = \begin{cases} \downarrow \text{ if } T_m(m) = M'(m) \uparrow \\ \uparrow \text{ if } T_m(m) = M'(m) \downarrow\end{cases}$$

Now we get a contradiction since $M'(m) \downarrow$ if $M'(m) \uparrow$ and $M'(m) \downarrow$ if $M'(m) \uparrow$.

| cite | improve this answer | |
  • $\begingroup$ So, for input $(i,i)$ the coding of the Turing machine $M'$ and $M$ is the same? $\endgroup$ – Mary Star Aug 23 '16 at 17:34
  • 1
    $\begingroup$ @MaryStar well almost, except $M$ takes two numbers as input whereas $M'$ only takes a single number. $\endgroup$ – mrp Aug 23 '16 at 17:57
  • $\begingroup$ Ah ok!! Thank you!! :-) $\endgroup$ – Mary Star Jan 26 '17 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.