edited by
823 views
0 votes
0 votes
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$

is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$
edited by

1 Answer

0 votes
0 votes
Last time I said as it was undecidable it is actually Semi Decidable. We can't really say. As the condition M1 <M2 so Semi Decidability is satisfied. Hence, M1 is reduciblie to M2 is recursive enumerable.

One way theorem satisfies these conditions of semi-decidability are:

1. P <--- P

2. NP <---- NP

3. Recursive Enumerable <---- Recursive enumerable

4. Recursive lang <--- Recursive Language
edited by

Related questions

0 votes
0 votes
0 answers
2
aditi19 asked Oct 29, 2018
247 views
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
0 votes
0 votes
0 answers
4
sushmita asked Dec 23, 2016
394 views
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems...