Turing Machine Basics and Design: Step-by-Step Worked Example for GATE

An infinite tape is the easy part of a Turing machine; the harder skill is turning a language condition into transitions and executing each move accurately. A six-state deterministic machine decides L = {0^n1^n | n >= 1} by pairing 0s and 1s, and its run on 0011 takes exactly 19 transitions, including every left-return move. Turing Machines in Theory of Computation: Design, Worked Trace and Decidability connects the same construction to recognisers, deciders and equivalent machine variants.

Turing machine basics: tape, head, states and transition function

A deterministic single-tape Turing machine is written as M = (Q, Sigma, Gamma, delta, q0, blank, F).

• Q: finite state set.

• Sigma: input alphabet, excluding blank.

• Gamma: tape alphabet, including Sigma, blank, and working markers.

• delta: transition function.

• q0: start state; blank: blank symbol; F: accepting states.

For our machine, Sigma = {0,1} and Gamma = {0,1,X,Y,blank}. The start state is q0, the accepting state is q_accept, and the rejecting state is q_reject. Markers X and Y mean a 0 and a 1 have been paired. They cannot occur in the original input.

Read each rule in read, write, move, state order. For example, delta(q0,0) = (q1,X,R) says: read 0, write X, move right, and enter q1, all in one transition.

A DFA has only finite-state memory. A PDA adds a stack, while a TM can revisit and rewrite tape cells. That ability to mark a symbol and return to it makes the pairing invariant possible.

Configurations: read a computation one move at a time

A configuration places the state immediately before the cell under the head. Thus blank q0 0 0 1 1 blank puts the head on the first 0. In blank X 0 q1 1 1 blank, it is on the first 1 after X0.

The input and tape contents are different ideas. The problem instance remains 0011 even when the tape changes to X0Y1 and then XXYY.

For every step, ask: which symbol is under the head, which rule matches the state-symbol pair, and what are the new symbol, head position, and state? Do not jump by intuition.

Design a decider for L = {0^n1^n | n >= 1}

The invariant drives the design. Each round marks the leftmost unmarked 0 as X, uses q1 to find and mark a matching 1 as Y, then uses q2 to return left. When no 0 remains, q3 checks that only Ys remain.

Each table action has the form (symbol written, move, next state). A Reject entry abbreviates a transition to q_reject; its head movement is irrelevant because q_reject halts.

Both halting states have no outgoing rules. The empty string is rejected in q0 because the language requires n >= 1. The input 00111 also rejects because one 1 remains unmatched after two rounds.

Fully worked tape trace for input 0011

The initial configuration is row 0. Every numbered row after it is the result of exactly one table application, so all 19 transitions remain visible.

0   blank q0 0 0 1 1 blank
1   blank X q1 0 1 1 blank
2   blank X 0 q1 1 1 blank
3   blank X q2 0 Y 1 blank
4   blank q2 X 0 Y 1 blank
5   q2 blank X 0 Y 1 blank
6   blank q0 X 0 Y 1 blank
7   blank X q0 0 Y 1 blank
8   blank X X q1 Y 1 blank
9   blank X X Y q1 1 blank
10  blank X X q2 Y Y blank
11  blank X q2 X Y Y blank
12  blank q2 X X Y Y blank
13  q2 blank X X Y Y blank
14  blank q0 X X Y Y blank
15  blank X q0 X Y Y blank
16  blank X X q0 Y Y blank
17  blank X X Y q3 Y blank
18  blank X X Y Y q3 blank
19  blank X X Y Y blank q_accept blank

Rows 1-6 complete round one. Rows 7-14 complete round two, including four leftward return moves. Rows 15-19 perform the final scan and enter q_accept. The full run is therefore 6 + 8 + 5 = 19 transitions.

There are only four marker writes, two Xs and two Ys. Counting rewrites instead of transitions would therefore give the wrong answer.

For 00111, two rounds produce XXYY1. After q0 reaches the first Y, q3 crosses the remaining Y, reads the extra 1, and rejects. Matching a prefix is not enough.

Why the design is correct and why it halts

If the machine accepts, every X has a later paired Y, and q3 found no unmarked symbol. The input therefore has all its 0s before an equal number of 1s, so it is in 0^n1^n.

If the input is 0^n1^n with n >= 1, every round finds one 0 and one later 1. After n rounds, q3 scans only Ys, reaches blank, and accepts.

For termination, each completed round permanently changes one 0 to X. The input is finite, and every sweep reaches a symbol, marker, or blank. It halts on every input, so it is a decider. Continue with Turing Machines and Decidability for the broader distinction.

Common TM design and tracing traps

• If q1 does not skip old Ys, the second matching round breaks.

• If the machine accepts as soon as q0 sees the first Y, it accepts a matched prefix and may miss extra symbols.

• Omitting the q3 scan can wrongly accept 00111.

• Accepting blank in q0 wrongly includes the empty string.

• Failing to reject a later 0 can wrongly accept 0101; here q3 finds that unmarked 0 and rejects.

• Sigma does not contain X, Y, or blank. Blank is a tape symbol, not a missing diagram label.

• The state marker identifies the scanned cell. One transition performs the read, write, move, and state change together.

How exam questions test TM basics and design

Typical tasks are executing a table, filling a transition, identifying the language, finding an input that rejects or loops, and deciding whether every computation halts.

Quick checks: after blank X 0 q1 1 1 blank comes blank X q2 0 Y 1 blank; 00111 rejects; 0101 rejects on an unmarked 0; and 0011 takes 19 transitions.

KnowledgeGate currently has about 50 practice questions on TM Basics & Design. Use them to practise transition-table and trace formats rather than assuming a fixed topic weightage or future-paper pattern.

Short version and next step

• Define the input alphabet, tape alphabet, and markers.

• Write the phase invariant before writing transitions.

• Trace without skipping head moves.

• Prove both correctness and halting.

For this machine, 0011 becomes XXYY and accepts after 19 transitions, while 00111 leaves one unmatched 1 and rejects. Use GATE Guidance by Sanchit Sir for structured GATE CS study, take the Zero to Hero complete CS course for a broader fundamentals route, or browse the GATE CS exam category to choose your next topic.