881 views
0 votes
0 votes
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }.

is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.

1 Answer

Best answer
2 votes
2 votes

I'm assuming the given operation is set difference. 

The given problem is, given two Turing machines $M_1$ and $M_2$ if $\epsilon$ is accepted by $M_1$ and not accepted by $M_2.$

Lets assume this problem is semi-decidable or equivalently the corresponding language is recursively enumerable. i.e., we have a Turing Machine say $N$ to semi-decide it (given a string which is in $L$ TM $N$ will always say "yes")

Now, consider another known problem which is not even semi-decidable  say $P$

  • given a TM $A$ if $\epsilon$ is not accepted by it. 

Using our assumed TM $N$, we can make a TM for $P$ as follows:

  • Take $M_1$ as a TM which accepts $\epsilon$ (its language can be anything but must contain $\epsilon)$
  • Take $M_2$ as $A$ the given input TM

Now, if our TM $N$ outputs "yes" it means $M_2$ or equivalently $A$ must not accept $\epsilon$ as we know that $M_1$ accepts $\epsilon.$ i.e., using TM $N$ we semi-decide a known not even semi-decidable problem. So, such a TM $N$ cannot exist. i.e., the original given problem is not even semi-decidable. 

selected by

Related questions

0 votes
0 votes
0 answers
4