01
Automata and formal languages
What is the simplest machine that can recognise a pattern?
Advanced · Module 08
Theory of Computation
The limits of the machine, established before the machine existed. Turing and Cook define the boundaries of the whole field.
By the end of this module
You know which problems are impossible, which are merely intractable, and how to tell them apart.
0%0 / 3 complete
02
Turing machines and undecidability
Is there anything a computer provably cannot do?
Primary source★ LandmarkFree
On Computable Numbers, with an Application to the Entscheidungsproblem ↗Alan Turing, 1936
03
P, NP and the Cook–Levin theorem
What does P vs NP actually ask?
Quiz
Not written yet for this module. The lectures above are complete and the module still counts toward your progress.