UTM REDUCTION

191 views

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
0

How is LU recursive and not REL ?

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 Lu is a set of strings which the TM accepts..Hence Lu 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 ?
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 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
1
201 views
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
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .