How is L_{U} recursive and not REL ?

4 votes

Best answer

In the given question , L_{U }is 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 L_{U} has this property..In other words , L_{U } represents a recursive language (or a recursive set)..

Now given reduction : L β€ L_{U}

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 , L_{U} is a recursive language , so due to the reduction : L β€ L_{U }, L is recursive as well..

**Hence option C) should be correct..**

1

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 L_{u} is a set of strings which the TM accepts..Hence L_{u} should be recursive..

0

Thanks @HabibKhan

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

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

0

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 L_{U} 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 L_{u}.

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