Let A, B, C, D, and E be languages, with A decidable, C Turing
recognizable, D not Turing recognizable, and E is not decidable.
Circle the letters of the true statements. Theorems &
corollaries: If L ≤m L' and L' TR, then L is also TR. If L ≤m L'
and L' TD, then L is also TD. If L ≤m L' and L not TR, then L' is
also not TR. If L ≤m L' and L not TD, then L' is also not TD. a) If
A ≤m C and A ≤m C, then C is decidable. b) If D ≤m B, then B is not
decidable. c) If C ≤m C, then C is decidable. d) If E ≤m B and B ≤m
C, then B is not co-Turing recognizable
Let A, B, C, D, and E be languages, with A decidable, C Turing recognizable, D not Turing recognizable, and E is not dec
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
Let A, B, C, D, and E be languages, with A decidable, C Turing recognizable, D not Turing recognizable, and E is not dec
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!