1
$\begingroup$

$L_0=\{\langle M,w,0\rangle\mid M \text{ halts on } w\}$

$L_1=\{⟨M,w,1⟩\mid M \text{ does not halts on } w\}$

Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit. 

Let $L=L_0 \cup L_1$. Is $L$ non R.E ?

After seeing the question I was able to figure out that there are some strings that do not belong to $L_0$ as well as $L_1$.

Like, lets take the case for $L_0$ and a string $001\dots10−01−1$, ("$-$" shown for notation purpose only) where the  first component describes a TM $M$ followed by input "$w=01$" and last bit "$1$". Now suppose M halts on "$01$". Still the given input is not in $L_0$ as the last bit is "$1$" and not "$0$" as required by $L_0$. So, this input must be in $L_1$. But since $M$ halts on $w$, this input is not in $L_1$ either.  So there are infinite strings like these. I am not able to prove that these infinite set of strings are not r.e.

Is there any method to solve these kind of problems? I am not able to master these kind of problems.

Please someone help.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ The method to solve this kind of problem is to solve a few of these exercises. We can solve each given exercise for you, but you will never understand the material until you struggle with it on your own. $\endgroup$ – Yuval Filmus Sep 6 '17 at 13:12
  • $\begingroup$ For some of the problems I am finding it hard to reduce it to halting problem :( $\endgroup$ – Zephyr Sep 6 '17 at 13:21
  • 2
    $\begingroup$ Hint: Assume that $L$ is r.e. and $M_L$ recognizes $L$. Given $M, w$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in in $L$. Then ... recall what a r.e. set means, and think about how you could run/simulate $M_L$ on both input $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ simultaneously. $\endgroup$ – fade2black Sep 6 '17 at 19:44
  • $\begingroup$ @fade2black, Actually I did the same thing to other problem slightly different than this and I got confused there. You can see the link here :- cs.stackexchange.com/questions/80892/… $\endgroup$ – Zephyr Sep 6 '17 at 19:46
4
$\begingroup$

Assume that $L$ is r.e. and $M_L$ recognizes $L$. Given $\langle M,w \rangle$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in $L$. Then using a universal Turing machine start to run/simulate $M_L$ on both inputs $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$, simultaneously, say one step at a time for each input. After each step check if $M_L$ halts on at least one input. Since $L$ is r.e. and exactly one of $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ belongs to $L$, $M_L$ must eventually halt on one of them. Depending on which input $M_L$ halts, you can tell if $M$ halts on $w$. This decides the Halting problem and hence $L$ is not r.e.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer . Why can't we apply the same thing over here cs.stackexchange.com/questions/80892/…. If we do the same thing there then even that problem is non r.e and not regular. Why is that 3rd bit changing the results ? $\endgroup$ – Zephyr Sep 6 '17 at 20:45
  • 1
    $\begingroup$ That language is quite different from this one. Pay attention to additional 0 and 1s in this case. That one is decidable and mainly about encoding rather than halting. The third bit bears information about halting of $M$ on $w$. That's why we can reduce the HP to $L$ in case $L$ is r.e. $\endgroup$ – fade2black Sep 6 '17 at 20:50
  • $\begingroup$ So in the question which is in the link, even if we halt on one of L1 or L2, then we won't be able to solve halting problem because in both the cases input w is same and there is no way to differentiate them as we don't have 3rd bit ? $\endgroup$ – Zephyr Sep 6 '17 at 21:13
  • 1
    $\begingroup$ Right, since $L$ is the union, you cannot tell which one $\langle M,w \rangle$ belongs to. In fact $L_1 \cup L_2$ in that question is the set of all TMs. $\endgroup$ – fade2black Sep 6 '17 at 21:18
  • 1
    $\begingroup$ Warning: not "...both the cases input w" but should be "..both the cases input <M,w>" $\endgroup$ – fade2black Sep 6 '17 at 21:21
2
$\begingroup$

The Turing machine $M$ doesn't halt on $w$ if and only if $\langle M,w,1 \rangle \in L$. This shows that $L$ is not r.e.: if it were, then since the halting problem is r.e., we would get a decision procedure for the halting problem. Similarly, $L$ is not co-r.e.

| cite | improve this answer | |
$\endgroup$

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.