0 votes 0 votes If Language L1 is reducible to L2 and L2 reducible to L1, then shouldn't they both be Recursively Enumerable Languages? I am really confused with the option given. Source : testbook.com live test on 3rd January, 2016 Theory of Computation recursive-and-recursively-enumerable-languages normal compound-automata + – Utk asked Jan 4, 2016 • retagged Jul 4, 2017 by Arjun Utk 701 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes as both are polynomial time reducible ie both decidable Solution also says both are decidable tiger answered Jan 4, 2016 tiger comment Share Follow See all 3 Comments See all 3 3 Comments reply Utk commented Jan 4, 2016 reply Follow Share My confusion is that the second statement, L1 is Recursive and L2 is RE should also be false, since both are decidable languages. Thus, both the options should be false, right? 0 votes 0 votes tiger commented Jan 5, 2016 reply Follow Share yes 0 votes 0 votes mkg243001 commented Jun 18, 2016 reply Follow Share why it is decidable? 0 votes 0 votes Please log in or register to add a comment.