# Unrecognizability of HALT

I am currently stuck on a question from Sipser's book of automata. The question goes like this:

Consider the following language: V = {w|w = 0a for some a which is an element of HALT} U {w|w=1b for some b which is an element of complement of HALT }

Prove that V is unrecognizable? Prove that complement of V is unrecognizable?

I kinda know that to prove them we have to use contradiction but I got stuck after that and haven't been able to come up with any solution up till now. Any pointers/hints would be appreciated.

If $V$ was recognizable then the language of Halting problem could be reduced to $V$ as following.
Let $M_V$ be a TM recognizing $V$, i.e, $M_V$ accepts $x$ if $x \in V$. Let $u$ be some string (description of a TM). Then we run $M_V$ on $0u$ and $1u$ by dovetailing. $M_V$ will eventually halt on one of these inputs since $u$ is either in $HALT$ or not in $HALT$. So, when it halts we simply check: if $M$ has halted on $0u$ then $u \in HALT$, else if $M$ has halted on 1u then $u \notin HALT$. Thus this implies that $HALT$ is decidable which is impossible.
Similarly for $\overline{V}$. Let $u$ be some string (description of a TM). If $M_{\overline{V}}$ accepts $0u$ then $u \notin HALT$. If $M_{\overline{V}}$ accepts $1u$ then $u \in HALT$.
• @SagarP $HALT = \{ \langle M,w \rangle \mid M \text{ is a TM and } M \text{ halts on } w\}$. – fade2black Nov 25 '17 at 14:46
• @SagarP You are right, $\overline{V} = \overline{L_1} \cap \overline{L_2}$ and I don't claim that it is union. I simply use the fact that $\forall u \notin HALT$, $0u \in \overline{V}$ and $\forall u \in HALT$, $1u \in \overline{V}$ by the definition of $V$. – fade2black Nov 27 '17 at 12:35
• @SagarP complement of $L_1$ contains also strings starting with $1$. – fade2black Nov 27 '17 at 13:37