AQA 7517 · Paper 1 · 4.4.3

Turing
Machines

Universal computation model · Church-Turing thesis · Section 4.4

WHAT YOU'LL LEARN

Tape · Read/write head · Transition function · Universal TM · Church-Turing thesis

AQA SPEC LINK

4.4.3 — Turing machines and the Universal Turing Machine

The Model

What is a Turing Machine?

A Turing machine is a theoretical model of computation invented by Alan Turing (1936). Despite its simplicity, it can compute anything that any computer can compute.

Infinite tape — divided into cells, each containing a symbol (or blank)

Read/write head — reads current cell, writes a symbol, moves left or right

State register — holds current state (like FSM states)

Transition function — δ(state, symbol) = (new state, write symbol, direction)

Formal Definition

Turing Machine — Formal Components

TM = (Q, Σ, Γ, δ, q₀, qₐ, qᵣ) where:

Q = finite set of states

Σ = input alphabet (not including blank)

Γ = tape alphabet (Σ ∪ {blank})

δ = transition function: Q × Γ → Q × Γ × {L, R}

q₀ = start state; qₐ = accept state; qᵣ = reject state

Transition Table

Turing Machine Transition Table

Each row: (current state, symbol read) → (write, move, new state). Example: TM that replaces all 0s with 1s:

State	Read	Write	Move	New State
q₀	0	1	R	q₀
q₀	1	1	R	q₀
q₀	B	B	R	qₐ

B = blank. Input "001" → writes "111" → halts in accept state qₐ.

Universal TM

Universal Turing Machine (UTM)

A Universal Turing Machine is a TM that can simulate any other TM. It takes as input the description of a TM and its input, then simulates it.

The UTM is the theoretical foundation of general-purpose computers

Modern CPUs act as UTMs — they execute any program stored as data

Programs stored in memory = description of a specific TM

Church-Turing Thesis

The Church-Turing Thesis

"Any computation that can be performed by any algorithmic process can be performed by a Turing machine."

This is a thesis, not a proven theorem — it cannot be proved formally

Defines the concept of computability — what problems can in principle be solved by algorithms

A problem is computable if a Turing machine can solve it

Some problems are uncomputable — no TM can solve them (e.g. Halting Problem)

TM vs FSM

Turing Machine vs Finite State Machine

FSM

Read-only on tape

Move only right

Finite memory

Recognises Type 3 (regular)

TURING MACHINE

Read AND write on tape

Move left or right

Infinite tape = unlimited memory

Recognises Type 0 (all computable)

Importance

Why Turing Machines Matter

Established the theoretical basis for all of computer science

Defined what computation IS — before any physical computer existed

Led to understanding of limits of computation (what cannot be computed)

The UTM concept led to stored-program computers (von Neumann architecture)

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

(a) State FOUR components of a Turing machine. [4]
(b) Explain what is meant by a Universal Turing Machine. [2]
(c) State what the Church-Turing thesis claims. [1]

[7 marks]

4 marks

(a) Any 4 from: infinite tape / read-write head / finite set of states / transition function / start state / accept state / reject state / tape alphabet

2 marks

(b) A TM that can simulate any other TM by taking the description of that TM and its input as data on its tape, then executing it

1 mark

(c) Any computation that can be performed algorithmically can be performed by a Turing machine

Summary

Key Points to Remember

Turing machine — tape, head, states, transition function (state, read) → (write, move, new state)

Universal TM — simulates any TM; theoretical basis for general-purpose computers

Church-Turing thesis — anything computable can be computed by a TM

TM > FSM — can read/write, move both ways, unlimited memory

Some problems are uncomputable — no TM can solve them

🎉 Lesson complete — move to the quiz!