1 votes 1 votes Theory of Computation decidability theory-of-computation turing-machine recursive-and-recursively-enumerable-languages + – Na462 asked Nov 14, 2018 Na462 1.6k views answer comment Share Follow See all 22 Comments See all 22 22 Comments reply Show 19 previous comments Gurdeep Saini commented Nov 15, 2018 reply Follow Share @na462 i think uou are right 0 votes 0 votes Somoshree Datta 5 commented Nov 15, 2018 reply Follow Share For L2, by applying Rice's 1st theorem, we can say that L2 is undecidable. But we can apply Rice's 2nd theorem here. So here in order to know if L(tm) is not a subset of {00,11}, we can see if it accepts atleast one string other than 00 and 11..In that case we can halt and say that<TM> belongs to L2 since L(TM) is not a subset of {00,11}. But we can never be sure about the no case of the problem, i.e. whether L(TM) is a subset of {00,11}. So this is semi decidable and RE. Is this approach correct? 0 votes 0 votes Gurdeep Saini commented Nov 18, 2018 reply Follow Share Somoshree Datta 5 yes your approach is right 0 votes 0 votes Please log in or register to add a comment.