2
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ What does element of halt mean here? $\endgroup$
    – Sagar P
    Nov 25, 2017 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, 2017 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, 2017 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, 2017 at 12:35
  • 1
    $\begingroup$ @SagarP complement of $L_1$ contains also strings starting with $1$. $\endgroup$
    – fade2black
    Nov 27, 2017 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.