Basics of a Turing Machine
Computation and Turing Machines · v2.0.5
2026-09-20 23:10:27
Where we are
Scope and prerequisites
- Proving that a problem has no algorithm requires a precise mathematical stand-in for algorithm
- An informal notion — some program, in some language, that always answers correctly — cannot supply one
- This unit builds that stand-in
- Assumed: sets, tuples, functions, and reading a table that says “in this situation, do that”
No formal language theory is assumed: no automata, no grammars, no language classes.
Outline of key topics
- Why a model of computation is needed, and what it must satisfy
- The three components: tape, head and finite control
- The formal definition, as a 6-tuple
- Configurations, and a run as a sequence of them
- Four machines: two that rewrite the tape, two that recognize a language
- The Universal Turing Machine
Why we need a model of computation
The demand
- The next unit proves that some problems have no algorithm
- The absence of something cannot be proved until it is defined
- A working intuition for what a program can do is not a definition
Three demands at once
- simple enough to reason about mathematically — a model with fifty features admits no finished proof
- intuitive enough to be believed as an account of carrying out a computation step by step
- generic enough that nothing computable escapes it
The three pull against each other.
Turing’s approach
The model is derived, not invented.
- Not a powerful device, proposed and hoped to be sufficient
- Built from the operations a computation requires: read a symbol, write a symbol, move one cell
- Simplicity, intuitiveness and generality follow from the derivation rather than being assumed
The machine’s components
What a computation requires
- somewhere to hold the input
- somewhere to record intermediate results, and to read them back
- somewhere to leave the output
- a rule fixing what to do next
Four requirements, met by three components.
The three components
Tape, head, and finite control.
| Requirement | Component |
|---|---|
| storage for symbols | tape |
| reading and writing one cell | tape head |
| what to do next | transition function |
What each part earns
- Tape — unbounded storage. Unbounded, not infinite in use: any halting run touches finitely many cells
- Tape head — reads and writes one cell, and moves left or right. One cell per step is the whole of its reach
- States — the machine’s memory of where it is. There are finitely many, and that is the substantive assumption
The three primitive 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 those three.
The formal definition
A Turing machine is a 6-tuple
\[M = (Q, \Sigma, \Gamma, \delta, q_0, H)\]
- \(Q\) — a finite set of states
- \(\Sigma\) — the input alphabet, excluding \(\triangleright, \square, \leftarrow, \rightarrow\)
- \(\Gamma\) — the tape alphabet, with \(\Sigma \cup \{\triangleright, \square\} \subseteq \Gamma\)
- \(q_0 \in Q\) — the start state
- \(H = \{q_{\text{acc}}, q_{\text{rej}}\}\) — the halting states
The transition function
\[\delta : (Q - H) \times \Gamma \to Q \times (\Gamma \cup \{\leftarrow, \rightarrow\})\]
The domain
- \((Q - H) \times \Gamma\), not \(Q \times \Gamma\)
- halting states have no outgoing transitions
- that is what halting means
The codomain
- a next state, paired with either a symbol to write or a direction to move
- never both
- writing and moving take two steps
The symbols
- \(\triangleright\) — the left end symbol
- \(\square\) — the blank symbol
- \(\leftarrow, \rightarrow\) — the movement symbols
- \(\Gamma\) is allowed to be larger than \(\Sigma\): the extra symbols are working space
Marks the machine writes to remember what it has already dealt with. Every machine below uses them.
The left end constraint
One further condition on \(\delta\), rather than part of its type:
- The head never falls off the left end of the tape
- When the current symbol is \(\triangleright\), the head must move right
- A machine omitting this transition is not a legal Turing machine
Configurations and the yield relation
Definition — configuration
A configuration records the current state, the head position, and the tape contents.
\[(q_4,\; \triangleright\;b\;\underline{\color{red}{b}}\;b\;\square)\]
The underlined red cell is the one the head is on.
A run as a sequence
A computation is a sequence of successive configurations, related by \(\vdash_M\):
\[C_0 \vdash_M C_1 \vdash_M C_2 \vdash_M C_3 \vdash_M C_4 \vdash_M C_5\]
- \(C_0 \vdash^{5}_{M} C_5\) — the computation time is 5
- \(C_1 \vdash^{*}_{M} C_4\) — the first yields the second eventually
A complete run, on \(bbb\)
| Time | State | Tape |
|---|---|---|
| 0 | \(q_0\) | \(\underline{\color{red}{\triangleright}}\;b\;b\;b\;\square\;\cdots\) |
| 1 | \(q_1\) | \(\triangleright\;\underline{\color{red}{b}}\;b\;b\;\square\;\cdots\) |
| 2 | \(q_4\) | \(\triangleright\;b\;\underline{\color{red}{b}}\;b\;\square\;\cdots\) |
| 3 | \(q_4\) | \(\triangleright\;b\;b\;\underline{\color{red}{b}}\;\square\;\cdots\) |
| 4 | \(q_4\) | \(\triangleright\;b\;b\;b\;\underline{\color{red}{\square}}\;\cdots\) |
| 5 | \(q_{\text{rej}}\) | \(\triangleright\;b\;b\;b\;\underline{\color{red}{\square}}\;\cdots\) |
The head does not move on the final step: \(\delta\) is undefined there, which is the rejection.
Named configurations
- the starting configuration
- the accepting and rejecting configurations
- the halting configurations
Tracing one configuration per line is how a machine’s actual behaviour becomes visible.
A consequence of the definition
A 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
Example 1: erasing the input
| \(\triangleright\) | \(a\) | \(\square\) | |
|---|---|---|---|
| \(q_0\) | \((q_0, \rightarrow)\) | \((q_1, \square)\) | \((q_h, \square)\) |
| \(q_1\) | — | \((q_0, a)\) | \((q_0, \rightarrow)\) |
Two states suffice: \(q_0\) writes a blank, \(q_1\) steps right, and back again.
Reading the table against the definition
- On \(\triangleright\) the machine moves right — the left end constraint, in force
- On \(a\) it writes \(\square\)
- On \(\square\) it writes \(\square\) and halts, because there is nothing left to erase
Example 2: copying a string
Copy a string from \(L = \Sigma^*\), where \(\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 the marker, step right
The shape of the copying machine
- the left branch through \(q_4\) carries an \(a\) across
- the right branch through \(q_5\) carries a \(b\)
- both return through \(q_6\) and \(q_7\)
- a blank table cell means termination in \(q_{\text{rej}}\)
One round trip, on \(\triangleright bba\)
| Time | State | Tape |
|---|---|---|
| 10 | \(q_3\) | \(\triangleright\;\underline{\color{red}{b}}\;b\;a\;\#\;\square\;\cdots\) |
| 11 | \(q_5\) | \(\triangleright\;\underline{\color{red}{2}}\;b\;a\;\#\;\square\;\cdots\) |
| 16 | \(q_6\) | \(\triangleright\;2\;b\;a\;\#\;\underline{\color{red}{b}}\;\cdots\) |
| 21 | \(q_7\) | \(\triangleright\;\underline{\color{red}{b}}\;b\;a\;\#\;b\;\cdots\) |
| 22 | \(q_3\) | \(\triangleright\;b\;\underline{\color{red}{b}}\;a\;\#\;b\;\cdots\) |
Mark, carry across, restore, advance. The whole run takes 47 steps.
Two ideas that generalize
- Markers are memory. The state set is finite and cannot count, so anything the machine must remember about position is 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
Example 3: one scan is enough
\[L = \{\text{strings containing } ab \text{ or ending with } ba\}\]
- every transition moves right
- nothing is ever written
- \(q_2\) — just saw an \(a\)
- \(q_4\) — just saw a \(b\)
- \(q_3\) — have seen \(ab\); accept whatever follows
What the finite state set can hold
On \(aabbbbb\), the machine reaches \(q_3\) after reading \(aab\) and accepts on the next step.
- Four symbols remain unread
- A Turing machine can accept a string without scanning it completely
Example 4: when one scan is not enough
\[L = \{a^n b^n c^n \mid n \geq 1\}\]
- The machine must confirm that three counts are equal
- \(n\) can be arbitrarily large, and \(Q\) is finite
- No fixed number of states holds an unbounded tally
The counting has to happen on the tape.
Crossing off, one of each per pass
\[\Gamma = \Sigma \cup \{\triangleright, \square, x, y, z\}\]
- \(q_1\) crosses an \(a\) to \(x\)
- \(q_2\) runs right to the first \(b\), crosses it to \(y\)
- \(q_3\) runs right to the first \(c\), crosses it to \(z\)
- \(q_4\) walks back to the last \(x\)
Why the crossings-off work
- They persist between passes, so pass \(k\) sees what pass \(k-1\) did
- When \(q_1\) finds \(y\) instead of \(a\), the \(a\)s have run out
- \(q_5\) sweeps right to confirm only \(y\)s and \(z\)s remain, then accepts
- Six states match three counts of any size
The same technique as the copying machine, applied to a harder problem.
The Universal Turing Machine
What \(U\) does
A Universal Turing Machine \(U\) simulates the execution of any machine \(M\) on any input \(w\).
\[U(\langle M, w \rangle)\]
- \(\langle M \rangle\) — an encoding of the machine
- \(w\) — that machine’s input
The specification
- \(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.
- Everything in the 6-tuple can be written out, so it can be written out as a string
- Once a machine is a string, it can sit on a tape — and a tape is where input lives
- The distinction between program and data disappears
Why the tape is what makes this possible
- \(\langle M \rangle\) can be arbitrarily long, and \(U\) must re-read it at every step
- \(U\) must also 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; not every model has it.
The same idea, running today
Compiler self-hosting and bootstrapping.
- A compiler for a new language \(X\) can be written in \(X\) itself
- Write the first compiler in another language, use it to compile the \(X\) compiler’s source
- From then on the compiler compiles itself — because the program is data
Scope of the construction
\(U\) simulates. It does not decide.
- If \(M\) loops forever on \(w\), \(U\) loops forever too
- \(U\) cannot report in advance what \(M\) will do
- The next unit turns on exactly this gap
Summary
Summary
- Turing machines model computation as states, a tape and transitions
- A machine is defined completely by \(M = (Q, \Sigma, \Gamma, \delta, q_0, H)\)
- Computation is a sequence of configurations under \(\vdash_M\)
- The tape is the memory the finite state set cannot provide
- A Universal Turing Machine simulates any machine given its description, because a finite machine encodes as a string
Where next
Algorithms and the Limits of Computation — the next unit in this module.
- Takes this machine as the definition of algorithm, and asks what stays out of reach
- Halting: once an algorithm must always halt, whether a given machine halts becomes the central question