In the lecture notes I have got in class I have the following proof for the halting problem not being recursive

  1. Assume $H$ is recursive and TM $M_1$ decides it.
  2. Construct $M_2$ that
    1. gets input $x$ in $\{0,1\}^*$ and transform it into $x*code(x)$
    2. applies $M_1$ to $x * code(x)$
  3. if x is in SA (Self Accepting), $M_1$ halts on $Y$ if x is in SA (Self Accepting), $M_1$ halts on $Y$
  4. $M_2$ decides SA, hence a contraddiction

In this prove, I am confused on what would $x*code(x)$ correspond to. Is the input followed by the coded input? Why would we want to do so?

| cite | improve this question | | | | |
  • $\begingroup$ Is $SA=\{\langle M\rangle\mid \langle M\rangle\in L(M)\}$? In other words, is $SA$ the language of all TM descriptions $\langle M\rangle$ such that $M$ accepts when given its own description? Whether or not, there seems to be something wrong with your (3): first, the two clauses are identical and second, you haven't defined $Y$. Finally, making some obvious corrections to your post it seems that you need one more step in the description of $M_2$. $\endgroup$ – Rick Decker Nov 22 '14 at 18:00
  • 1
    $\begingroup$ The x*code(x) expression appears to be an attempt to emphasize that we're running a TM on its own description. In my opinion, it's not a particularly good attempt in this context. $\endgroup$ – Rick Decker Nov 22 '14 at 19:12

Let $H=\{(\langle M\rangle, x)\mid M, \text{ when given input }x, \text{ halts}\}$. In other words, the language $M$ consists of all pairs of TM descriptions and words, such that the TM halts on that word.

Let $SA=\{\langle M\rangle\mid M, \text{ when given its own description, halts}\}$. You're given the fact that $SA$ is undecidable.

Suppose, to the contrary, that $H$ was decidable, so that there was a TM $M_1$ such that when given a pair, $(\langle M\rangle, x)$, of a TM $M$, and a word $x$ $$ M_1((\langle M\rangle, x)) = \begin{cases}\text{accept}, & M(x) \text{ halts}\\ \text{reject}, & M(x) \text{ doesn't halt}\end{cases} $$ We'll use this to build a decider, $M_2$, for SA, establishing the desired contradiction. Define

M2(<M>) =
   if M1((<M>,<M>)) = accept  ; does M halt on its own description?
      return M(<M>)           ; if so, this will always halt
      return reject

Now if $M$ halts on its own description, the if test will detect that and so we can simulate the action of $M$ on $\langle M\rangle$, be sure it halts, and return the result, either accept or not. If $M$ doesn't halt on its own description, we reject. The upshot is that we'll have built a decider, $M_2$ for $SA$, so have a contradiction, and hence our assumption that $H$ was decidable, must be false.

| cite | improve this answer | | | | |

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.