Undecidabilty

Question

L= {<M1,M2>| M1 and M2 are two TMs and $\varepsilon \epsilon L(M1)\cap L(M2)$}.

Is it RE or not RE?

Comments

Sir if M1=M2, it can either contain $\varepsilon$ or may not contain $\varepsilon$. So Sir are you saying to simulate the TM for L on every pair of TMs such that if any pair halts and accepts $\varepsilon$, then that pair <M1,M2> belongs to the language L? If this is the approach, then L becomes semi-decidable, isn't it?

---

You can see the answer now.

---

Got it Sir. Thanks :)

Answer 1

We know that if a TM accepts $\epsilon$ or not is semi-decidable but not decidable (undecidable) (Rice's theorem). So, the given problem must also be undecidable as by taking $M_2 = M_1$, it reduces to the known undecidable problem.

Now, the given problem is semi-decidable, because we can semi-decide it in two steps. First see if $M_1$ accepts $\epsilon$ and then see if $M_2$ accepts $\epsilon.$ If $\epsilon$ is in $L$ both $M_1$ and $M_2$ will halt making our problem semi-decidable.

Comments

@Somoshree $0$ is always problematic and so is $\epsilon$ :)

$L_1 \backslash L_2$ is basically the set of all suffix strings of $L_1$ and so if there is no string in $L_1$ this should be empty set.

Now question of whether $\epsilon$ is in $L_1 \backslash L_2$ is same as if $L_1$ is not empty. Because for any string $\epsilon$ can act as a suffix. So, this problem is undecidable but recursively enumerable.

---

Sorry Sir..and thank you Sir for giving your valuable time in making me understand :)

---

tell me some resource from where i can read about decidabilty in detail

Answer 2

I think the language will be not RE because we have to do infinite comparisons between two languages of turing machine which is notRE.

Comments

Even I think so. If we simulate M1 and M2 with $\varepsilon$ then even if one TM may halt, but we never know after how many steps the other TM will halt.

But check in the following link once. It says that the language is RE.

https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf

 

 

---

its really ambigouos to decide. because if both of them accepts only epsilon than also we have to go for infinite comparisons.