0 votes 0 votes A. L is undecidable B. L is decidable C. L is regular. D. None of these. Please explain in detail. Theory of Computation turing-machine theory-of-computation decidability recursive-and-recursively-enumerable-languages + – Shubham Kumar Gupta asked Dec 23, 2017 Shubham Kumar Gupta 562 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Manu Thakur commented Jan 1, 2018 reply Follow Share i think A is Answer? 0 votes 0 votes Anu007 commented Jan 1, 2018 reply Follow Share 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 votes 0 votes Manu Thakur commented Jan 1, 2018 reply Follow Share @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 votes 0 votes Anu007 commented Jan 1, 2018 reply Follow Share yes, this is also correct, informally( i don't know how formally we can be proved) 0 votes 0 votes reboot commented Jul 17, 2020 reply Follow Share Duplicate question: https://gateoverflow.in/192804/decidability 0 votes 0 votes Please log in or register to add a comment.