611 views

1 Answer

Best answer
4 votes
4 votes

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

Related questions

1 votes
1 votes
0 answers
1
srestha asked Feb 28, 2019
486 views
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizableThen $L_{1}$ cannot beA)not RELB)Context SensitiveC)Context Free​​​​​​​​​​​​​​D)Recursi...
0 votes
0 votes
0 answers
2
Mk Utkarsh asked Sep 19, 2018
491 views
A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true?A) B is RecursiveB) B is Recursive EnumerableC) B is Not RED) B i...