Skip to content
Wyatt's Notes — University

Theory of Computation

Theory of Computation

The theory of computation addresses the fundamental question of what can be computed and how efficiently computation can be carried out. It provides the mathematical framework for classifying computational problems by their inherent difficulty and for understanding the capabilities and limitations of different models of computation.

Key Concepts

The Chomsky hierarchy classifies formal languages by the type of automaton that recognises them: regular languages (finite automata), context-free languages (pushdown automata), context-sensitive languages (linear-bounded automata), and recursively enumerable languages (Turing machines). Decidability theory identifies problems for which no algorithm can always produce a correct answer, while complexity theory partitions decidable problems into classes such as P\text{P}, NP\text{NP}, and PSPACE\text{PSPACE} based on resource bounds.

Contents

  1. Introduction
  2. Regular Languages
  3. Context-Free Languages
  4. Turing Machines
  5. Decidability
  6. Complexity Theory
  7. Problem Set

Overview

University-level theory of computation notes covering automata, languages, and complexity.

Topics Covered

  • Automata Theory: Finite automata, pushdown automata, Turing machines
  • Formal Languages: Regular expressions, context-free grammars, Chomsky hierarchy
  • Computability: Decidability, reductions, the Halting Problem
  • Complexity Theory: P, NP, NP-completeness, space complexity

Prerequisites

  • Discrete mathematics and logic
  • Mathematical proofs and induction
  • Basic programming experience

How to Use These Notes

Start with automata theory to build foundational knowledge, then progress to computability and complexity. Each section includes worked examples and practice problems.

Use the sidebar to browse topics, or start with the introductory pages linked from the sidebar.

Additional Resources

Each section includes:

  • Detailed explanations of key concepts
  • Worked examples with step-by-step solutions
  • Practice problems with answers
  • Common pitfalls and how to avoid them
  • Connections to other areas of computer science

Study Tips

  1. Master formalism: Theoretical CS requires precise mathematical language
  2. Practice reductions: Learn to reduce problems to prove hardness
  3. Draw automata: Visualise state machines and their transitions
  4. Learn the hierarchy: Understand the relationships between complexity classes
  5. Connect to practice: Relate theory to practical applications (compilers, cryptography)