retagged by
1,344 views

1 Answer

Best answer
4 votes
4 votes

First we should get the class of L(M) by reduction theory then think for L which is the language of  TMs representing L(M)..So the reduction mentioned is :

L(M)  <p  { 0p 12p | p > 0 } .

Hence the RHS is context free language and hence recursive..As we know in reduction theory the class P, NP , REC and RE are considered easier and reduction is hence done for them right to left.So if we know RHS then we know LHS is of same class but if LHS is known but not RHS we cannot say anything regarding the class of RHS..

Vice versa works for hard problems(undecidable and NP hard).

So it follows that L(M) is as hard as the RHS problem..

But this does not change the non trivial property of the problem

Hence the given problem is undecidable..Hence A) is correct answer..

edited by

Related questions

3 votes
3 votes
1 answer
1
0 votes
0 votes
1 answer
2
Veerendra V asked Dec 27, 2016
606 views
How does complement of a Recursively enumerable but not recursive is not recursively enumerable?