2 votes 2 votes If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable? Theory of Computation turing-machine decidability regular-language + – adwaitLP asked Sep 13, 2017 adwaitLP 2.1k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Warlock lord commented Sep 13, 2017 reply Follow Share Undecidable. But It is recognizable (R.E) –1 votes –1 votes joshi_nitish commented Sep 13, 2017 reply Follow Share it is neither decidable nor Recursively enurable 3 votes 3 votes Warlock lord commented Sep 13, 2017 reply Follow Share Right. If it were something like "L is a Regular Language and accepts regular sets", this would be a R.E, right? Because it can have a 'yes' ? 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes $T_{yes}=\phi$ $T_{no}=0^{n}1^{n}$ using Rice theorem $2$, Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable non-monotonic property Holds as -: $T_{yes}\subset T_{no}$ Hence is is not turing recognizable , so no chance of its decidablity. sourav. answered Sep 13, 2017 selected Sep 13, 2017 by adwaitLP sourav. comment Share Follow See all 11 Comments See all 11 11 Comments reply A_i_$_h commented Sep 13, 2017 reply Follow Share can someone suggest a good video or liink to understand rice theorem easily please 0 votes 0 votes sourav. commented Sep 13, 2017 reply Follow Share http://gatecse.in/rices-theorem/ 0 votes 0 votes adwaitLP commented Sep 13, 2017 reply Follow Share What is recognizability? Can someone explain! 0 votes 0 votes sourav. commented Sep 13, 2017 reply Follow Share recognizablity?what recognizablity? if a Language is turing recognizable,it will be accepted by Turing M/c,hence RE. go through the link http://gatecse.in/rices-theorem/ 1 votes 1 votes srestha commented Sep 13, 2017 reply Follow Share if we ask a question like "if a number is divisible by 2" then there are two answer possible either "yes" or "no". like take a number 8 if 8 is divisible by 2? ans is yes if we take a number 9, then answer will be "no" So, where yes and no both ans possible, that language is called turing decidable language. Because we can definitely say yes and no ans for it In turing recognizable language Similarly we can predict "yes" ans, but cannot say anything about "no" ans 0 votes 0 votes Rishabh Gupta 2 commented Sep 13, 2017 reply Follow Share Is there any other link, video or something for rice theorem and related stuff?? "Other than gatecse link." 0 votes 0 votes A_i_$_h commented Sep 13, 2017 reply Follow Share (1) L(M)L(M) has at least 10 strings We can have TyesTyes for Σ∗Σ∗ and TnoTno for ϕϕ. Hence, L={M∣L(M) has at least 10 strings}L={M∣L(M) has at least 10 strings} is not Turing decidable (not recursive). (Any other TyesTyes and TnoTno would also do. TyesTyes can be any TM which accepts at least 10 strings and TnoTno any TM which doesn’t accept at least 10 strings ) how this is not turing decidable iunderstood the monotonic property ( part 2) but not clear with PaRT 1 @sourav 0 votes 0 votes sourav. commented Sep 13, 2017 i edited by sourav. Sep 14, 2017 reply Follow Share @A_i_$_h, A language is decidable iff it is Recursive(i.e indirectly CSL,CFL,RL) There is no point of arguing that a language which is not even RE will decidable or not !? 0 votes 0 votes A_i_$_h commented Sep 14, 2017 reply Follow Share y its is not RE ? 0 votes 0 votes Arjun commented Sep 14, 2017 reply Follow Share @sourav A language is decidable iff it is recursive -- not all r.e. languages are decidable. 0 votes 0 votes sourav. commented Sep 14, 2017 reply Follow Share @arjun sir, Thanks! I missed it.Updated! 0 votes 0 votes Please log in or register to add a comment.