Turing Machine questions mix three skills that students often blur together: recalling the formal model, executing one transition correctly, and deciding what a whole computation accepts. Decide each option before you read the explanation, never by recognising the wording, and for every trace question write down the active state, the scanned symbol and the head move. Every question below is a previous-year question from Bihar STET, BPSC, UGC NET, ISRO or GATE, and the Turing machine subtopic they are drawn from holds about 50 in all inside GATE CS Exam Preparation.
TM notation and trace method
A Turing machine has finite control, an unbounded cell-divided tape, and a read/write head. Parts: input alphabet Σ, tape alphabet Γ containing blank B, a start state, and accept/reject outcomes. δ(q, x) = (p, y, D) means: in q, read x, write y, move one cell in D ∈ {L, R}, and enter p.
Calibrate the method with δ(q0, 0) = (q0, X, R) and δ(q0, B) = (q_accept, B, R) on input 000:
Before | Applied rule | After |
|---|---|---|
| Replace |
|
| Replace |
|
| Replace |
|
| Keep |
|
Each X is written tape content, and q0 marks the head position. Acceptance occurs only when q0 scans B. The same notation carries the design proofs in Turing Machines in Theory of Computation: Design, Worked Trace and Decidability.
TM MCQs 1-3: representation and one step
Q1
Turing machine can be represented using: (Bihar STET 2025)
A. Transition table
B. Transition diagram
C. Instantaneous description
D. All of these
Correct answer: D. All of these.
A transition table and a transition diagram both encode the rule set, the same information written two ways. An instantaneous description encodes something else: state, tape contents and head position at one instant. All three are standard notations for a machine, so D is the answer.
Q2
Which of the following is NOT a component of a Turing machine? (BPSC PGT Tier-3, 2024)
A. Input tape
B. Output tape
C. Control unit
D. More than one of the above
E. None of the above
Correct answer: B. Output tape.
Single-tape TMs have one input/work/output tape, finite control, and a read/write head. No dedicated output tape, so B alone is absent.
Q3
Arrange the following stages of a Turing Machine (TM) operation in the correct order as they occur during computation.
(A) Writing a symbol on the tape
(B) Moving the tape head left to right
(C) Reading a symbol from the tape
(D) Transitioning to a new state based on the current state and symbol read
(E) Halting and accepting or rejecting the input
Choose the correct answer from the options given below: (UGC NET Paper 2, August 2024)
A. (C), (A), (B), (D), (E)
B. (C), (B), (A), (D), (E)
C. (C), (D), (A), (B), (E)
D. (C), (D), (B), (A), (E)
Correct answer: C. (C), (D), (A), (B), (E).
Read the scanned symbol (C), look up the rule and take the new state (D), write the replacement symbol (A), then move the head one cell (B), with E ending the run. Writing or moving before the rule is consulted reverses cause and effect.
TM MCQs 4-6: halting and deciding
Q4
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input? (ISRO 2014)
A. it may halt and accept the input
B. it may halt by changing the input
C. it may halt and reject the input
D. it may never halt
Correct answer: B. it may halt by changing the input.
A run has exactly three possible outcomes: halt and accept, halt and reject, or never halt. Rewriting cells happens on almost every step, but that is an action inside the run, not a way it ends. B dresses an action up as an outcome, so B is false.
Q5
Which statement is equivalent to:
Turing machine M decides language L ⊆ {0,1}* (GATE 2026, Set 2)
A. Turing machine M halts on all input strings in {0,1}*
B. Turing machine M accepts all input strings in L
C. Turing machine M rejects all input strings in {0,1}* − L
D. Turing machine M accepts all input strings in L and rejects all input strings in {0,1}* − L
Correct answer: D. Turing machine M accepts all input strings in L and rejects all input strings in {0,1}* − L.
A decider must halt on every input and give the right verdict on every input. A promises only the halting half, so a machine that rejects everything satisfies it. B names only the strings inside L, C only those outside it. D carries both halves, which is what deciding L means.
Q6
A language L ⊆ Σ* is recursive if there exists some Turing machine M. Which of the following conditions is satisfied for any string ω? (UGC NET Paper 2, June 2019)
A. If ω ∈ L, then M accepts ω and M will not halt
B. If ω ∉ L, then M accepts ω and M will halt by reaching a final state
C. If ω ∉ L, then M halts without reaching an accepting state
D. If ω ∈ L, then M halts without reaching an accepting state
Correct answer: C. If ω ∉ L, then M halts without reaching an accepting state.
A language is recursive when some machine halts on every string, accepting those in L and rejecting the rest. C states exactly the rejecting half. A contradicts itself by accepting and never halting at once, while B and D swap the membership conditions around.
TM MCQs 7-9: language hierarchy
Q7
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true ? (GATE 2003)
A. L is necessarily finite
B. L is regular but not necessarily finite
C. L is context free but not necessarily regular
D. L is recursive but not necessarily context free
Correct answer: D. L is recursive but not necessarily context free.
Lexicographic order gives every string finitely many predecessors, so to test w you enumerate until w appears or a later string does. Either branch stops, which makes L recursive. That order says nothing about a grammar, so D is the only option carrying both halves.
Q8
Consider the following language families:
L₁ ≡ the context-free languages
L₂ ≡ the context-sensitive languages
L₃ ≡ the recursively enumerable languages
L₄ ≡ the recursive languages
Which one of the following options is correct? (UGC NET Paper 2, December 2019)
A. L₁ ⊆ L₂ ⊆ L₃ ⊆ L₄
B. L₂ ⊆ L₁ ⊆ L₃ ⊆ L₄
C. L₁ ⊆ L₂ ⊆ L₄ ⊆ L₃
D. L₂ ⊆ L₁ ⊆ L₄ ⊆ L₃
Correct answer: C. L₁ ⊆ L₂ ⊆ L₄ ⊆ L₃.
Every context-free language is context-sensitive, every context-sensitive language has a decider that always halts, and every decider is also a recogniser. That chain gives L₁ ⊆ L₂ ⊆ L₄ ⊆ L₃. The trap is any option placing L₃ before L₄.
Q9
Let L = {aᵖ | p is a prime}. Then which of the following is true? (ISRO 2017)
A. It is not accepted by a Turing Machine
B. It is regular but not context free
C. It is context free but not regular
D. It is neither regular nor context free, but accepted by a Turing Machine
Correct answer: D. It is neither regular nor context free, but accepted by a Turing Machine.
A Turing machine can count the a symbols and test that count for primality, so A is out. Gaps between primes grow without bound, so no finite automaton tracks them and L is not regular. Every unary context-free language is regular, so L is not context free either.
TM MCQs 10-12: traces and Church's thesis
Q10
Given a Turing machine M = ({q₀, q₁, q₂, q₃}, {a, b}, {a, b, B}, δ, B, {q₃}) where δ is a transition function defined as:
δ(q₀, a) = (q₁, a, R)
δ(q₁, b) = (q₂, b, R)
δ(q₂, a) = (q₂, a, R)
δ(q₂, b) = (q₃, b, R)
The language L(M) accepted by the Turing machine is given as: (UGC NET Paper 2, June 2016)
A. aa*b
B. abab
C. aba*b
D. aba*
Correct answer: C. aba*b.
Trace abaab: q0 abaab → a q1 baab → ab q2 aab → aba q2 ab → abaa q2 b → abaab q3 B. One a, one b, then q2 loops over any number of a symbols until a closing b reaches q3: aba*b.
Q11
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table
State | 0 | 1 | B |
|---|---|---|---|
q0 | q1, 1, R | q1, 1, R | Halt |
q1 | q1, 1, R | q0, 1, L | q0, B, L |
The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ? (GATE 2003)
A. M does not halt on any string in (0 + 1)+
B. M does not halt on any string in (00 + 1)*
C. M halts on all string ending in a 0
D. M halts on all string ending in a 1
Correct answer: A. M does not halt on any string in (0 + 1)+.
On 1, q0 1 B → 1 q1 B → q0 1 B, repeating. A 0 in q0 becomes 1, then cycles. Only empty input halts; every non-empty binary string loops.
Q12
Church's Thesis supports: (Bihar STET 2025)
A. Both "TM is a general-purpose computer" and "TM is an algorithm and vice versa" are correct
B. A Turing machine as an algorithm and an algorithm as a Turing machine
C. A Turing machine as a general-purpose computer system
D. None of them is correct
Correct answer: B. A Turing machine as an algorithm and an algorithm as a Turing machine.
Church's Thesis identifies the informal notion of an effective algorithm with what a Turing machine computes, in both directions. B is the only option stating that two-way identification. One side of it stays informal, so the thesis is accepted on evidence rather than proved.
Six TM traps
Trap | Questions |
|---|---|
Rule set versus configuration | Q1 |
One tape versus dedicated output tape | Q2 |
Read, choose, write, move | Q3 |
Accept/reject/loop | Q4-Q6 |
Recursive versus RE | Q7-Q9 |
Local transition versus language claim | Q10-Q12 |
Timed routine: box state, underline scanned symbol, write (next state, symbol, direction), change one cell, move one square. For classes, first write CFL ⊆ CSL ⊆ Recursive ⊆ RE.
Try Finite Automata MCQs: 10 Solved DFA and NFA (GATE) for easier machine-model practice, then Context-Free Grammar MCQs: 11 Solved GATE Questions for the rung below Turing machines. Tape tracing sits one level above both of them.
TM basics: next practice
Retest Questions 3, 5, 8, 10 and 11 without looking. Together they cover one transition, decider semantics, the language ladder, language extraction and a non-halting loop. Write full configurations on paper for Q10 and Q11 rather than simulating them mentally. For a sequenced Theory of Computation route that places Turing machines after automata, regular languages and pushdown automata, continue with GATE Guidance by Sanchit Sir.
The short version: read one transition locally, trace the machine mechanically, and only then make a global claim about its language or halting behaviour.
