Turing machines and computability: trace a machine and recognise the limits
AQA's theory content separates the cost of a solution from whether a general algorithm exists. Use an original binary-increment machine to make the formal model concrete, then connect it to complexity and the halting problem.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
The idea to start with
A Turing machine has finitely many states and tape symbols, a read/write head and an unbounded tape. Its transition rule uses the current state and read symbol to determine what to write, which way to move and the next state. A halting state has no outgoing transitions.
Computability asks whether a general algorithm can solve the defined problem; complexity asks how required time or space grows with input size. The halting problem has no general algorithm deciding termination for every program/input pair, even though termination can be established for many particular programs.
AQA 7517 · 4.4.4.1–4.4.4.7, 4.4.5.1
Before you start
Useful foundations
Binary place values
States, transitions and trace tables
Basic Big-O notation and functions
By the end, you should be able to
Represent and hand-trace a simple Turing machine using equivalent transition rules and a diagram.
Explain a universal machine's role in modelling computation.
Interpret function growth, factorial search and time/space comparisons.
Distinguish an inefficient algorithm, an intractable problem and a non-computable problem.
Describe the halting problem's general impossibility without confusing it with a timeout.
Define the tape, symbols and starting point
Tape positions are 0, 1, 2 and so on, without a right-hand limit. Each cell holds one symbol from {0, 1, _}; _ means blank. The head starts at position 0 in state scan; the other states are carry and halt.
The input is non-empty binary text with a leading zero reserved for carrying, then blanks. For example 01011 represents decimal 11. The zero lets the carry finish before the head would move left of position 0.
The simulator rejects inputs violating that precondition. It stores only visited/needed cells and adds blanks when required; the conceptual infinite tape does not mean allocating infinitely many Python list items.
Apply one complete transition
Use δ(current_state, read) = (next_state, write, direction). A table row and a diagram edge express the same transition. Label diagram edges read/write,direction, and give halt no outgoing edges.
For example scan has self-loop 1/1,R; its blank edge to carry is _ / _,L. The state and transition table form the machine’s fixed program; the input bits are its data.
A single Turing-machine step
1
Read
Observe the current state and the symbol beneath the head.
2
Choose the rule
Find the matching table row; it determines the next state, written symbol and direction.
3
Write and move
Replace the symbol, then move the head one square left or right as specified.
4
Change state
Adopt the next state. If it is halt, stop after performing the write and move.
Binary increment transition function; defined convention
Current state
Read
Next state
Write
Move
scan
0
scan
0
R
scan
1
scan
1
R
scan
_
carry
_
L
carry
1
carry
0
L
carry
0
halt
1
R
The transitions implement a binary carry
Scan preserves each digit and moves right to the first blank. The blank rule moves left onto the final digit and enters carry. Carry turns trailing ones into zeros, then changes the first zero to one and halts.
These rules add one to the represented number. They are not arbitrary text substitutions: the changes match the place-value rules of binary addition.
A universal Turing machine reads an encoding of another machine and its input, then simulates its rules. This connects program-as-data with a general-purpose model of computation.
Turing machines formalise what it means to compute a result. Faster hardware or more physical memory changes execution resources; it does not supply a general solution to a non-computable problem.
Compare growth in time and space
Let n count input items, rather than source-code lines. A time function maps size to estimated work: T(n) = 3n² operations can have positive integer sizes as domain and non-negative work counts as co-domain.
Big-O gives an upper growth bound, discarding constants and lower-order terms. State the best, average or worst case and the operation counted. Time and space are separate: faster algorithms may need larger auxiliary structures.
For positive n, examples are constant 1, logarithmic log₂ n, linear n, polynomial n² and exponential 2^n. Doubling n multiplies n² by four, but changes 2^n to (2^n)². Consider growth alongside the actual workload.
Permuting n distinct items gives n! arrangements. Four display panels give 4 × 3 × 2 × 1 = 24 orders; ten give 3,628,800. Exhaustive enumeration grows beyond a simple polynomial; repeated values can reduce distinct permutations.
Classify the problem, then judge practicality
Under AQA’s classification, a problem with a polynomial-or-better time solution is tractable; one without such a solution is intractable. An exponential implementation alone does not establish the problem’s classification: a better method may exist.
Not knowing a polynomial algorithm is not proof that none exists. Conversely, even a polynomial such as n^100 can be impractical. Theoretical classification and completion within available time or memory answer different questions.
For a solvable problem exceeding practical limits, better hardware or an algorithm may help. A heuristic may provide a useful approximation when exact optimisation is too expensive; assess its validity and answer quality separately.
Why a timeout cannot decide the halting problem
The halting problem asks for a procedure that always correctly decides whether any given program terminates on its particular input. No general decider exists. AQA requires the description and significance, rather than a proof.
The limitation concerns a universal procedure. Specific programs can still have termination proofs: decrementing a non-negative integer to zero gives a progress argument, while a deliberate forever loop can be shown not to terminate.
Running an unfamiliar program for an hour without a result proves only that it did not halt within that hour. It might halt later; observing a timeout is not a general halting decision.
Worked example
Hand-trace 01011 before running the simulation
In scan, visit positions 0 through 4 and preserve the digits 0, 1, 0, 1, 1. The head reaches blank position 5.
Read blank at 5, preserve it, move left to 4 and enter carry. The tape still contains 01011.
Carry changes the 1 at position 4 to 0, then the 1 at position 3 to 0. At position 2 it reads 0, writes 1, moves right to 3 and enters halt.
The final finite digit sequence is 01100, decimal 12. There are nine transitions. The tape's blank cells and the final head position are distinct from the numeric result.
Original transition trace; head position before each transition
def increment_machine(bits):
if not bits.startswith("0") or not set(bits) <= {"0", "1"}:
raise ValueError("non-empty binary input with leading zero required")
rules = {("scan", "0"): ("scan", "0", 1),
("scan", "1"): ("scan", "1", 1),
("scan", "_"): ("carry", "_", -1),
("carry", "1"): ("carry", "0", -1),
("carry", "0"): ("halt", "1", 1)}
tape = list(bits) + ["_"]
state, head = "scan", 0
history = []
while state != "halt":
read = tape[head]
next_state, write, movement = rules[(state, read)]
history.append((state, head, read, write, movement, next_state))
tape[head] = write
head += movement
if head < 0:
raise ValueError("left edge of one-way tape")
if head == len(tape):
tape.append("_")
state = next_state
return "".join(tape).rstrip("_"), history
result, history = increment_machine("01011")
print("Result", result)
print("Steps", len(history))
Worked example
Use evidence to classify different claims
A programmer tests every permutation to solve a task. The shown algorithm may take factorial work; that fact alone does not prove every solution to the task must do so.
A correct linear search over a million stored items is computationally solvable but may exceed a particular response deadline. An index or different representation may improve that practical limit.
A proposed tool promises always to decide termination for any submitted program and input. That is a general halting decider, which cannot exist with the promised universal correctness.
An analyser that proves termination for a restricted class of loops and returns unknown otherwise does not make the impossible universal promise. Distinguish an honest partial result from an always-decides claim.
Original A-Level practice
7 original questions total 28 marks. Attempt each before opening the independently written indicative marking guidance.
Question 1
5 marks
Using this transition table, trace input 011. Give the final digits, decimal result, number of transitions and final head position.
Binary-increment machine
Tape positions begin at 0 and extend indefinitely to the right. Put 011 in positions 0–2, with blanks (_) after it. Begin in scan with the head at position 0. Apply the write and move even on the transition into halt; halt has no outgoing rule.
Transition rules
Current state
Read
Next state
Write
Move
scan
0
scan
0
R
scan
1
scan
1
R
scan
_
carry
_
L
carry
1
carry
0
L
carry
0
halt
1
R
Show solution and marking guidance+
Indicative answer
Scan visits the three digits and then blank (1). Carry changes the last two ones to zeros, then the leading zero to one (1). Final digits are 100, decimal 4 (1). There are seven transitions (1), and the final head is position 1 after the last right move (1).
Question 2
4 marks
Express the carry-on-1 rule using this transition-function convention and describe the corresponding diagram edge. Explain why halt has no outgoing edge.
Rule and notation for this question
Use δ(current_state, read) = (next_state, write, direction). When carry reads 1, it writes 0, moves one square left and remains in carry. Halt is the machine's stopping state.
Show solution and marking guidance+
Indicative answer
δ(carry, 1) = (carry, 0, L) (2). Draw a carry self-loop labelled 1/0,L (1). Halt has no outgoing transitions because reaching it ends the computation (1).
Question 3
4 marks
Explain why this binary-increment machine requires a leading zero and how the simulator represents an infinite-right tape using finite memory.
Show solution and marking guidance+
Indicative answer
The zero guarantees a place for the carry to finish (1), preventing movement beyond the one-way tape's left edge (1). The simulator materialises only visited/needed cells (1), extending the finite stored portion with blank cells as needed (1).
Question 4
4 marks
A search tries all arrangements of five distinct items. Calculate how many complete arrangements there are. Explain why this search's cost alone does not prove its problem is intractable.
Show solution and marking guidance+
Indicative answer
5! = 5 × 4 × 3 × 2 × 1 = 120 (2). This describes the chosen exhaustive method (1); a different polynomial-or-better solution might exist, so the problem's classification is not established (1).
Question 5
3 marks
An operation count is T(n) = 7n² + 3n + 8. State its Big-O growth, the change in its dominant term when n doubles, and a practical limitation of calling every polynomial solution efficient.
Show solution and marking guidance+
Indicative answer
O(n²) (1). The dominant quadratic term becomes four times as large (1). A high degree, large constants or the actual input/resource limit can still make a polynomial solution impractical (1).
Question 6
5 marks
Describe the halting problem and distinguish a one-hour timeout from a correct general solution. Explain why proving one decrementing loop terminates does not contradict the limitation.
Show solution and marking guidance+
Indicative answer
It asks whether any given program eventually stops on a particular input (1). No always-correct algorithm decides this for all program/input pairs (1). A timeout establishes only no halt within that period (1); halting may occur later (1). Particular restricted programs can have termination proofs without supplying a universal decider (1).
Question 7
3 marks
Distinguish the fixed increment machine from a universal Turing machine. State why faster hardware does not remove a non-computability result.
Show solution and marking guidance+
Indicative answer
The increment machine follows one fixed transition program (1). A universal machine reads an encoding of another machine and its input to simulate it (1). Faster hardware changes execution cost, not the existence of a general algorithm for a non-computable problem (1).
Specification and references
This guide addresses AQA 7517 4.4.4.1–4.4.4.7, 4.4.5.1. Check your examination year and the complete specification for the assessment scope.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.