turing machine

Question

L = { <M>  | M is a turing machine and L(M) <=_p  {0^p 1^2p | p>0}} where <=_{p denotes polynomial time reducible}

a) L is undecidable

b)L is decidable

c)L is regular

d)none

Answer 1

answer a)

The question wishes to know that whether L is undecidable, decidable or regular when it has given L(M) is decidable. So it asks whether L is equivalent to L(M) or not.

Now, { 0^p1^2p | p >= 0 } is a DCFL.

DCFL is REC,i.e always decidable. So, L(M) is reducible to a decidable lang. then L(M) also has to be decidable.Thus the problem reduces to,

L = { <M> | M is a TM & L(M) is decidable }

Usually a lang. accepted by a TM is RE. Now whether RE is REC, i.e decidable or not, is a non-trivial question because some TM can accept REC while some only RE.

[ since we know, RE may or may not be REC, thus non-trivial question ]

And also by Rice's theorem any non-trivial question on an RE lang. is always Undecidable.

Comments

the answer is undecidable...but i did approach the same way as u did

---

@Tuhin WHAT is DCFL? You have to first see what L means.

---

Sir, DCFL is a PDA for which every state transition is deterministic or that never has a choice in its move, i.e at most one move can be made.

Like: Even length palindrome is not DCFL: L  = { WW^R: W belongs to (a,b)*} because when to start checking for the reverse string to match with W is not deterministic while Odd length palindrome is DCFL L = { WcW^R: W belongs to (a,b)* } 

In the above question, I missed what L is. The question wishes to know that whether L is undecidable, decidable or regular when it has given L(M) is decidable. So it asks whether L is equivalent to L(M) or not.

Now, { 0^p1^2p | p >= 0 } is a DCFL.

DCFL is REC,i.e always decidable. So, L(M) is reducible to a decidable lang. then L(M) also has to be decidable.Thus the problem reduces to,

L = { <M> | M is a TM & L(M) is decidable }

Usually a lang. accepted by a TM is RE. Now whether RE is REC, i.e decidable or not, is a non-trivial question because some TM can accept REC while some only RE.

[ since we know, RE may or may not be REC, thus non-trivial question ]

And also by Rice's theorem any non-trivial question on an RE lang. is always Undecidable.