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 Show 8 previous comments 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.