Multiple choice

Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognisable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation. (4) Turing recognisable languages are closed under union and intersection.

  1. 1 and 4 only

  2. 1 and 3 only

  3. 2 only

  4. 3 only
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

(1) NTM $\cong$ DTM (2) RELs are closed under union but not complementation. (3) Turing decidable languages are recursive and recursive languages are closed under intersection and complementation. (4) RELs are closed under union and intersection but not under complementation.

Keep practicing — related questions