Computability and complexity
Turing machines, the most powerful model of computation; the halting problem and other problems no program can solve; and P, NP and NP-completeness, the limits of efficient computation.
About 5 hours of study
Learning objectives
- Design and simulate Turing machines
- Prove undecidability by diagonalisation and reduction
- Explain P, NP, certificates and NP-completeness
Lessons
- 1
Turing machines Advanced
A Turing machine has a finite control and an unlimited tape it can read, write and move along in both directions. Build a simulator in Python, write a machine that adds 1 to a binary number, and see why this simple model captures every computation.
- 2
Decidability and the halting problem Advanced
Some problems cannot be solved by any program at all. Learn the difference between deciding and recognising, follow Turing's diagonal argument that no program can decide whether programs halt, and see in Python why simulation alone cannot settle it.
- 3
P, NP and NP-completeness Advanced
Some problems are easy to check but seem hard to solve. Learn the classes P and NP, certificates and verifiers, why SAT is NP-complete, and what the P vs NP question asks, with subset sum and SAT in Python.
Module practice
- Theory: A machine that flips bitsEasy
- Theory: Run any Turing machineMedium
- Theory: Watch a Turing machine workHard
- Theory: Halting within a step limitEasy
- Theory: Diagonalise a tableMedium
- Theory: Run programs with a step limitHard
- Theory: Check a certificateEasy
- Theory: Does an assignment satisfy the formula?Medium
- Theory: Solve SAT by brute forceHard