3 3 votes Check whether the language below is recursive, recursively enumerable but not recursive, or not recursively enumerable? L={⟨M⟩∣ M halts on all palindromes}. How can i use Rice's theorem here? Tyes={All palidroms} Tno={Signma*}.Will that work here? M halts on all palindromes means M halts on only palindromes ? Theory of Computation theory-of-computation turing-machine decidability + – rahul sharma 5 1.5k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply Kapil commented Aug 8, 2017 reply Follow flag Same reason is also applicable here, as I told in your previous question. 0 0 replyShare rahul sharma 5 commented Aug 8, 2017 reply Follow flag I was thinking the same way.Not getting cough confidence though:) 1 1 replyShare Please log in or register to add a comment.
Best answer 2 2 votes I think the given language is NOT RE. L is the collection of all such TMs which halts on all palindromes. I think it's not possible to say that a TM halts on all palindromes, it will keep on checking before we can conclude a TM halts on all palindromes. Manu Thakur answered Aug 7, 2017 • selected Aug 20, 2017 Manu Thakur comment Share Follow See 1 comment 1 1 comment reply rahul sharma 5 commented Aug 8, 2017 reply Follow flag Yes,right. Thanks 0 0 replyShare Please log in or register to add a comment.
0 0 votes We can apply Rice' Theorem here because: 1. Its a non trival property as there are some TM which does not halt on all palindrom and some are halt. 2. Its a language property obviously. So, The above problem is undecidable. mystylecse answered Sep 8, 2017 mystylecse comment Share Follow 0 reply Please log in or register to add a comment.
