Turing Machines

A Turing machine is a theoretical model of computation devised by Alan Turing in 1936. Its design is almost provocatively simple — an unbounded tape, a head that reads and writes one cell at a time, a finite set of states, and a fixed table of rules — yet that minimal apparatus turns out to be as powerful as any computer that has ever been built or ever could be built. The Turing machine sits at the very top of the Chomsky hierarchy: it recognises strictly more languages than a pushdown automaton (which in turn beats a finite state machine), and it defines the precise boundary of what is computable. Studying it is not an exercise in nostalgia for 1930s mathematics; it is the way computer scientists make rigorous the otherwise vague idea of "an algorithm", and it is the foundation on which the next two lessons — the halting problem and the limits of computation — are built.

---

Spec Mapping

This lesson addresses the Theory of Computation strand of the AQA A-Level Computer Science specification (7517), in the area dealing with a model of computation (around section 4.4.5). You are expected to understand the structure of a Turing machine — its tape, read/write head, finite set of states, and transition rules / transition function; to read a transition table and interpret a machine's configurations as it runs; to follow or construct a worked Turing machine that performs a concrete task (such as incrementing a binary number or recognising a simple language); to understand the idea and significance of a Universal Turing Machine; and to appreciate why the Turing machine matters — that it captures the notion of "effectively computable" and so marks the limit of what any computing device can do. The descriptions below are in the standard automata-theory vocabulary; you should learn the concepts rather than any verbatim phrasing.

---

The Structure of a Turing Machine

A Turing machine has four parts, and each one is a deliberate, minimal answer to the question "what is the least apparatus needed to capture all of computation?"

Component	Description
Infinite tape	Divided into discrete cells, each holding one symbol from the tape alphabet. The tape is unbounded — conceptually it extends as far as needed in both directions — and it serves as both the input medium and the machine's working memory.
Read/write head	Sits over exactly one cell at a time. On each step it can read the symbol in that cell, write a (possibly different) symbol back, and then move one cell left or right.
State register	Holds the machine's current state, drawn from a finite set of states. This finite control is the only "internal" memory; everything unbounded lives on the tape.
Transition function	The machine's program: a fixed set of rules that, given the current state and the symbol under the head, dictates the symbol to write, the direction to move, and the next state to enter.

The single most important design decision is the split between the finite control (the states) and the unbounded tape. A finite state machine has only the finite control — that is exactly why it cannot count without limit. The Turing machine keeps the finite control but bolts on an unbounded read/write tape, and that one addition is the difference between recognising only the regular languages and being able to compute anything computable.

---

Formal Definition

A Turing machine is defined as a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_a, q_r)$(Q,Σ,Γ,δ,q0​,qa​,qr​):

Symbol	Meaning
$Q$Q	A finite set of states
$\Sigma$Σ	The input alphabet — the symbols that may appear on the tape at the start
$\Gamma$Γ	The tape alphabet, which includes $\Sigma$Σ together with the blank symbol $\square$□ (and any extra "working" symbols the machine uses)
$\delta$δ	The transition function: $\delta(\text{state}, \text{symbol}) \to (\text{new symbol}, \text{direction}, \text{new state})$δ(state,symbol)→(new symbol,direction,new state)
$q_0$q0​	The start state, $q_0 \in Q$q0​∈Q
$q_a$qa​	The accept (halt-and-accept) state
$q_r$qr​	The reject (halt-and-reject) state

The machine begins in state $q_0$q0​ with the input string written on the tape, the head positioned over the leftmost input symbol, and every other cell holding the blank symbol $\square$□. Two features deserve emphasis. First, $\Gamma$Γ is a superset of $\Sigma$Σ: the machine is allowed extra tape symbols (like the $X$X and $Y$Y markers used later) that never appear in legitimate input but are invaluable as scratch marks. Second, the transition function $\delta$δ is exactly the machine's program — change $\delta$δ and you have a different machine computing a different thing, even though every other part stays the same. This is the seed of the universal-machine idea developed below.

---

Configurations: Capturing a Machine "Mid-Thought"

To reason about a running machine precisely, computer scientists use the idea of a configuration (sometimes called an instantaneous description). A configuration records everything needed to know the machine's situation at one instant and to determine what it does next, namely:

1. the current state;
2. the entire tape contents (only finitely many cells are non-blank, so this is finite to write down); and
3. the head position.

A computation is then simply a sequence of configurations, each obtained from the previous one by applying the single rule of $\delta$δ that matches the current state and the symbol under the head. The machine halts when it reaches the accept state $q_a$qa​, the reject state $q_r$qr​, or a (state, symbol) pair for which no rule is defined. Writing a trace as a table of configurations — state, tape, head position, rule applied — is the standard exam technique, and it is what we do for every worked machine below.

---

How a Turing Machine Operates

One step of computation is always the same short cycle:

1. Read the symbol in the cell currently under the head.
2. Look up the matching rule in the transition function: $\delta(\text{current state}, \text{current symbol})$δ(current state,current symbol).
3. Write the rule's specified symbol into the current cell (this may leave it unchanged).
4. Move the head one cell left (L) or right (R) as the rule dictates.
5. Change to the rule's specified next state.
6. Repeat until the machine enters $q_a$qa​ (accept), $q_r$qr​ (reject), or a configuration for which $\delta$δ has no rule (in which case it simply halts).

# One step of a Turing machine, in pseudocode
FUNCTION step(state, tape, headPos)
    symbol ← tape[headPos]
    IF delta has no rule for (state, symbol) THEN
        RETURN HALTED                       # no move possible
    ENDIF
    (writeSym, direction, nextState) ← delta[state][symbol]
    tape[headPos] ← writeSym                # write
    IF direction = L THEN headPos ← headPos - 1
                     ELSE headPos ← headPos + 1   # move
    RETURN (nextState, tape, headPos)       # new configuration
ENDFUNCTION

Notice how little happens per step — one table lookup, one write, one move. All of the machine's power comes from the unbounded number of steps it may take and the unbounded tape it may use, not from any cleverness in an individual step. This is the same lesson the FSM taught (the engine is trivial; the design of the rule table is everything), now extended with read/write memory.

---

Worked Machine 1: Binary Increment

Our first concrete machine adds 1 to a binary number written on the tape (for example, 1011 becomes 1100). The strategy mirrors how you add one by hand: walk to the least significant (rightmost) bit, then propagate a carry leftwards, flipping 1s to 0s until you reach a 0 (or a blank), which you flip to 1.

States: {q0, q1, qHalt} — q0 scans rightwards to the end of the number; q1 performs the carry leftwards. Tape alphabet: {0, 1, □}.

Transition rules ($\delta$δ):

State	Read	Write	Move	Next State	Purpose
q0	0	0	R	q0	scan right over a 0
q0	1	1	R	q0	scan right over a 1
q0	□	□	L	q1	reached the end; step back to the last digit
q1	0	1	L	qHalt	carry stops: 0 becomes 1, done
q1	1	0	L	q1	carry continues: 1 becomes 0, keep going left
q1	□	1	L	qHalt	carry ran off the left end: write a leading 1

Trace: Input "1011" (configurations)

The head position is shown by square brackets around one cell.

Step	Tape (head in brackets)	State	Rule applied
0	[1] 0 1 1 □	q0	start at leftmost digit
1	1 [0] 1 1 □	q0	read 1, write 1, move R
2	1 0 [1] 1 □	q0	read 0, write 0, move R
3	1 0 1 [1] □	q0	read 1, write 1, move R
4	1 0 1 1 [□]	q0 → q1	read □, write □, move L (end found)
5	1 0 1 [1] □	q1	read 1, write 0, move L (carry)
6	1 0 [1] 0 □	q1	read 1, write 0, move L (carry)
7	1 [0] 0 0 □	q1 → qHalt	read 0, write 1, move L (carry stops)
8	[1] 1 0 0 □	qHalt	machine halts

Result: 1100, and indeed 1011 is 11 in decimal, 1100 is 12, so the machine has correctly computed $11 + 1 = 12$11+1=12. ✓

It is worth tracing a carry-overflow case in your head to see the last rule earn its place. On input 11 (decimal 3), q0 scans right to the blank and steps back into q1; q1 reads the rightmost 1, writes 0, moves left; reads the next 1, writes 0, moves left; now reads the blank to the left of the number and applies the q1, □ → 1, L, qHalt rule, writing a new leading 1. The tape becomes 100 (decimal 4) — exactly $3 + 1$3+1. Without that final rule the carry would have nowhere to go.

---

Worked Machine 2: Recognising the Language $\{ a^n b^n : n \geq 1 \}${anbn:n≥1}

The second machine is an acceptor rather than a transformer: it decides whether its input has the form $a^n b^n$anbn — some as followed by an equal number of bs (ab, aabb, aaabbb, …). Recall from the FSM lesson that no finite state machine can do this, because it would need to count an unbounded $n$n. The Turing machine succeeds precisely because it can use the tape as memory: it repeatedly "crosses off" one a and one matching b until both are exhausted.

The strategy in words:

1. In the start state, if the head reads an a, replace it with the marker X and move right (we have "used up" one a).
2. Move right over any remaining as and any Y markers until the first unmarked b is found; replace it with Y and turn left (one b matched against the a).
3. Move left over bs, Ys and as until the X just written is found; step one cell right so the head sits on the next unmarked a, and repeat from step 1.
4. When, in the start state, the head reads Y (no as remain) or a blank, sweep right to verify that no unmarked b remains. If the tape is clean, accept; if a stray b or a is left over, reject.

stateDiagram-v2
    [*] --> q0
    q0 --> q1 : a / X, R
    q0 --> q3 : Y / Y, R
    q1 --> q1 : a / a, R
    q1 --> q1 : Y / Y, R
    q1 --> q2 : b / Y, L
    q2 --> q2 : a / a, R
    q2 --> q0 : X / X, R
    q3 --> q3 : Y / Y, R
    q3 --> qAcc : blank / blank, R
    qAcc --> [*]

(The diagram labels each transition as read / write, move. State q0 starts a new pass, q1 searches right for a b, q2 returns left to the next a, and q3 performs the final clean-tape check before qAcc.)

Trace: Input "aabb" (configurations)

Step	Tape (head in brackets)	State	Rule applied
0	[a] a b b □	q0	read a, write X, move R
1	X [a] b b □	q1	read a, write a, move R
2	X a [b] b □	q1	read b, write Y, move L
3	X [a] Y b □	q2	read a, write a, move L
4	[X] a Y b □	q2	read X, write X, move R
5	X [a] Y b □	q0	read a, write X, move R
6	X X [Y] b □	q1	read Y, write Y, move R
7	X X Y [b] □	q1	read b, write Y, move L
8	X X [Y] Y □	q2	read Y... move L to find X
9	X [X] Y Y □	q2	read X, write X, move R
10	X X [Y] Y □	q0	read Y (no a's left), move to check
11	X X Y [Y] □	q3	read Y, write Y, move R
12	X X Y Y [□]	q3 → qAcc	read blank, tape clean → accept

The machine ends in the accept state, so "aabb" is accepted — correct, since it is $a^2 b^2$a2b2. A string like aab would fail: after crossing off both as the second pass finds no b to match the second X, and the machine rejects. A string like abb leaves a stray b at the final check in q3 and is likewise rejected. The tape, used as a scratchpad of X and Y markers, is the unbounded memory that lifts this beyond any finite state machine.

---

The Universal Turing Machine (UTM)

Every machine above does one fixed job, because its program — the transition function $\delta$δ — is baked in. Turing's deepest insight was that a single Turing machine can be built to do the job of any of them. A Universal Turing Machine (UTM) takes two things written on its tape:

1. an encoded description of some Turing machine $T$T (its states, alphabet and transition rules, written out as a string of symbols), and
2. an input $w$w for $T$T.

The UTM then simulates $T$T step by step on $w$w, reading $T$T's rules from the tape, keeping track of $T$T's current state and head position, and producing exactly the result $T$T would produce. In effect the UTM treats the description of $T$T as a program and the string $w$w as that program's data.

flowchart LR
    A["Encoded description of machine T"] --> U["Universal Turing Machine"]
    B["Input w for T"] --> U
    U --> R["Same output T would give on w"]

The significance is hard to overstate:

• It shows that a single, fixed machine can be made to behave like any special-purpose machine, simply by being given that machine's description. There is no need to build new hardware for each new task.
• This is precisely the principle of the stored-program computer (the von Neumann architecture): a program and its data both live in the same memory, and a single processor fetches and executes whatever program it is given.
• Every general-purpose computer you use — phone, laptop, server — is, at this level of abstraction, a physical realisation of a Universal Turing Machine. The CPU is the universal machine; the software is the description of the special-purpose machine you want it to imitate.

The UTM is therefore the theoretical bridge between Turing's 1936 abstraction and the programmable computers that followed: the very idea that software exists is the universal machine made real.

---

Turing Machine versus Finite State Machine