i think A is Answer?

The Gateway to Computer Science Excellence

0 votes

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 = {0^{p} 1^{2p}}

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?

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?

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,154 answers

193,758 comments

93,723 users