How to revise Theory of Computation
Theory of Computation questions reward clear reasoning as well as a final answer. This revision guide is a starting point for using the available papers; it is not the official syllabus or a promise about future exams.
Revision focus
Automata; formal languages; grammars; computability; reductions
Useful prior knowledge
Sets, functions, logic and proof techniques
Common mistakes
Confusing a language with a machine recognising it or reversing a reduction
Use these papers effectively
State the language precisely. For a construction, explain the machine’s invariant; for an impossibility claim, specify the reduction direction. After checking a solution, solve the question again without looking and record the specific step you missed.
Revision guidance only. Check your current official course materials for the assessed syllabus.