Turing Machine: RE, REC and Undecidability GATE 2013 Question #10032 with Solution

GATE 2013 · session-1

Theory of ComputationTuring Machine: RE, REC and UndecidabilityeasyMCQ1 mark

Which of the following statements about Turing machines and languages 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.

A1 and 4 onlyB1 and 3 onlyC2 onlyD3 only

Save your progress

Related Theory of Computation PYQs

GATE 2013

Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = ϕ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L…

GATE 2013

Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent determin…

GATE 2013

Which of the following languages is NOT regular?

GATE 2013

Which of the following statements is FALSE?

GATE 2013

Consider the following deterministic finite automaton (DFA) over the alphabet {0, 1} with states {q0, q1, q2}, where q0 is the sta…

GATE 2013

The language L = {a^n b^m c^m d^n | n, m >= 1} is:

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.

Related Theory of Computation PYQs

Turn practice into measurable progress