Basics of a Turing Machine
Turing Machine
2026-08-18 18:01
Where we are
What this unit does not assume
This course does not have formal language theory as a prerequisite.
- We will not use finite automata, pushdown automata or grammars.
- We will not classify languages as regular or context-free.
- Everything is built from scratch.
Every claim about what a Turing machine can do is backed by building one.
What you will be able to do
- Explain how a Turing machine formalizes a human computing with pencil and paper.
- Write down the 6-tuple definition and read a transition function.
- Trace a run as a sequence of configurations.
- Construct a machine that rewrites its tape.
- Construct a machine that recognizes a language.
- Explain what a Universal Turing Machine does.
What we will cover
- Turing Machine — an infinite tape, a read/write head, a finite state control.
- Turing Machine Configuration — a snapshot of state, head position and tape.
- Universal Turing Machine — a machine that simulates any other machine.
- Compiler Self-Hosting and Bootstrapping — a compiler written in its own language.
Why we need a model of computation
The question
What does it mean for something to be computable?
You can already write programs, so you have an intuition for this.
The next unit proves that some problems have no program at all — and you cannot prove the absence of something you have not defined.
Three demands, pulling against each other
Simple enough to reason about mathematically.
A model with fifty features admits no finished proof.
Intuitive enough that we believe it captures human calculation.
Generic enough that nothing computable escapes it.
Turing’s move
He modelled the person, not the machine.
Rather than inventing a powerful device and hoping it was powerful enough, he looked at what a human being does with a pencil and a sheet of paper — and formalized that.
From paper to tape
How does a human compute?
- Write the input on the paper.
- Do the computation — think, and write intermediate results on the paper.
- Write the output on the paper.
Three activities. We now give each one a machine component.
The mapping
| Human | Machine |
|---|---|
| the paper | tape |
| the hand and eye | tape head |
| what to do next | transition function |
What each part is for
- Tape — simulates unlimited sheets of paper.
- Tape head — reads and writes one cell, moves left or right.
- States — simulate the states of a human mind. There are finitely many.
- Input — finitely many symbols initially on the tape.
- Output — finitely many symbols finally on the tape.
Three operations
| Operation | Explanation |
|---|---|
| Write | (Optionally) writes a new symbol at the current tape position. |
| Move | (Optionally) moves either left or right. |
| Think | (Optionally) changes to a new state. |
Everything in the rest of this unit is built from these three.
Is this really enough?
The claim that write, move and think capture every mechanical computation is not a theorem.
It is a claim about the physical world.
We meet it by name next unit: the Church–Turing thesis.
The formal definition
A Turing machine is a 6-tuple
\[M = (Q, \Sigma, \Gamma, \delta, q_0, H)\]
The six components
- \(Q\) — a finite set, the set of states.
- \(\Sigma\) — the input alphabet. Excludes \(\triangleright, \square, \leftarrow, \rightarrow\).
- \(\Gamma\) — the tape alphabet, with \(\Sigma \cup \{\triangleright, \square\} \subseteq \Gamma\).
- \(\delta\) — the transition function.
- \(q_0\) — the start state, \(q_0 \in Q\).
- \(H = \{q_{\text{acc}}, q_{\text{rej}}\}\) — the halting states.
\(\Gamma\) is allowed to be bigger than \(\Sigma\). The extra symbols are working space — every machine we build uses them.
The symbols
- \(\triangleright\) — the left end symbol.
- \(\square\) — the blank symbol.
- \(\leftarrow, \rightarrow\) — the movement symbols.
- \(\Sigma\) — input, output and special symbols.
- \(\Gamma\) — every symbol that can appear on the tape.
Reading the transition function
\[\delta : (Q - H) \times \Gamma \to Q \times (\Gamma \cup \{\leftarrow, \rightarrow\})\]
Two details worth slowing down for
The domain is \((Q - H) \times \Gamma\), not \(Q \times \Gamma\).
Halting states have no outgoing transitions. That is what halting means.
The codomain pairs a next state with either a symbol or a direction.
Writing and moving take two steps, never one.
The left-end trap
There is one more constraint, and it is a condition on \(\delta\) rather than part of its type:
\(M\) never falls off the left end. When the current symbol is \(\triangleright\), the head has to move right.
Forgetting the \(\triangleright\) column is the most common mistake in a hand-built machine.
Configurations and the yield relation
A configuration
The current state, the head position, and the tape content.
\[(q_4, \triangleright bbb\square)\]
A snapshot with nothing left out.
A computation is a sequence of them
| Time | Configuration | State | Tape |
|---|---|---|---|
| 0 | \(C_0\) | \(q_0\) | ▷ b b b □ … |
| 1 | \(C_1\) | \(q_1\) | ▷ b b b □ … |
| 2 | \(C_2\) | \(q_4\) | ▷ b b b □ … |
| 3 | \(C_3\) | \(q_4\) | ▷ b b b □ … |
| 4 | \(C_4\) | \(q_4\) | ▷ b b b □ … |
| 5 | \(C_5\) | \(q_{\text{rej}}\) | ▷ b b b □ … |
The yield relation
\[C_0 \vdash_M C_1 \vdash_M C_2 \vdash_M C_3 \vdash_M C_4 \vdash_M C_5\]
Computation length is 5:
\[C_0 \vdash^{5}_{M} C_5\]
When the number of steps does not matter:
\[C_1 \vdash^{*}_{M} C_4\]
Tracing is slow, and that is the point
It is the only way to see what a machine actually does rather than what you meant it to do.
It is how you will debug every machine you build in the next two sections.
A machine can accept early
A Turing machine may reach \(q_{\text{acc}}\) before the head has visited the whole input.
Nothing obliges the head to advance through the input at a fixed rate, or at all. It moves only where \(\delta\) sends it.
That freedom is what makes both early acceptance and running forever possible.
Machines that rewrite the tape
These machines compute, they do not answer
They change the tape and leave a result on it.
A machine that could only ever read would have nowhere to put an answer.
Erasing the input: the run
Problem. Construct a TM to erase the input string.
| Time | State | Tape |
|---|---|---|
| 0 | \(q_0\) | ▷ a a a □ … |
| 2 | \(q_1\) | ▷ □ a a □ … |
| 4 | \(q_1\) | ▷ □ □ a □ … |
| 6 | \(q_1\) | ▷ □ □ □ □ … |
| 8 | \(q_h\) | ▷ □ □ □ □ … |
Erasing the input: the machine
| \(\triangleright\) | \(a\) | \(\square\) | |
|---|---|---|---|
| \(q_0\) | \((q_0, \rightarrow)\) | \((q_1, \square)\) | \((q_h, \square)\) |
| \(q_1\) | — | \((q_0, a)\) | \((q_0, \rightarrow)\) |
Two states are enough: \(q_0\) blanks the symbol, \(q_1\) steps right.
Copying a string: the idea
Problem. Copy a string over \(\Sigma = \{a, b\}\).
\[\Gamma = \Sigma \cup \{\triangleright, \square, \#, 1, 2\}\]
- \(\#\) marks where the copy begins.
- \(1\) stands for an \(a\) already copied, \(2\) for a \(b\) already copied.
One symbol per round trip: mark it, walk right, write the copy, walk back, restore.
Copying a string: the machine
| \(\triangleright\) | \(a\) | \(b\) | \(\#\) | 1 | 2 | \(\square\) | |
|---|---|---|---|---|---|---|---|
| \(q_0\) | \((q_1, \rightarrow)\) | — | — | — | — | — | — |
| \(q_1\) | — | \((q_1, \rightarrow)\) | \((q_1, \rightarrow)\) | — | — | — | \((q_2, \#)\) |
| \(q_2\) | \((q_3, \rightarrow)\) | \((q_2, \leftarrow)\) | \((q_2, \leftarrow)\) | \((q_2, \leftarrow)\) | — | — | — |
| \(q_3\) | — | \((q_4, 1)\) | \((q_5, 2)\) | \((q_{\text{acc}}, \#)\) | — | — | — |
| \(q_4\) | — | \((q_4, \rightarrow)\) | \((q_4, \rightarrow)\) | \((q_4, \rightarrow)\) | \((q_4, \rightarrow)\) | — | \((q_6, a)\) |
| \(q_5\) | — | \((q_5, \rightarrow)\) | \((q_5, \rightarrow)\) | \((q_5, \rightarrow)\) | — | \((q_5, \rightarrow)\) | \((q_6, b)\) |
| \(q_6\) | — | \((q_6, \leftarrow)\) | \((q_6, \leftarrow)\) | \((q_6, \leftarrow)\) | \((q_7, a)\) | \((q_7, b)\) | — |
| \(q_7\) | — | \((q_3, \rightarrow)\) | \((q_3, \rightarrow)\) | — | — | — | — |
Cells with “—” mean the machine terminates in \(q_{\text{rej}}\).
Copying a string: the shape of it
The left branch through \(q_4\) carries an \(a\) across; the right branch through \(q_5\) carries a \(b\).
Two ideas that generalise
Markers are memory.
The state set is finite and cannot count, so anything the machine must remember about position gets written on the tape.
A round trip is a pair of states.
\(q_4\) and \(q_5\) go right; \(q_6\) comes back. Every multi-pass machine has this shape.
Machines that recognize languages
Two examples, either side of a line
What a single scan can settle.
And what it cannot.
One scan is enough
Problem. Accept all strings containing \(ab\) or ending with \(ba\).
| \(\triangleright\) | \(a\) | \(b\) | \(\square\) | |
|---|---|---|---|---|
| \(q_0\) | \((q_1, \rightarrow)\) | — | — | — |
| \(q_1\) | — | \((q_2, \rightarrow)\) | \((q_4, \rightarrow)\) | — |
| \(q_2\) | — | \((q_2, \rightarrow)\) | \((q_3, \rightarrow)\) | — |
| \(q_3\) | — | \((q_{\text{acc}}, \rightarrow)\) | \((q_{\text{acc}}, \rightarrow)\) | \((q_{\text{acc}}, \rightarrow)\) |
| \(q_4\) | — | \((q_5, \rightarrow)\) | \((q_4, \rightarrow)\) | — |
| \(q_5\) | — | \((q_2, \rightarrow)\) | \((q_3, \rightarrow)\) | \((q_{\text{acc}}, \rightarrow)\) |
Notice what is missing
There is no write anywhere in the table. Every entry is a move.
Two runs
\(bba\) — accepted
| Time | State |
|---|---|
| 0 | \(q_0\) |
| 1 | \(q_1\) |
| 2 | \(q_4\) |
| 3 | \(q_4\) |
| 4 | \(q_5\) |
| 5 | \(q_{\text{acc}}\) |
\(bbb\) — rejected
| Time | State |
|---|---|
| 0 | \(q_0\) |
| 1 | \(q_1\) |
| 2 | \(q_4\) |
| 3 | \(q_4\) |
| 4 | \(q_4\) |
| 5 | \(q_{\text{rej}}\) |
The tape never changes in either run.
Now trace \(aabbbbb\) yourself
The machine reaches \(q_3\) after reading \(aab\), and accepts on the next step.
Four symbols are still unread.
A Turing machine can accept a string without scanning it completely.
When one scan is not enough
Problem. Accept \(L = \{a^n b^n c^n \mid n \geq 1\}\).
\[L = \{abc,\; aabbcc,\; aaabbbccc,\; \ldots\}\]
The machine must confirm three counts are equal.
- \(n\) can be arbitrarily large.
- \(Q\) is finite.
No fixed number of states holds an unbounded tally. The counting must happen on the tape.
Grow the alphabet, cross things off
\[\Gamma = \Sigma \cup \{\triangleright, \square, x, y, z\}\]
\(x\), \(y\) and \(z\) mark a crossed-off \(a\), \(b\) and \(c\).
Each pass crosses off one of each, then returns to the left end.
The machine
| \(\triangleright\) | \(a\) | \(b\) | \(c\) | \(x\) | \(y\) | \(z\) | \(\square\) | |
|---|---|---|---|---|---|---|---|---|
| \(q_0\) | \((q_1, \rightarrow)\) | — | — | — | — | — | — | — |
| \(q_1\) | — | \((q_2, x)\) | — | — | — | \((q_5, \rightarrow)\) | — | — |
| \(q_2\) | — | \((q_2, \rightarrow)\) | \((q_3, y)\) | — | \((q_2, \rightarrow)\) | \((q_2, \rightarrow)\) | — | — |
| \(q_3\) | — | — | \((q_3, \rightarrow)\) | \((q_4, z)\) | — | \((q_3, \rightarrow)\) | \((q_3, \rightarrow)\) | — |
| \(q_4\) | — | \((q_4, \leftarrow)\) | \((q_4, \leftarrow)\) | — | \((q_1, \rightarrow)\) | \((q_4, \leftarrow)\) | \((q_4, \leftarrow)\) | — |
| \(q_5\) | — | — | — | — | — | \((q_5, \rightarrow)\) | \((q_5, \rightarrow)\) | \((q_{\text{acc}}, \square)\) |
The cycle
- \(q_1\) crosses an \(a\) to \(x\)
- \(q_2\) runs right, crosses a \(b\) to \(y\)
- \(q_3\) runs right, crosses a \(c\) to \(z\)
- \(q_4\) walks back to the last \(x\)
. . .
\(q_1\) finding \(y\) means the \(a\)s ran out. \(q_5\) checks only \(y\)s and \(z\)s remain.
One pass per row
| State | Tape |
|---|---|
| \(q_0\) | ▷ a a b b c c □ |
| \(q_2\) | ▷ x a b b c c □ |
| \(q_3\) | ▷ x a y b c c □ |
| \(q_4\) | ▷ x a y b z c □ |
| \(q_2\) | ▷ x x y b z c □ |
| \(q_3\) | ▷ x x y y z c □ |
| \(q_4\) | ▷ x x y y z z □ |
| \(q_5\) | ▷ x x y y z z □ |
| \(q_{\text{acc}}\) | ▷ x x y y z z □ |
The crossings-off are the memory
They persist between passes, so pass \(k\) sees what pass \(k-1\) did.
Six states match three counts of any size.
The same trick as the copying machine, applied to a harder problem.
The Universal Turing Machine
Every machine so far did one job
The last construction of the unit does all of them.
What \(U\) promises
A Universal Turing Machine \(U\) simulates any machine \(M\) on any input \(w\), given \(\langle M, w \rangle\).
- \(U(\langle M, w \rangle)\) halts if and only if \(M\) halts on \(w\).
- If \(M\) decides or semidecides: \(M\) accepts \(\Rightarrow\) \(U\) accepts; \(M\) rejects \(\Rightarrow\) \(U\) rejects.
- If \(M\) computes a function: \(U(\langle M, w \rangle) = M(w)\).
The move that makes it work
A Turing machine is a finite object.
Finitely many states, a finite alphabet, a finite transition table.
So it can be written out as a string, \(\langle M \rangle\).
Once a machine is a string, it can sit on a tape. And a tape is where input lives.
Program becomes data
The distinction between program and data disappears.
That collapse is the whole idea.
Why the tape is what makes this possible
\(\langle M \rangle\) can be arbitrarily long — \(M\) may have any number of states.
\(U\) must re-read it at every step, and track the whole of \(M\)’s tape.
A machine whose only memory is its finite state set could hold neither.
Universality is bought with the unbounded rewritable tape.
You have already seen this
Invent a language \(X\). No compiler for \(X\) exists — you just invented it.
Can you write a compiler for \(X\) in \(X\)?
Yes. Write the first one in another language, compile the \(X\) compiler’s source, and from then on it compiles itself.
Compiler Self-Hosting and Bootstrapping works for the same reason \(U\) does: the program is data.
What has not been shown
\(U\) simulates.
If \(M\) loops forever on \(w\), then \(U\) loops forever too.
\(U\) does not decide anything.
Summary
What you can now do
- Derive the machine from a person with a pencil.
- State \(M = (Q, \Sigma, \Gamma, \delta, q_0, H)\) and read a transition table.
- Trace a run as configurations.
- Build a machine that rewrites the tape, and one that recognizes a language.
- Explain universality and what it costs.
The five things to carry away
- Turing machines formalize human pencil-and-paper computation through states, tapes and transitions.
- A machine is defined completely by its 6-tuple; everything else is a way of reading \(\delta\).
- Computation is a sequence of configurations, \(C_0 \vdash_M \dots \vdash_M C_k\).
- The tape is not just storage — it is the memory the finite state set cannot provide.
- A Universal Turing Machine simulates any machine, because a finite machine encodes as a string.
Where next
Algorithms and the Limits of Computation
The next unit takes this machine as the definition of algorithm, and asks what stays out of reach.
Two threads it pulls on
Halting. Nothing forces a Turing machine to stop.
Once an algorithm is defined as a machine that always halts, whether a given machine halts becomes the central question — and it has no algorithmic answer.
Universality. We built a machine that takes another machine as input.
That is exactly the self-reference a diagonal argument needs.
This unit built the machine.
The next one finds its limits.
Turing Machine · Basics of a Turing Machine