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

Lessons

  1. 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. 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. 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

Module quiz

1. What can a Turing machine do that a pushdown automaton cannot?
2. Which outcome is possible for a Turing machine but not for a DFA?
3. Why can a simulator with a step limit not decide the halting problem?
4. A problem is in NP. What is certainly true?
5. You reduce SAT to your problem X in polynomial time. What have you shown?
6. In the halting proof, what does contrary do on its own description?

‹ Context-free languagesFinal assessment ›