Turing Machines

A Turing machine is the most powerful model of computation in the whole of theoretical Computer Science — and, remarkably, one of the simplest to describe. Devised by Alan Turing in 1936, years before any electronic computer existed, it was not a blueprint for a machine to build but a mathematical idealisation designed to answer a profound question: what does it mean for something to be computable at all? Turing's answer — a tireless clerk following fixed rules, with an endless supply of paper, reading and rewriting symbols one at a time — turned out to capture every form of mechanical computation we have ever devised. Anything a modern supercomputer can compute, a Turing machine can compute too (given enough tape and time); and, more startlingly, there are precisely-stated problems that no Turing machine — and therefore no computer ever — can solve.

This is the model that sits at the top of the automata story you have been building. A finite-state machine has only its states as memory; a pushdown automaton adds a stack; a Turing machine adds an unbounded tape it can move along and rewrite freely — and that single addition is enough to make it as powerful as computation gets. This lesson develops the H446 view: the Turing-machine model (tape, head, states, transition function), the formal definition written in proper notation, two fully worked machines that you can trace by hand, the idea of the Universal Turing Machine (one machine that runs any other — the theoretical root of the stored-program computer), the Church–Turing thesis, and the halting problem — the landmark proof that some things are simply non-computable. The halting problem links straight to the optimisation & tractability material in the Algorithms course, where the practical cousin of "impossible" — "possible but infeasible" — is explored.

---

Spec Mapping

This lesson addresses the Turing-machine content of H446 section 2.1 (computational methods / theory of computation). The specification expects you to be able to:

• describe the Turing-machine model — an infinite tape of cells, a read/write head, a finite set of states, and a transition function that, from the current state and the symbol read, fixes the symbol to write, the direction to move, and the next state;
• understand and use the formal definition of a Turing machine as a tuple, and read a transition rule written in the standard notation;
• trace a given Turing machine on a given input tape, showing the tape and head position at each step, and design a simple machine for a stated task;
• explain the Universal Turing Machine and its significance as the theoretical basis of the stored-program (von Neumann) computer, and state the Church–Turing thesis;
• understand computable vs non-computable problems and the halting problem as the canonical example of non-computability, including the idea that this draws a hard limit on what computers can do.

It is the apex of the automata sequence (FSMs → pushdown automata → Turing machines) developed across this course, and it connects to optimisation & tractability (Algorithms course) and stored-program architecture (Processors topic).

---

The Turing-Machine Model

A Turing machine has just four parts, but each is chosen with care:

Component	Description
Tape	an infinite strip of cells, each holding one symbol (or a blank); it can be read and written, and is unbounded in (at least) one direction
Read/write head	points at one cell at a time; it can read that cell's symbol, overwrite it, and move one cell left or right
State register	holds the machine's current state, one of a finite set
Transition function	the fixed rulebook: given (current state, symbol read) it dictates (symbol to write, direction to move, next state)

The contrast with the earlier automata is the whole story. A finite-state machine reads its input once, left to right, and cannot write; its only memory is which of finitely many states it is in. A Turing machine can move both ways along its tape and rewrite any cell, and its tape is unbounded — so it has effectively limitless, re-usable memory it can revisit as often as it likes. That is exactly the capability the lesser machines lacked, and it is why the Turing machine can do things (genuine arithmetic, simulating other machines, recognising the hardest languages) that they cannot.

How it operates, step by step

At each step the machine:

1. reads the symbol in the cell under the head;
2. consults the transition function with (current state, symbol read), which specifies:
   • the symbol to write into the current cell (replacing what was there),
   • the direction to move the head — Left or Right by one cell,
   • the next state to enter;
3. repeats — until it enters a halting state (accept or reject), or it never halts and runs forever.

That final clause is not a flaw to be engineered away — the possibility of running forever is intrinsic to the model, and it is precisely what makes the halting problem meaningful later.

---

Formal Definition

A Turing machine is formally a 7-tuple:

$M = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ q_{accept},\ q_{reject})$M=(Q, Σ, Γ, δ, q0​, qaccept​, qreject​)

with each component defined as follows:

Symbol	Meaning
$Q$Q	a finite set of states
$\Sigma$Σ	the input alphabet — symbols that may appear on the tape initially (the blank is not in $\Sigma$Σ)
$\Gamma$Γ	the tape alphabet — everything that may appear on the tape; it includes $\Sigma$Σ and the blank symbol
$\delta$δ	the transition function (the rulebook)
$q_0$q0​	the start state (an element of $Q$Q)
$q_{accept}$qaccept​	the accepting halting state
$q_{reject}$qreject​	the rejecting halting state

The transition function has the signature

$\delta : Q \times \Gamma \ \to\ Q \times \Gamma \times \{L, R\}$δ:Q×Γ → Q×Γ×{L,R}

which reads: given a state and the symbol under the head, produce a next state, a symbol to write, and a move direction (Left or Right). The relationship $\Sigma \subseteq \Gamma$Σ⊆Γ — the input alphabet is part of the larger tape alphabet — matters because a machine often needs extra working symbols (markers, a blank) that were never in the input but are useful as scratch notation on the tape.

---

The Transition Function in Practice

A single rule of $\delta$δ is conventionally written

$\delta(q_i,\ a) = (q_j,\ b,\ D)$δ(qi​, a)=(qj​, b, D)

meaning: in state $q_i$qi​, reading symbol $a$a, write $b$b, move in direction $D$D, and switch to state $q_j$qj​. The same information is usually laid out as a table. Here, for instance, is a machine that flips every bit and then returns the head to the left (using _ for the blank):

Current state	Read	Write	Move	Next state
q0	0	1	R	q0
q0	1	0	R	q0
q0	_	_	L	q1
q1	0	0	L	q1
q1	1	1	L	q1
q1	_	_	R	qhalt

Reading row 1 in formal notation: $\delta(q_0, 0) = (q_0, 1, R)$δ(q0​,0)=(q0​,1,R). The table is the machine — together with the start state and the alphabets, it fully determines the behaviour, exactly as a state-transition table fully determines an FSM.

A useful idea when tracing is the configuration (sometimes called an instantaneous description): a complete snapshot of the machine at one moment, consisting of the current state, the entire tape contents, and the head position. Because the transition function is fixed, each configuration determines exactly one next configuration — so a Turing-machine computation is nothing more than a chain of configurations, each following from the last by one rule, starting from the initial configuration (start state, head on the leftmost input symbol) and ending — if it ends at all — in a halting configuration. The trace tables below are simply that chain of configurations written out row by row, which is why showing the state, full tape and head position on every line is the correct way to present a trace.

---

Worked Example: Binary Complement

Task. Build a Turing machine that replaces every bit of a binary string with its complement (every 0→1, every 1→0).

Idea. Sweep right across the string, flipping each bit as the head passes over it, and stop at the first blank. Only one working state is needed:

Current state	Read	Write	Move	Next state
q0	0	1	R	q0
q0	1	0	R	q0
q0	_	_	L	qhalt

Formally the flipping rules are $\delta(q_0,0)=(q_0,1,R)$δ(q0​,0)=(q0​,1,R) and $\delta(q_0,1)=(q_0,0,R)$δ(q0​,1)=(q0​,0,R), with $\delta(q_0,\_)=(q_{halt},\_,L)$δ(q0​,_)=(qhalt​,_,L) to stop at the blank. Trace on input 10110 (head starts on the leftmost symbol; brackets mark the head):

Step	State	Tape (head in brackets)	Action
0	q0	_ [1] 0 1 1 0 _	read 1 → write 0, move R
1	q0	_ 0 [0] 1 1 0 _	read 0 → write 1, move R
2	q0	_ 0 1 [1] 1 0 _	read 1 → write 0, move R
3	q0	_ 0 1 0 [1] 0 _	read 1 → write 0, move R
4	q0	_ 0 1 0 0 [0] _	read 0 → write 1, move R
5	q0	_ 0 1 0 0 1 [_]	read _ → halt (move L into qhalt)

Output tape: _ 0 1 0 0 1 _. The complement of 10110 is 01001 — correct. Notice how the machine rewrites the tape in place, something no FSM can do — the tape is both the input and the workspace.

---

Worked Example: Unary Increment

Task. Add 1 to a number written in unary (the number n is written as n ones). So 111 (three) must become 1111 (four).

Idea. Walk right over the existing ones to the first blank, write a 1 there, and stop:

Current state	Read	Write	Move	Next state
q0	1	1	R	q0
q0	_	1	L	qhalt

In notation: $\delta(q_0,1)=(q_0,1,R)$δ(q0​,1)=(q0​,1,R) to skip over existing ones, and $\delta(q_0,\_)=(q_{halt},1,L)$δ(q0​,_)=(qhalt​,1,L) to append the new one. Trace on 111:

Step	State	Tape (head in brackets)	Action
0	q0	_ [1] 1 1 _	read 1 → keep, move R
1	q0	_ 1 [1] 1 _	read 1 → keep, move R
2	q0	_ 1 1 [1] _	read 1 → keep, move R
3	q0	_ 1 1 1 [_]	read _ → write 1, halt

Output: 1111 — four in unary. The machine extended its own data by writing into a previously blank cell, using the unbounded tape as growable memory. These two examples — complement and increment — show the model doing genuine symbol manipulation that a finite-state or pushdown machine could not.

---

The Universal Turing Machine

So far each machine does one job, hard-wired into its rules. Turing's masterstroke was to show that a single machine can do every job. A Universal Turing Machine (UTM) is a Turing machine that takes, as its input, an encoded description of any other Turing machine $T$T together with $T$T's input, and then simulates $T$T on that input — producing whatever $T$T would have produced.

Aspect	Detail
Input	a description of a machine $T$T (its rules), plus the input intended for $T$T
Operation	the UTM reads $T$T's description and faithfully imitates $T$T step by step
Significance	one fixed machine can perform the computation of any machine — generality from a single device

The implications are enormous, and they are why the UTM, not the special-purpose machines, is the truly profound idea. The UTM is the theoretical ancestor of the stored-program (von Neumann) computer:

• the description of $T$T corresponds to a program held in memory;
• the input for $T$T corresponds to data held in memory;
• the UTM reading the description and acting on it corresponds to a processor fetching and executing instructions.

In other words, the reason a single physical computer can run a word processor, a game, and a compiler — rather than needing a different machine soldered for each — is precisely the universality Turing identified in 1936. Programs are data that another program (the machine) interprets.

Key Term: The Universal Turing Machine is why general-purpose computing exists. Because one machine can simulate any other from a stored description, we write software — programs treated as data — instead of building bespoke hardware for every task. This is the conceptual seed of the stored-program architecture.

---

The Church–Turing Thesis

The Church–Turing thesis asserts:

Any function that can be computed by any effective (mechanical, step-by-step) method can be computed by a Turing machine.

It is one of the most important claims in the subject, and its status is worth getting exactly right:

Aspect	Detail
It is a thesis, not a theorem	It cannot be proved, because "any effective method" is an informal, intuitive notion — there is nothing precise to prove it against
Overwhelming evidence	Every model of computation ever proposed (lambda calculus, recursive functions, register machines, real computers) has turned out no more powerful than a Turing machine
No counterexample	In nearly a century, nothing computable by any means has been found that a Turing machine cannot compute
Implication	the Turing machine defines the limit of what is computable — "computable" effectively means "computable by a Turing machine"

The practical upshot is stark: if no Turing machine can solve a problem, then no computer can solve it — ever — regardless of speed or memory. Computability is not about engineering; it is an absolute mathematical boundary.

---

Computability and the Halting Problem