Assume statements S₁ and S₂ defined as: S₁: L₂ − L₁ is recursive enumerable…
2013
Assume statements S₁ and S₂ defined as:
S₁: L₂ − L₁ is recursive enumerable where L₁ and L₂ are recursive and recursive enumerable respectively
S₂: The set of all Turing machines is countable
Which of the following is true?
- A.
S₁ is correct and S₂ is not correct
- B.
Both S₁ and S₂ are correct
- C.
Both S₁ and S₂ are not correct
- D.
S₁ is not correct and S₂ is correct
Attempted by 18 students.
Show answer & explanation
Correct answer: B
S₁ is correct because the difference of a recursively enumerable language and a recursive language results in a recursively enumerable set. S₂ is correct because every Turing machine has a finite description, making the set of all Turing machines countable.
A video solution is available for this question — log in and enroll to watch it.