2 2 votes CONSIDER TWO PROBLEMS: $L_1$ IS A DECIDABLE LANGUAGE, AND $L_2$ IS A RECURSIVELY ENUMERABLE (R.E.) BUT NOT DECIDABLE LANGUAGE. LET $L_3$ BE ANOTHER LANGUAGE.WHICH ONE OF THE FOLLOWING STATEMENTS IS FALSE? IF $L_3$ IS R.E. AND ITS COMPLEMENT $\bar{L}_3$ IS ALSO R.E., THEN $L_3$ IS DECIDABLE. IF $L_3$ IS REDUCIBLE TO $L_1$, THEN $L_3$ IS DECIDABLE. IF $L_2$ IS REDUCIBLE TO $L_3$, THEN $L_3$ IS UNDECIDABLE. IF $L_1$ IS REDUCIBLE TO $L_3$, THEN $L_3$ IS DECIDABLE. Theory of Computation goclasses theory-of-computation goclasses-cs-dpp goclasses-cs-dpp-day-131 goclasses-toc-practice-questions + – GO Classes 278 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
0 0 votes Gemini generated answerOption D:Reducing an easy (decidable) problem to a harder one tells us nothing about the difficulty of the harder problem. For example, any decidable language L1 can be easily reduced to the Halting Problem (which is undecidable).Therefore, L3 could be decidable, or it could be undecidable. Asserting that L3 is decidable is incorrect. pratikmishra1200 answered Jun 10 pratikmishra1200 comment Share Follow 0 reply Please log in or register to add a comment.
