The Gateway to Computer Science Excellence
0 votes
$L=\left \{< M_{1},M_{2}> \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 )$
in Theory of Computation by Boss (11k points)
edited by | 187 views

1 Answer

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
by (33 points)
edited by
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.

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,833 questions
57,748 answers
108,120 users