MadeEasy Subject Test: Theory of Computation - Decidability

Question

1) L is undecidable

2) L is decidable

3) L is regular

4) none 

Answer given: 1) undecidable

My solution: Since L(M) is reducible to a CFL language and since all CFL are recursive that means language accepted by M is recursive. And since recursive halts on all inputs so this language will too and answer should be decidable.

How to approach this type of question ?

Comments

I think the answer is correct. M is a machine which generates some language,it is form of CFL.Now this whole problem itself is the language 'L' which we need to run on some machine to check if this is correct i.e whether the machine M generates language which is CFL or not.Now this being a non-trivial property is undecidable.

---

Yes it's undecidable by Rice Theorem. 

T_yes = aⁿb²ⁿ

T_no = (sigma)*

T_yes is a subset of T_no. Therefore follows the Non-trivial property. Hence undecidable. 

---

Duplicate question:

https://gateoverflow.in/76610/decidability

Answer 1

Check this one out https://gateoverflow.in/83074/what-is-the-difference. The answer section provides detailed explanation. Also at the end part it states that recursive is decidable.