AQA 7517 · Paper 1 · 4.4.4a

The Halting
Problem

Decidability · Undecidability · Turing's proof · Section 4.4

WHAT YOU'LL LEARN

The halting problem · Decidability · Proof by contradiction · Limits of computation

AQA SPEC LINK

4.4.4 — The halting problem and decidability

The Problem

What is the Halting Problem?

Is there an algorithm that, given any program P and any input I, can determine whether P will halt (finish) or run forever?

Some programs run forever (infinite loops). Can we always tell in advance?

Alan Turing proved in 1936: No such algorithm exists

The halting problem is undecidable — no Turing machine can solve it for all cases

Decidability

Decidable vs Undecidable Problems

A problem is decidable if there exists an algorithm that always gives a correct YES/NO answer in finite time. Undecidable = no such algorithm exists.

DECIDABLE EXAMPLES

Is n prime?

Sort a list

Does FSM accept string?

UNDECIDABLE EXAMPLES

Halting problem

Does this program ever output "hello"?

Are two programs equivalent?

Proof

Turing's Proof by Contradiction

Assume there exists a program H(P, I) that solves the halting problem — returns TRUE if P halts on I, FALSE if not.

# Build a paradoxical program D(P):
SUBROUTINE D(P)
  IF H(P, P) = TRUE THEN
    loop forever  # if P halts on itself, loop
  ELSE
    RETURN  # if P loops on itself, halt
  ENDIF
ENDSUBROUTINE

The Paradox

The Contradiction

What happens when we call D(D)? (Pass D to itself)

Case 1: H says D(D) halts → D will loop forever. But D was supposed to halt. Contradiction!

Case 2: H says D(D) loops → D will halt. But D was supposed to loop. Contradiction!

Both cases lead to contradiction → our assumption that H exists must be FALSE. No halting algorithm can exist. ∎

Implications

What This Means for Computing

There are inherent limits to what any computer can compute

Anti-virus software cannot perfectly detect all malware (related problem)

Automated verification of all programs is impossible in general

Many real-world security and verification problems are related to halting-type problems

Relationship to Turing

Halting Problem & Turing's Thesis

The halting problem was proved before physical computers existed. Turing showed some problems are uncomputable — this was the beginning of the theory of computation.

The proof used diagonalisation — a technique also used in maths to prove infinities

Turing's proof inspired Gödel's incompleteness theorems in logic

Real Example

Infinite Loop Example

A simple loop in pseudocode — no algorithm can tell for all programs whether they halt:

# Does this halt? Only if Collatz conjecture is true!
n ← USERINPUT
WHILE n ≠ 1 DO
  IF n MOD 2 = 0 THEN
    n ← n DIV 2
  ELSE
    n ← 3 * n + 1
  ENDIF
ENDWHILE

The Collatz conjecture: we believe this halts for all positive n, but it has never been proved. This illustrates the halting problem in practice.

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

(a) State what is meant by the "halting problem". [2]
(b) State whether the halting problem is decidable or undecidable. Justify your answer. [2]
(c) Describe, in outline, the method Turing used to prove the halting problem is undecidable. [3]

[7 marks]

2 marks

(a) Given any program P and input I, determine whether P will eventually halt (terminate) or run forever on I

2 marks

(b) Undecidable — no algorithm can solve it for all possible programs and inputs

3 marks

(c) Assume H(P,I) exists. Build D(P) that loops if H says P(P) halts, else halts. Run D(D) — either outcome leads to contradiction. Therefore H cannot exist.

Summary

Key Points to Remember

Halting problem — can we decide whether any program halts on any input?

Answer: NO — proved by Turing in 1936 using proof by contradiction

Undecidable — no algorithm can correctly answer YES/NO for all cases

Method — assume H exists; build paradoxical D(D); reach contradiction

Shows there are fundamental limits to computation

🎉 Lesson complete — move to the quiz!