156 views

A.  L is undecidable

B.  L is decidable

C.  L is regular.

D.  None of these.

| 156 views
0
0

question asking given turing machine M , will L polynomially reducible to Given language, which is same as
L(m) polynomialy reducible to DCFL ,
we know which is non trivial property , hence undecidable.

using Rice theorem:
Tyes = {0p 12p}

Tno = (0+1)*

Tyes subset of Tno hence undecidable, and NonRE.

0
@anu i used the following logic:

if an unkown problem  is polynomial time reducible to a recursive/ Decidable Problem then that unknown problem is also Decidable.

I think in this question they are asking if the language of the inputted turing machine is Decidable , and this is an Undecidable Problem.

right?
0
yes, this is also correct, informally( i don't know how formally we can be proved)

+1 vote