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

  • $\begingroup$ What does element of halt mean here? $\endgroup$ – Sagar P Nov 25 '17 at 14:36
  • 1
    $\begingroup$ @SagarP $HALT = \{ \langle M,w \rangle \mid M \text{ is a TM and } M \text{ halts on } w\}$. $\endgroup$ – fade2black Nov 25 '17 at 14:46
  • $\begingroup$ Hey, I have one silly doubt. In 2nd part where we find the complement of the language, why are you still considering union and not intersection ? It should be L1' intersection L2' and not L1' union L2' right ? $\endgroup$ – Sagar P Nov 27 '17 at 8:21
  • 1
    $\begingroup$ @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$. $\endgroup$ – fade2black Nov 27 '17 at 12:35
  • 1
    $\begingroup$ @SagarP complement of $L_1$ contains also strings starting with $1$. $\endgroup$ – fade2black Nov 27 '17 at 13:37

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.