Log In
5 votes

please give proper reasoning.

in Theory of Computation 191 views

1 Answer

4 votes
Best answer

In the given question , Lis a set of strings which are accepted by the Universal Turing Machine..In order words , these are the strings in which the given Turing machine halts and each of the string of LU has this property..In other words , L represents a recursive language (or a recursive set)..

Now given reduction :   L  β‰€  LU

Now we know that for easy problems (or) languages [ REC (or) decidable , RE , P , NP ] , reduction works right to left i.e. if the class of the right part of the reduction is known , then we can deduce the left part also..But other way round , we cannot conclude anything..

As here , LU is a recursive language , so due to the reduction : L  β‰€  LU  , L is recursive as well..

Hence option C) should be correct..

selected by

How is LU recursive and not REL ?


Actually here the universe of strings is not mentioned like strings in {0,1}* which are accepted by the turing machine..

It is mentioning already that Lu is a set of strings which the TM accepts..Hence Lu should be recursive..

Thanks @HabibKhan

one question what do you mean by easy problems and does reduction from right to left work only for these languages ?

Actually , I termed easy problems according to the language class..If a problem (or) language belongs to P , NP , recursive , RE or decidable then these are considered as "easy" problems and for reduction of "easy" problems reduction works right to left.

As in the case here , we know the right side of reduction which is LU is REC , so we can conclude L is REC as well.

But say L were known to be REC , then we cannot conclude anything regarding Lu.

For this , I would suggest u to study :reduction theorems in TOC

Related questions

1 vote
0 answers
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizable Then $L_{1}$ cannot be A)not REL B)Context Sensitive C)Context Free ​​​​​​​​​​​​​​D)Recursive
asked Feb 28, 2019 in Theory of Computation srestha 201 views
0 votes
0 answers
A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true? A) B is Recursive B) B is Recursive Enumerable C) B is Not RE D) B is CFL
asked Sep 19, 2018 in Theory of Computation Mk Utkarsh 164 views