0 votes 0 votes 1. Turing Decidable means Recursive language 2. Turing recognizable means REL 3. Decidable means Recursive 4. Undecidable means REL or Turing Recognizable. Does the 4th statement is correct or not . Plz give valid assertions and reasons. Theory of Computation theory-of-computation closure-property + – dragonball asked Dec 20, 2017 dragonball 342 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Ashwin Kulkarni commented Dec 20, 2017 reply Follow Share If you’re saying about membership of RE then it is undecidable. 0 votes 0 votes dragonball commented Dec 20, 2017 reply Follow Share What about option S1? Is it true or false ? 0 votes 0 votes Ashwin Kulkarni commented Dec 20, 2017 reply Follow Share Emptiness property for TM is undecidable. Hence I think it is false. 0 votes 0 votes Suneel Padala commented Jan 24, 2019 reply Follow Share S1 is false S2 is true Use rice Theorem part 2 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 1,2,3 are true 4th False Because Semi decidable are REL, undecidable are not even REL Suneel Padala answered Jan 24, 2019 Suneel Padala comment Share Follow See all 0 reply Please log in or register to add a comment.