The Gateway to Computer Science Excellence
0 votes

A.  L is undecidable

B.  L is decidable

C.  L is regular.

D.  None of these.

Please explain in detail.

in Theory of Computation by (449 points) | 156 views
i think A is Answer?

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.

@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.

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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,832 questions
57,686 answers
107,214 users