The Gateway to Computer Science Excellence
0 votes
120 views
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.
in Theory of Computation by Loyal (7.8k points) | 120 views
0
$(M_1)$ \ $L(M_2)= L(M_1) \cap \bar{ L(M_2)}$

M2 is a TM so L(M2) is RE and $\bar{L(M_2)}$  is not RE.

Whether ∈ belongs to L(M1) which is RE is an undecidable problem. But whether ∈ belongs to $\bar{L(M_2)}$ which is non RE also should be undecidable.

But L whether RE or not RE is the question :/

Somebody please help here.. :(
0

@MiNiPanda

I think it depends on if M1 and M2 RE or non RE on that

0

@srestha

M1 and M2 are TMs (given) that means L(M1) and L(M2) are RE..am i going wrong?

0
Is it halting TM always?
0
No I guess..
0
Then how will you telling it will be RE always

It could be Rec too, or non RE too
0
answer given was non re
0

night i got some reason behind it plzz see if it is correct....

from halting problem i reduced -----1st point to prove can we say yes if it has epsilon or not ............see we have one turing machine tm1 and epsilon is not there till now  , and language may be infinite  so we came across epsilon now can we say that yes it has epsilon ? no because we still have to see l2 that it have epsilon or not ......so we cant yes ............ hence not RE   is it correct ?

0

@Deepanshu Didn't get you.. :(

0
that is one question that how is L(r1) / L(r2) = L(r1) Intersection    ( complement  of )L(r2)

because if its so then L(r1)- L(r2) = L(r1) / L(r2)
0

@MiNiPanda

chk below

1 Answer

+2 votes
Best answer

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. 

by Veteran (431k points)
selected by
0

@Arjun Sir, please clarify few things..

1) is this operator left quotient?

2) you have reduced this problem to complement of halting problem which is well known Non RE. Am i right?

3) Can we prove this language by Rice's second theorem?

+1
1. No, I suppose it is set difference

2. No. I reduced from complement of halting (accepting) problem to the given problem and not the other way

3. Not easy here as we don't know the strings in $L$
0
but what is final answer

It could be RE and non RE both?
0
Please read the answer again.
0

@Arjun 

Sir,

If the machine is like $M_{1}-M_{2}$

And as u said $M_{2}$ does not accept $\epsilon$ . Say it is like $\Sigma ^{+}$

Then will it not even R.E.?

I am not getting this

0
And why we only checking $M_{2}$ part and telling, it is not even RE? Why not at the mean time we looking after $M_{1}$ too?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
198,506 comments
105,272 users