Basics of a Turing Machine
Computation and Turing Machines · v1.0.1
2026-09-07 03:05:26
Where we are
Where this fits
- The previous unit, The Limits of Computation, left a question open
- Proving “no algorithm exists” requires a precise stand-in for algorithm
- The informal notion of “Python decidable” cannot supply that precision
- This unit builds the stand-in: the Turing machine
Outline of key topics
- Deriving the machine from pencil-and-paper computation
- The formal 6-tuple definition
- Configurations and the yield relation
- Machines that rewrite the tape
- Machines that recognize languages
- The Universal Turing Machine
Why a model of computation is needed
Requirements on the definition
A definition of computation has to satisfy three demands at once:
- simple enough to reason about mathematically
- intuitive enough to capture what a person does by hand
- generic enough that nothing computable escapes it
Turing’s approach
Model the person, not the machine.
- observe what a human does with pencil and paper
- formalize that process directly, rather than inventing a device and hoping it is powerful enough
What this unit builds
- derive the model from human computation
- define it precisely, as a 6-tuple
- trace it running, one step at a time
- build four machines
- finish with the Universal Turing Machine, a machine that runs other machines
From paper to tape
The three components
| Human computation | Machine computation |
|---|---|
| the paper | tape |
| the hand and eye | tape head |
| what to do next | transition function |
Components of a Turing machine
- the tape holds the symbols
- the head reads and writes one cell at a time
- the finite control holds the state
Why each part exists
- Tape — simulates unlimited sheets of paper; unlimited, not infinite in use, since any halting run touches finitely many cells
- Tape head — reads and writes one cell, and moves left or right
- States — simulate the states of a human mind; finitely many, which is the substantive assumption in the whole model
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 |
Every machine built in this unit is assembled from these three.
The formal definition
The 6-tuple
\[M = (Q, \Sigma, \Gamma, \delta, q_0, H)\]
- \(Q\): a finite set, the states
- \(\Sigma\): a finite set, the input alphabet
- \(\Gamma\): a finite set, the tape alphabet, with \(\Sigma \cup \{\triangleright, \square\} \subseteq \Gamma\)
- \(\delta\): the transition function
- \(q_0\): the start state
- \(H = \{q_{\text{acc}}, q_{\text{rej}}\}\): the halting states
The alphabets
- \(\triangleright\) — the left end symbol
- \(\square\) — the blank symbol
- \(\leftarrow, \rightarrow\) — the movement symbols; excluded from both \(\Sigma\) and \(\Gamma\)
- \(\Gamma \supseteq \Sigma \cup \{\triangleright, \square\}\): every symbol \(\Gamma\) adds beyond \(\Sigma\) is working space, for marks the machine writes to remember what it has already handled
The transition function
\[\delta : (Q - H) \times \Gamma \to Q \times (\Gamma \cup \{\leftarrow, \rightarrow\})\]
- domain excludes \(H\): halting states have no outgoing transitions
- codomain: a step writes a symbol or moves — never both
- on \(\triangleright\), the head must move right; \(M\) never falls off the left end of the tape
The most common mistake
- forgetting the transition on \(\triangleright\)
- every machine in this unit opens with a \(\triangleright\) transition that moves right
- a machine that omits it is not a legal Turing machine
Configurations and the yield relation
Definition of a configuration
A configuration is the state, the head position, and the tape content — for example \((q_4, \triangleright bbb\square)\).
A snapshot: everything needed to pause the machine and resume it later, and nothing more.
A traced run, on input \(bbb\)
| Time | Configuration | State | Tape |
|---|---|---|---|
| 0 | \(C_0\) | \(q_0\) | ▷ b b b □ □ … |
| 1 | \(C_1\) | \(q_1\) | ▷ 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\]
\[C_0 \vdash^{5}_{M} C_5 \qquad C_1 \vdash^{*}_{M} C_4\]
- \(\vdash_M\): one configuration yields the next
- \(\vdash^{k}_M\): yields in exactly \(k\) steps
- \(\vdash^{*}_M\): yields eventually, step count unstated
A consequence of the definition
- a machine may reach \(q_{\text{acc}}\) before the head has visited the whole input
- nothing forces the head to advance through the input at a fixed rate, or at all — it moves only where \(\delta\) sends it
- that freedom permits both early acceptance and running forever
Machines that rewrite the tape
Erasing the input
Problem. Construct a TM to erase the input string.
- sweeps right, replacing each symbol with a blank
- two states are enough, because the work alternates
Erasing machine, transition table
| \(\triangleright\) | \(a\) | \(\square\) | |
|---|---|---|---|
| \(q_0\) | \((q_0, \rightarrow)\) | \((q_1, \square)\) | \((q_h, \square)\) |
| \(q_1\) | — | \((q_0, a)\) | \((q_0, \rightarrow)\) |
\(q_0\) writes a blank over the current symbol; \(q_1\) steps right; the cycle repeats.
Erasing machine, diagram
- self-loop on \(q_0\): the \(\triangleright\) transition
- \(q_0 \to q_1\): write blank
- \(q_1 \to q_0\): step right
Copying a string
Problem. Construct a TM that copies a string from \(L = \Sigma^*\), \(\Sigma = \{a, b\}\).
\[\Gamma = \Sigma \cup \{\triangleright, \square, \#, 1, 2\}\]
- \(\#\) marks where the copy begins
- \(1\): an \(a\) already copied; \(2\): a \(b\) already copied
- strategy: one symbol per round trip — mark it, walk right, write the copy, walk back, restore the marker, step right
Copying machine, diagram
- \(q_4\): carries an \(a\) across
- \(q_5\): carries a \(b\) across
- \(q_6, q_7\): return and restore the marker
What generalises
- Markers are memory. The state set is finite and cannot count, so anything the machine must remember about position is written on the tape instead.
- 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
Strings containing \(ab\) or ending in \(ba\)
Problem. Construct a TM that accepts \(L = \{\)strings containing \(ab\) or ending with \(ba\}\).
Recognizer, diagram
- \(q_2\): just saw an \(a\)
- \(q_4\): just saw a \(b\)
- \(q_3\): has seen \(ab\), accepts whatever follows
No writes needed
| \(\triangleright\) | \(a\) | \(b\) | \(\square\) | |
|---|---|---|---|---|
| \(q_0\) | \((q_1, \rightarrow)\) | — | — | — |
| \(q_1\) | — | \((q_2, \rightarrow)\) | \((q_4, \rightarrow)\) | — |
| \(q_3\) | — | \((q_{\text{acc}}, \rightarrow)\) | \((q_{\text{acc}}, \rightarrow)\) | \((q_{\text{acc}}, \rightarrow)\) |
Every entry is a move. The whole job is done by the finite state set.
Accepting before the input ends
On \(aabbbbb\): the machine reaches \(q_3\) after reading \(aab\), and accepts on the next step, with four symbols still unread.
A Turing machine can accept a string without scanning it completely.
Counting three symbols: \(a^n b^n c^n\)
Problem. Construct a TM to accept \(L = \{a^n b^n c^n \mid n \geq 1\}\).
Why the state set alone fails
- three counts must be confirmed equal
- \(n\) can be arbitrarily large
- \(Q\) is finite: no fixed number of states holds an unbounded tally
- the counting has to happen on the tape
\[\Gamma = \Sigma \cup \{\triangleright, \square, x, y, z\}\]
Recognizer, diagram
- one pass crosses off one \(a\), one \(b\), one \(c\)
- \(q_4\) returns to the left for the next pass
- \(q_5\) confirms only \(y\)s and \(z\)s remain
What generalises
- a recognizer needs no writes when the finite state set can hold everything it must remember
- when it cannot — an unbounded count — the tape holds the memory instead, as crossed-off symbols
- rejection is a state, \(q_{\text{rej}}\), reached by every transition the table leaves blank
The Universal Turing Machine
Definition
A Universal Turing Machine \(U\) simulates the execution of any Turing machine \(M\) on any input \(w\).
The input to \(U\) is written \(\langle M, w \rangle\): an encoding of the machine, together with its input.
The specification
- \(U(\langle M, w \rangle)\) halts if and only if \(M\) halts on \(w\)
- if \(M\) decides or semidecides: \(U\) accepts exactly when \(M\) accepts, rejects exactly when \(M\) rejects
- if \(M\) computes a function: \(U(\langle M, w \rangle) = M(w)\)
The universality theorem
Given any Turing machine \(M\) and an input string \(w\), there exists a Turing machine \(M'\) that simulates the execution of \(M\) on \(w\), halts if and only if \(M\) halts on \(w\), and if it halts, returns whatever result \(M\) returns.
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 as a string, \(\langle M \rangle\)
- a string can sit on a tape, and a tape is where input lives
- the distinction between program and data disappears
Why the tape makes this possible
- \(\langle M \rangle\) can be arbitrarily long, since \(M\) may have any number of states
- \(U\) must re-read \(\langle M \rangle\) at every step, alongside tracking the whole of \(M\)’s own tape
- a finite state set alone could hold neither
- universality is bought with the unbounded rewritable tape
Compiler self-hosting and bootstrapping
- write a new language \(X\)’s first compiler in some other language
- use it to compile the source of an \(X\)-language compiler, written in \(X\)
- from then on, the compiler compiles itself
- the same reason \(U\) works: the program is data
What has not been shown
- \(U\) simulates: if \(M\) loops forever on \(w\), \(U\) loops forever too
- \(U\) does not decide anything — it cannot say in advance what \(M\) will do
Summary
Summary \(^1/_2\)
- Turing machines formalize human pencil-and-paper computation through states, tape and transitions
- A machine is defined completely by the 6-tuple \(M = (Q, \Sigma, \Gamma, \delta, q_0, H)\)
- Computation is a sequence of configuration transitions, \(C_0 \vdash_M \cdots \vdash_M C_k\)
Summary \(^2/_2\)
- The tape provides memory the finite state set cannot: markers let a fixed number of states match unbounded counts
- A Universal Turing Machine simulates any machine given its description, because a finite machine can be encoded 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
- the halting question becomes central, and has no algorithmic answer
- the Universal Turing Machine supplies the self-reference a diagonal argument needs
Computation and Turing Machines · Basics of a Turing Machine · ver. 1.0.1 ·