Self Doubt: Decidability

Question

$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 )$

Answer 1

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

Comments

Didn't understand anything 😞

---

@Arjun Sir, is not this question is incomplete? as we have not given any description about  machine M either it is decidable or undecidable

than how we can decide, in that case it should be not even RE.

not getting answer provided by@hina firdaus

---

M1 and M2 are inputs or like parameters to a function. That is from the input you can know the description of the 2 Turing machines and based on this you have to say if first one can be reduced to second or not -- so question is perfectly fine. For some inputs this is easy to say yes or no as answer but question is if we can always say yes or no correctly for all inputs.

---

so it is semidecidable or non R.E?