Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

2. Turing recognizable languages are closed under union and complementation.

3. Turing decidable languages are closed under intersection and complementation.

4. Turing recognizable languages are closed under union and intersection.This question was previously asked in

GATE CS 2013 Official Paper

Option 3 : 2 only

IBPS SO IT Officer Mains: Full Mock Test

5486

60 Questions
60 Marks
45 Mins

** Answer**: Option 3

** Concept**:

A Turing machine is an automaton whose temporary storage is tape. This tape is divided into cells, each of which is capable of holding one symbol. Associated with the tape is a read-write head that can travel right or left on the tape and that can read and write a single symbol on each move.

Languages that are recognized and accepted by this Turing machine are Turing recognizable languages.

Turing machines can be viewed as acceptors. Turing recognizable languages are those for which there exists a Turing machine that will halt and accept the strings in that language. Turing machine does not halt for those strings which are not present in a language.

Closure properties of Turing recognizable languages:

1) Union

2) Concatenation

3) Kleen closure

4) Intersection

Turing recognizable languages are not closed under complement.

The power of the Turing machine in both the cases deterministic and non-deterministic is the same.

For every deterministic Turing machine there exists a non-deterministic Turing machine that recognizes the same language as that of the deterministic machine. So, this statement is correct.

** Explanation**:

__Statement__ 1:For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine

This Statement is **true**. The question is asking for a **false** statement.

__Statement 2__: Turing recognizable languages are closed under union and complementation.

This Statement is **false **since Turing recognizable languages are not closed under complementation operation.

__Statement 3__: Turing decidable languages are closed under intersection and complementation.

This Statement is **true**. since Turing decidable languages are nothing but recursive languages and recursive languages are closed under both intersection and complementation operation.

__Statement 4__: Turing recognizable languages are closed under union and intersection.

This Statement is **true**. since Turing recognizable languages are closed under union and intersection.

Hence Option 3 is the **correct **answer.