A finite automaton has only its states for memory. A pushdown automaton adds a stack, but it can only look at the top, and once it pops something, that information is gone. Neither can recognise a language as simple as {anbncn}, while you can check it easily with a pencil: tick off one a, one b and one c, go back, and repeat.
In 1936 Alan Turing asked exactly this question: what can a person with a pencil, an eraser and an unlimited supply of paper compute by following fixed rules? His answer was the Turing machine: a finite control (the rules) plus an infinite tape that it can read, write, and move over in both directions. This simple machine turns out to be as powerful as any computer that has ever been built.
A Turing machine (TM) is a finite-state control attached to an infinite tape divided into cells. In one move, depending on its current state and the symbol under its head, it writes a symbol in that cell, moves the head one cell left or right, and changes state. Unlike a DFA or PDA, it can revisit and overwrite its input as often as it likes.
In this chapter we define TMs formally, learn how to describe their computations with instantaneous descriptions, and design machines that accept languages and compute functions. Every machine here was run on a simulator: the acceptors were tested against their language definitions on all strings up to length 9 to 12, and the transducers on dozens of inputs.
The Model
... | B | B | a | a | b | b | B | B | ... infinite tape
▲
│ read / write head (moves L or R)
┌──────┴──────┐
│ finite │
│ control q │
└─────────────┘The tape is divided into cells and is infinite (in the standard model, infinite in both directions; the next chapter shows the choice does not matter). Initially it holds the input string w, and every other cell holds the special blank symbol B.
The head starts on the leftmost input symbol.
In each move the TM, based on (current state, scanned symbol): (1) writes a tape symbol in the scanned cell (possibly the same one), (2) moves the head one cell Left or Right, (3) enters a new state.
The three differences from earlier machines are what make it powerful: it can write, it can move left (re-read), and its storage is unbounded and randomly reachable by walking, not restricted to the top of a stack.
Formal Definition
Following Hopcroft, Motwani and Ullman, a Turing machine is a 7-tuple
M = (Q, Σ, Γ, δ, q0, B, F)Component | Meaning |
|---|---|
Q | finite set of states |
Σ | input alphabet |
Γ | tape alphabet, with Σ ⊂ Γ (Γ also contains B and any marker symbols) |
δ | transition function, δ : Q × Γ → Q × Γ × {L, R}, a partial function (may be undefined) |
q0 | start state |
B | blank symbol, B ∈ Γ but B ∉ Σ |
F | set of final (accepting) states, F ⊆ Q |
δ(q, X) = (p, Y, D) means: in state q scanning X, write Y, move in direction D, go to state p. Since δ gives at most one move, this basic TM is deterministic.
Why B ∉ Σ? The input must not contain blanks, so the machine can find the end of its input by looking for the first blank.
Other textbooks use small variations: Sipser has one accept state and one reject state, both halting, and a tape infinite only to the right. These are all equivalent in power, so in an exam just use the convention your syllabus uses and state it.
Instantaneous Descriptions and Moves
An instantaneous description (ID) is a snapshot of the whole computation. We write it as
X1 X2 ... X(i-1) q Xi X(i+1) ... Xnmeaning: the non-blank part of the tape is X1...Xn, the machine is in state q, and the head is scanning Xi (the symbol just to the right of q). One move is written ⊢, and zero or more moves ⊢*.
If δ(q, Xi) = (p, Y, R): X1...X(i-1) q Xi...Xn ⊢ X1...X(i-1) Y p X(i+1)...Xn
If δ(q, Xi) = (p, Y, L): X1...X(i-1) q Xi...Xn ⊢ X1...X(i-2) p X(i-1) Y X(i+1)...XnAcceptance and halting
The TM halts when δ is undefined for the current state and symbol. We assume no moves are defined out of final states, so the TM halts as soon as it enters a final state.
The language accepted is
L(M) = { w ∈ Σ* : q0 w ⊢* α p β for some final state p ∈ F }On an input w, exactly one of three things happens:
Outcome | Meaning |
|---|---|
Halt in a final state | w is accepted |
Halt in a non-final state | w is rejected |
Run forever | w is not accepted, but we can never be sure by watching |
That third possibility is new: a DFA always stops after reading its input. Languages accepted by some TM are called recursively enumerable; those accepted by a TM that halts on every input are recursive. These classes are studied in Decidability: Recursive & Recursively Enumerable Languages.
Example 1: A TM for {anbn : n ≥ 1}
A PDA can do this language, but let us solve it the TM way, since the same idea scales to harder languages.
Idea (zig-zag matching): replace the leftmost a by X, run right to the leftmost b and replace it by Y, run back left to the X, and repeat. When no a is left, check that only Ys (no unmatched b) remain.
State | Role |
|---|---|
q0 | at the leftmost unmatched a (or at the first Y if all a's are used) |
q1 | just marked an a; moving right to find a b |
q2 | just marked a b; moving left back to the last X |
q3 | all a's used; checking the rest contains only Ys |
q4 | accept (final) |
Transition table (blank entries mean "no move", so the TM halts and, since the state is not final, rejects):
State | a | b | X | Y | B |
|---|---|---|---|---|---|
→ q0 | (q1, X, R) | - | - | (q3, Y, R) | - |
q1 | (q1, a, R) | (q2, Y, L) | - | (q1, Y, R) | - |
q2 | (q2, a, L) | - | (q0, X, R) | (q2, Y, L) | - |
q3 | - | - | - | (q3, Y, R) | (q4, B, R) |
* q4 | - | - | - | - | - |
The same machine as a list of arrows (each label is read / write, move):
q0 ── a/X,R ──► q1 q1 ── a/a,R or Y/Y,R ──► q1 (skip right)
q1 ── b/Y,L ──► q2 q2 ── a/a,L or Y/Y,L ──► q2 (skip left)
q2 ── X/X,R ──► q0 q0 ── Y/Y,R ──► q3 (no a left)
q3 ── Y/Y,R ──► q3 q3 ── B/B,R ──► q4 (accept)
mark a find b, mark Y back to X
q0 ───────────► q1 ─────────────────► q2 ───────────────┐
▲ │
└────────────────────────────────────────────────────────┘
│ all a's marked
▼
q3 ── only Ys, then blank ──► q4 (accept)Trace on aabb (accepted)
q0 aabb mark first a
⊢ X q1 abb
⊢ Xa q1 bb found first b
⊢ X q2 aYb mark it Y, turn back
⊢ q2 XaYb
⊢ X q0 aYb back at the leftmost unmatched a
⊢ XX q1 Yb
⊢ XXY q1 b
⊢ XX q2 YY
⊢ X q2 XYY
⊢ XX q0 YY no a left: check the rest
⊢ XXY q3 Y
⊢ XXYY q3 B
⊢ XXYYB q4 ACCEPT (13 moves)Why the bad strings are rejected
Input | Where it halts | Reason |
|---|---|---|
aab | XXY q1 B | second a has no matching b: q1 meets a blank |
abb | XY q3 b | an extra b remains after all a's are used |
abab | XY q3 ab | q3 finds an a after the Ys: wrong order |
ba | q0 ba | q0 has no move on b |
ε | q0 B | n ≥ 1 is required; q0 has no move on B |
This machine always halts. On anbn it makes exactly 2n2 + 2n + 1 moves (5, 13, 25, 41, ... for n = 1, 2, 3, 4), so it runs in O(n2) time because of the back-and-forth walking.
Example 2: A TM for {anbncn : n ≥ 1}
No PDA can accept this language, but the TM needs only one more marker. In each round, mark one a as X, one b as Y and one c as Z, then go back.
State | a | b | c | X | Y | Z | B |
|---|---|---|---|---|---|---|---|
→ q0 | (q1, X, R) | - | - | - | (q4, Y, R) | - | - |
q1 | (q1, a, R) | (q2, Y, R) | - | - | (q1, Y, R) | - | - |
q2 | - | (q2, b, R) | (q3, Z, L) | - | - | (q2, Z, R) | - |
q3 | (q3, a, L) | (q3, b, L) | - | (q0, X, R) | (q3, Y, L) | (q3, Z, L) | - |
q4 | - | - | - | - | (q4, Y, R) | (q4, Z, R) | (q5, B, R) |
* q5 | - | - | - | - | - | - | - |
q1: after marking an a, skip a's and Ys to the first unmarked b.
q2: after marking a b, skip b's and Zs to the first unmarked c, mark it Z.
q3: walk left over everything until the rightmost X, then step right into q0.
q4: when q0 sees Y, every a is used; accept only if the rest is Ys then Zs then blank.
The order check is built in: q1 refuses a c before finding a b, q2 refuses an a, and q4 refuses any unmarked letter.
q0 aabbcc
⊢ X q1 abbcc
⊢ Xa q1 bbcc
⊢ XaY q2 bcc
⊢ XaYb q2 cc
⊢ XaY q3 bZc
⊢ Xa q3 YbZc
⊢ X q3 aYbZc
⊢ q3 XaYbZc
⊢ X q0 aYbZc round 2
⊢ XX q1 YbZc
⊢ XXY q1 bZc
⊢ XXYY q2 Zc
⊢ XXYYZ q2 c
⊢ XXYY q3 ZZ
⊢ XXY q3 YZZ
⊢ XX q3 YYZZ
⊢ X q3 XYYZZ
⊢ XX q0 YYZZ no a left: verify
⊢ XXY q4 YZZ
⊢ XXYY q4 ZZ
⊢ XXYYZ q4 Z
⊢ XXYYZZ q4 B
⊢ XXYYZZB q5 ACCEPT (23 moves)The simulator confirmed this TM accepts exactly the strings anbncn (n ≥ 1) among all 29,524 strings over {a, b, c} of length ≤ 9.
Turing Machines That Compute Functions
A TM can also be a transducer: it starts with the input on the tape and, when it halts, whatever is left on the tape is the output. A function f is Turing-computable if some TM, started on w, always halts with f(w) on the tape.
Example 3: Unary addition
Numbers are written in unary: m is 1m. The input is 1m01n and the output should be 1m+n.
Idea: change the separator 0 into a 1 (now there are m + n + 1 ones), then go to the right end and erase one 1.
State | 1 | 0 | B |
|---|---|---|---|
→ q0 | (q0, 1, R) | (q1, 1, R) | - |
q1 | (q1, 1, R) | - | (q2, B, L) |
q2 | (q3, B, L) | - | - |
* q3 | - | - | - |
q0 11011 2 + 2
⊢ 1 q0 1011
⊢ 11 q0 011
⊢ 111 q1 11 the 0 became 1
⊢ 1111 q1 1
⊢ 11111 q1 B reached the end
⊢ 1111 q2 1
⊢ 111 q3 1 last 1 erased; tape = 1111 = 4Checked for all m, n from 0 to 6, including 0 + 0 (input "0", output empty tape).
Example 4: Binary increment
Input: a binary number w (most significant bit first). Output: w + 1 in binary.
Idea: walk to the rightmost bit, then add 1 as you would by hand: a 1 plus carry becomes 0 and the carry moves left; the first 0 (or a blank, if the number was all 1s) becomes 1 and we stop.
State | 0 | 1 | B |
|---|---|---|---|
→ q0 | (q0, 0, R) | (q0, 1, R) | (q1, B, L) |
q1 | (q2, 1, L) | (q1, 0, L) | (q2, 1, L) |
* q2 | - | - | - |
1011 + 1: 111 + 1 (carry out of the top):
q0 1011 q0 111
⊢ 1 q0 011 ⊢ 1 q0 11
⊢ 10 q0 11 ⊢ 11 q0 1
⊢ 101 q0 1 ⊢ 111 q0 B
⊢ 1011 q0 B ⊢ 11 q1 1
⊢ 101 q1 1 on last bit ⊢ 1 q1 10
⊢ 10 q1 10 1 → 0, carry ⊢ q1 100
⊢ 1 q1 000 1 → 0, carry ⊢ q1 B000 carry reaches the blank
⊢ q2 1100 0 → 1, stop ⊢ q2 B1000 B → 1, stop: 1000Checked on every binary string of length 1 to 10.
Techniques for Designing TMs
Real TM programs are built from a few standard tricks:
Marking symbols. Overwrite a symbol with a marker (X, Y, Z) to remember it has been processed, as in Examples 1 and 2.
Storage in the state. To remember a finite amount of data (for example, the first symbol of the input), use states such as qa and qb: "I am moving right and the symbol I picked up was a". The number of states grows, but stays finite. This is how a TM checks palindromes: pick up the first symbol, remember it in the state, run to the last symbol and compare.
Subroutines. A group of states that does one job (for example "copy a block" or "go to the left end") and then returns to a chosen state, like a function call. Multiplication can be built from repeated copying.
Multiple tracks and multiple tapes. Treating each cell as a tuple of symbols, or giving the machine several tapes. These are covered in Variants of Turing Machines, where we will see they add convenience but not power.
TM vs FA vs PDA
Feature | DFA / NFA | PDA | Turing machine |
|---|---|---|---|
Memory | finite states only | states + one stack | states + infinite tape |
Access to memory | - | top of stack only (LIFO) | any cell, by moving the head |
Can re-read input? | No (one pass, left to right) | No | Yes, input is on the tape |
Can write? | No | Only on the stack | Yes, anywhere |
Always halts? | Yes | Can be made to | No, may loop forever |
Determinism | DFA = NFA in power | DPDA weaker than NPDA | DTM = NTM in power |
Languages | regular | context-free | recursively enumerable |
Example it cannot do | anbn | anbncn | the halting problem |
The Church–Turing thesis claims that anything computable by an algorithm is computable by a Turing machine. It is a thesis, not a theorem, because "algorithm" is an informal idea; we discuss the evidence for it in the next chapter.
Common Mistakes
Treating "not accepted" as "rejected". A TM can fail to accept by looping forever, which is different from halting in a non-final state.
Putting B in Σ. The blank is a tape symbol, never an input symbol.
Writing the ID with the state after the scanned symbol. In "XX q1 Yb" the head is on Y, the symbol right after the state.
Forgetting the move in a transition. Every TM move writes a symbol and moves (L or R) in the standard model. "Stay" moves exist only in a variant.
Forgetting to check order. A machine that only counts matching a's and b's will wrongly accept abab. In Example 1 it is state q3 that rejects leftovers.
Saying a TM is just a "PDA with two-way input". The key is the ability to write unboundedly anywhere on the tape.
Practice and GATE-Style Questions
Q1. How many moves does the TM of Example 1 make on a3b3? What is its time complexity?
The move count is 2n2 + 2n + 1 = 18 + 6 + 1 = 25 moves (confirmed by simulation). Each of the n rounds walks across the string twice, so the time is O(n2).
Q2. In Example 1, what is the final ID on input aab, and is aab accepted?
The machine marks both a's and the b, giving XXY, and in the second round q1 runs off the end: the final ID is XXY q1 B. δ(q1, B) is undefined and q1 is not final, so aab is rejected.
Q3. A TM over Σ = {a} has only three moves: δ(q0, a) = (q0, a, R), δ(q0, B) = (q1, B, L), δ(q1, a) = (q0, a, R), and F = {q2}. What happens on input aa? On input ε?
aa: q0 walks right to the blank, steps back onto the last a in q1, steps right again in q0 onto the blank, back again, and so on. It loops forever, so aa is not accepted, but the machine never halts to say so.
ε: q0 sees B, moves left into q1 and again sees B. δ(q1, B) is undefined, so the machine halts after one move in the non-final state q1: ε is rejected. (q2 is unreachable, so this TM accepts the empty language, but it rejects some inputs and loops on others.)
Q4. Design idea: give a TM for the language of even-length palindromes over {a, b}.
Repeat: if the scanned symbol is blank, accept (everything matched). Otherwise read the leftmost symbol, replace it by B, and remember it in the state (qa or qb). Run right to the first blank, step left onto the last symbol. If it matches the remembered one, replace it by B, run back left to the blank, step right and repeat; if it does not match (or there is none), reject. Time O(n2). This uses the "storage in the state" technique.
Q5. Which of these does a TM have that a PDA does not: (a) infinite memory (b) ability to read memory other than the most recently written item (c) nondeterminism?
(b). A PDA also has unbounded memory (its stack) and can be nondeterministic. What a TM adds is free access: it can walk to any cell and read or rewrite it without destroying what lies on the way.
Q6. Interview: a TM on input w has been running for a billion steps. Can you conclude w ∉ L(M)?
No. It may accept at step 109 + 1. In general no algorithm can decide whether a TM will eventually halt; this is the halting problem, studied in Halting Problem & Undecidability.
Summary
A TM = finite control + infinite tape + read/write head that moves L or R. Formally M = (Q, Σ, Γ, δ, q0, B, F).
One move: write a symbol, move one cell, change state. An ID like XX q1 Yb records the tape, state and head position.
On an input a TM accepts (halts in F), rejects (halts elsewhere) or loops forever.
Marking with X/Y/Z and zig-zagging lets a TM compare counts: anbn in O(n2) moves, and anbncn, which no PDA can accept.
TMs can compute functions: unary addition, binary increment, and (by subroutines) anything a program can compute.
TMs accept the recursively enumerable languages, the largest class in the Chomsky hierarchy.
A Turing machine is a finite rulebook plus an endless notebook it can read, erase and rewrite anywhere. That small addition makes it a model of every computer, and also introduces the possibility of never halting.