You may be comfortable following DFA and PDA diagrams, yet find a Turing machine intimidating because it can overwrite a symbol and revisit the same cell. That one extra freedom, a read-write head moving in both directions, is enough to decide L = {0^n1^n | n >= 1}, which no finite automaton can do. Six states are sufficient: the machine pairs each 0 with a matching 1, rewrites the pair as X and Y, and on input 0011 halts in q_accept with the tape reading XXYY. The same machine also settles the distinction GATE keeps asking about, because recognising a language and deciding it are not the same claim, and only a halting argument separates them.
Turing machine model: tape, head, states and the seven-tuple
A deterministic single-tape Turing machine is M = (Q, Sigma, Gamma, delta, q0, q_accept, q_reject). Here Q is the finite state set; input alphabet Sigma excludes blank; tape alphabet Gamma contains Sigma, markers and blank; and delta returns a next state, symbol to write and direction. The distinct accept and reject states halt.
On tape [..., blank, 0, 1, 1, blank, ...], let q0 scan the first 0. Applying delta(q0,0) = (q1,X,R) produces visible tape X11, with state q1 scanning the first 1. Here {0,1} is the input alphabet and {0,1,X,Y,blank} is the tape alphabet.
Model | Memory and movement |
|---|---|
DFA | Finite control, read-only input, one-way scan |
PDA | Finite control plus one unbounded stack |
Turing machine | Read-write tape, with movement in both directions |
Within GATE CS Exam Preparation, theory of computation is the section that fixes what a machine can compute at all, and the Turing machine is the model the rest of that section builds towards.
Turing machine transitions and configurations
A configuration u q av means the tape contains uav, the state is q, and the head scans a. Therefore q0 0011 becomes X q1 011 in one move. We write this as q0 0011 ⊢ X q1 011; ⊢* means zero or more moves.
A computation may enter q_accept, enter q_reject, or continue forever. For the machine below, each unlisted non-halting transition goes to q_reject. It therefore never becomes stuck by accident.
Design states only after writing an invariant. Choose separate markers, decide how the head returns to a known boundary, and define what proves full consumption. Our invariant is: every completed pass changes exactly one left-side 0 to X and one matching right-side 1 to Y.
Turing machine design for L = {0^n1^n | n >= 1}
Use Q = {q0,q1,q2,q3,q_accept,q_reject}, Sigma = {0,1} and Gamma = {0,1,X,Y,blank}. State q0 selects a leftmost unmarked 0; q1 finds its unmarked 1; q2 returns to the latest X; and q3 verifies the remaining Ys.
q0:X/X,R,q0;0/X,R,q1;Y/Y,R,q3; on1or blank, reject.q1: on0orY, preserve and move right;1/Y,L,q2; onXor blank, reject.q2: on0orY, preserve and move left;X/X,R,q0; on1or blank, reject.q3:Y/Y,R,q3;blank/blank,R,q_accept; on0,1orX, reject.
Both halting states have no outgoing transitions. An unmatched 0 makes q1 reject at blank; an unmatched or misplaced 1 is caught by q0 or q3. Only equal, ordered pairs can become X and Y before the final blank.
Turing machine worked trace for 0011
Keep the state immediately before the scanned cell:
q0 0011 ⊢ X q1 011 ⊢ X0 q1 11 ⊢ X q2 0Y1 ⊢ q2 X0Y1 ⊢ X q0 0Y1 ⊢ XX q1 Y1 ⊢ XXY q1 1 ⊢ XX q2 YY ⊢ X q2 XYY ⊢ XX q0 YY ⊢ XXY q3 Y ⊢ XXYY q3 blank ⊢ XXYY blank q_accept blank
State q1 turns left after marking a match; q2 turns right at X to start the next pass. Finally, q3 reads the first blank and moves onto the second as q_accept.
For 0101, the first pass produces XY01. After the return, q0 sees Y and enters q3; q3 then sees the unmatched 0 and rejects. Equal counts alone are insufficient because block order also matters.
For input length 2n, each of the n pairings can scan across O(n) cells and return. This construction therefore uses O(n^2) time and O(n) visited tape cells. That bound describes this one-tape design, not every machine or algorithm for the language.
Turing machine recognisers, deciders and equivalent variants
A recogniser accepts every member but may reject or loop on a non-member. A decider halts on every input. This machine accepts 0011 and rejects 001 when q1 reaches blank. Its sweeps are finite, each pairing adds an X, and every other case rejects, so it is a decider.
Decidable, or recursive, languages form a proper subset of Turing-recognisable, or recursively enumerable, languages. The standard separating example is A_TM = {<M,w> | M accepts w}, which is recognisable but undecidable. Undecidability then spreads by reduction rather than by fresh proofs, and Rice's Theorem for GATE: Two-Part Undecidability Test pushes that to its limit: every non-trivial property of the language a machine recognises is undecidable as well.
Multi-tape and nondeterministic machines, enumerators and universal Turing machines have the standard model's computability power, although simulations may change efficiency. The Church-Turing thesis connects effective computation with Turing computability. It is a thesis, not a formal theorem.
Turing machines in GATE and interview questions
IIT Guwahati's GATE 2026 exam-papers and syllabus archive lists Turing machines and undecidability under Section 6, Theory of Computation, in the CS syllabus. The CS2 session paper from that cycle asked which statement is equivalent to the assertion that a Turing machine M decides L. The correct reading is the two-sided one: M accepts every string in L and rejects every string outside it, which is the halting requirement written out as two cases rather than assumed.
Question shape | What to do |
|---|---|
Execute a trace | Show state, scanned cell, write and move |
Infer a language | Identify the invariant |
Repair a machine | Find the missing transition or halt |
Recognise versus decide | Prove whether every path halts |
Classify a problem | Apply the right decidability or reduction fact |
Interview designs often include 0^n1^n, unary increment and palindrome checking, and each is built the same way: choose a marker, define one pass, prove the pass makes progress. If the state-machine reflexes are shaky, Finite Automata MCQs: 10 Solved DFA and NFA (GATE) rebuilds them, and Context-Free Grammar MCQs: 11 Solved GATE Questions covers the stack model that sits one step below the tape.
Turing machine mistakes that break a correct answer
Mistake | Consequence | Correction |
|---|---|---|
Confusing | Markers appear illegally in the input alphabet | Keep blank and work markers only in |
Moving before writing | The trace no longer follows one atomic transition | Read, write, move and change state as one step |
Accepting after all | A stray | Scan the remaining |
Calling a recogniser a decider | Termination is unproved | Show every input reaches a halt |
Calling a problem undecidable | It sounds as if no instance can be answered | State that no algorithm decides every instance |
After the first pairing of 0011, the tape is X0Y1, not X01Y. After the second it is XXYY, with q0 reading the first Y and q3 the second before blank. If either invariant fails, return to the first bad transition.
Every non-halting state-symbol pair needs an outcome, even rejection, and every loop needs progress. Here each outer pass adds one X, so finite input cannot produce infinitely many pairing passes.
Turing machines: the short version and next step
Write the seven-tuple.
Translate every edge as read, write and move.
State the tape invariant.
Keep the head position visible in a trace.
Separate accept, reject and loop.
Prove halting before saying decider.
The worked result is simple: 0011 becomes XXYY and accepts, while 0101 fails the final order check. GATE Guidance by Sanchit Sir is the structured next step if you want Turing machines sequenced with automata, grammars and undecidability. If you only need this concept, redraw the six-state machine from its invariant and reproduce the 0011 trace without looking.
