3
$\begingroup$

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.$

and

$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$ ?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ So, for input $(i,i)$ the coding of the Turing machine $M'$ and $M$ is the same? $\endgroup$
    – Mary Star
    Aug 23, 2016 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, 2016 at 17:57
  • $\begingroup$ Ah ok!! Thank you!! :-) $\endgroup$
    – Mary Star
    Jan 26, 2017 at 10:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .