# Why apply the assumed decide für HALT to the input and its code?

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?

• 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$. – Rick Decker Nov 22 '14 at 18:00
• 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. – 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
else
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.