3 3 votes L = { <M> | M is a TM and |L(M)| <= 3 }. Is it Recursively Enumerable or not ? Theory of Computation decidability theory-of-computation + – ankitgupta.1729 1.6k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 3 3 votes It is a property of language of Turing machines (recursively enumerable languages), Using Rice's theorem, there exists Turing Machine $T_{yes}$ for $L=\{a, aab\}$ and Turing machine $T_{no}$ for $L=(a+b)^*$ and also $L(T_{yes}) \subset L(T_{no})$, making the property non-trivial as well as non-monotonic. Hence, the above language is not recursively enumerable as per Rice's theorem part 2. https://gatecse.in/rices-theorem/ joshi_nitish answered Nov 11, 2017 • selected Nov 11, 2017 by Arjun joshi_nitish comment Share Follow See all 4 Comments 4 4 Comments reply Arjun commented Nov 11, 2017 reply Follow flag @Joshi the last part is not exactly correct. When we say subset, it involves 2 sets but you wrote two Turing Machines. 0 0 replyShare joshi_nitish commented Nov 11, 2017 reply Follow flag thankyou sir, corrected.. 1 1 replyShare ankitgupta.1729 commented Nov 11, 2017 reply Follow flag Thank you Nitish Joshi and Arjun Sir .. 1 1 replyShare Parshu gate commented Nov 30, 2017 reply Follow flag What does this actually mean "Tyes for L={a, aab} and Tno for L=(a+b)* and also L(Tyes)⊂⊂L(Tno)," ? 0 0 replyShare Please log in or register to add a comment.
