Under construction. This area is a framework being built: most courses have no teaching material yet, and things may change or break. Private self-study. Not an official programme and not recognised by any ministry or school. No qualification, mark or document is issued, and “years 1 to 3” and “advanced” are names of study paths only.
U04 Computability & complexity
Years 1 to 3 pathU: Years 1 to 3 electivesplannedabout 120 h (planning estimate)
Draft lectures and exercises are available for this course. They were written by AI and checked by a second AI; no person has reviewed them yet. Use them as a study aid, not as an authority.
Named in: Years 1 to 3 pathway
Why this course
What can and cannot be computed, and at what cost; matches Sipser-style teaching.
Prerequisites
Concept-level units
Units follow the syllabus order, as a recommended sequence rather than a gate.
- Finite automata
- Context-free languages
- Turing machines
- Decidability and recognizability
- Reductions
- Complexity and NP-completeness
Assessable outcome
Construct machines and reductions and distinguish theorems from open complexity questions.
Assessment design
- topic exercises
- mixed problem sets
- unseen proof or derivation problems
- cumulative examination
cumulative; uses spaced retrieval
Resources
Every title here is candidate, unverified unless marked verified. Titles were suggested while planning. Nobody has checked that they exist, what they cost or how they are licensed.
- Sipser · Introduction to the Theory of Computation
Content record
- Version
- 0.0.0
- Review
- no review of any kind
- Provenance
- catalogue imported from the owner brief of 29 Oct 2026; no teaching content authored
- Known issues
- none recorded
- Type
- course
Bridges and laboratories
- Laboratory: Automata, simulations, distinguishability, reduction builders planned Finite testing is not a proof of undecidability/nonregularity
You and this course
Reading your plan on this device…