Theory of Computation

What machines must remember, what they can decide, and at what cost

About this course

Models of computation and their limits — finite automata and regular languages, grammars and pushdown automata, Turing machines and undecidability, and time and space complexity through P, NP and NP-completeness.

What you will be able to do

  • Construct DFAs and NFAs, convert between automata and regular expressions, and minimize a DFA
  • Prove a language nonregular, and design grammars and pushdown automata for context-free languages
  • Design a Turing machine and distinguish deciders from recognizers
  • Prove problems undecidable by diagonalization and reduction
  • Show a problem is in NP and prove it NP-complete with a polynomial reduction

What this course covers

  • Equal-Arm Language: Soundness and Completeness Proof
  • Context-Free Grammar: Formal Definition
  • Balanced Parentheses Grammar and Height Predicate
  • Parse Trees vs. Derivation Schedules
  • Grammar Ambiguity
  • CYK-Style Chart Membership Algorithm
  • Closing Summary: Grammars, Trees, and Derivations Distinguished
  • Strings, alphabets, and languages
  • Relevant memory and suffix summaries
  • Deterministic finite automaton (DFA) definition and construction
  • Invariant proof of DFA correctness
  • Deterministic runs merging on shared state
  • Memory lower bound via distinguishing continuations
  • Counting accepted strings and diagnosing broken transitions
  • Turing Machine Configuration and Simulation Basics
  • The Halting Language: Definition and Scope
  • Fixed-Timeout Counterexample and Its Limits
  • Diagonalization on a Finite Boolean Table
  • Machine Descriptions as Input Data (Self-Input)
  • The Diagonal Machine D and the Halting Contradiction
  • Repeated Configurations and Proofs of Non-Termination
  • Halt TM Is Recognizable but Undecidable; Its Complement Is Not Recognizable
  • Turing Machine model and tape mechanics
  • Configuration as complete machine memory
  • Equality-testing machine design
  • Round invariant and correctness proof
  • Termination proof and halting vs. non-halting distinction
  • Two tape representations and their equivalence
  • Scope of testing vs. formal proof; outlook
  • Resource functions and worst-case time
  • Exact transition ledger via loop invariant
  • Upper vs. lower bounds and algorithm vs. language complexity
  • Asymptotic notation (Big-O and Theta)
  • Reusable space and the time–space distinction
  • Amortised bit-flip cost of a binary counter
  • Encoding size and its effect on complexity claims
  • Multi-tape to single-tape simulation overhead
  • Certificates and the Verifier Model
  • Clique Certificate: Encoding, Soundness, and Completeness
  • The Class P and Deterministic Reachability
  • The Class NP via Bounded Certificates
  • Equivalence of Certificates and Non-Deterministic Polynomial Time
  • SAT as an NP Certificate Example
  • P ⊆ NP, the P vs NP Question, and co-NP
  • Recognizers, deciders, and recognized languages
  • Mapping (many-one) reductions
  • Undecidability of the acceptance language
  • Wrapper language behavior table
  • Undecidability and unrecognizability of emptiness and non-emptiness
  • Unrecognizability of language equality and inequality
  • Diagnosing faulty reductions and proof-graph summary
  • Equal-arm recogniser for language H: stack invariant and correctness proof
  • Pushdown automaton: definition and configuration
  • Typed nested bracket recognition
  • Marked and unmarked palindrome recognition; non-deterministic branching
  • Grammar-to-pushdown compiler
  • Pushdown-to-grammar reverse correspondence
  • Simulator behaviour: accept, reject, and unknown
  • Two-property intersection language definition
  • Pattern-progress DFA for containing 101
  • Parity DFA for even zero count
  • Product (cross-product) construction
  • Inductive correctness proof for the product DFA
  • Reachability vs. minimality of product states
  • Closure under union, complement, and the totality requirement
  • Recognizers vs. Deciders: Formal Obligations
  • Observation Limits and Evidence Types
  • Decidability Is a Language Property, Not a Machine Property
  • Self-Delimiting Integer Encoding
  • Machine Description Encoding and Unique Parsing
  • Faithful Simulation and the Acceptance Problem
  • Fair Interleaving of Complementary Recognizers Yields a Decider
  • Nondeterministic finite automaton (NFA) definition
  • Nondeterministic acceptance as an existence claim
  • Epsilon transitions and epsilon closure
  • Subset (powerset) construction
  • Invariant meaning of subset states (recent-bit interpretation)
  • Reachable vs. possible subsets and NFA–DFA equivalence
  • Correctness proof of the subset construction
  • NP membership and polynomial verifiability
  • The 3-SAT-to-Clique occurrence graph construction
  • Polynomial-time many-one reductions
  • NP-hardness, NP-completeness, and the 3-SAT foundation
  • Correctness proof: 3-SAT ↔ Clique equivalence
  • Auditing the construction: size bounds and broken-rule counterexamples
  • Clique to Vertex Cover via graph and set complementation
  • Alphabet, words, languages, and epsilon distinctions
  • Regular expression syntax, scope, and language semantics
  • Fragment compiler: expressions to epsilon-NFA
  • Structural induction proof of compiler correctness
  • Small four-state machine and two-direction path argument
  • State elimination and recovery of a regular expression
  • Equivalence checking via reachable pair graph search
  • Three diagnostic questions for classifying machines
  • Typed stack invariant for nested bracket language
  • Context-free grammar equivalence for bracket language
  • Finite automaton construction for depth-capped bracket language
  • Distinguishing suffixes prove state minimality and non-regularity
  • Polynomial reduction from equal-block language to bracket language
  • Course map: memory, halting, and resource classification
  • Distinguishability of input histories
  • State invariant and reachability in the mod-3 machine
  • Partition refinement and quotient minimization
  • Three-state lower bound and minimality proof
  • Myhill–Nerode future-equivalence classes
  • Unbounded distinguishable prefixes and non-regularity of H
  • Pumping lemma and its correct application

Syllabus

  1. Finite Automata and Regular Languages

    1. L1 · What Must a Machine Remember?
    2. L2 · Regular Languages and DFA Construction
    3. L3 · Nondeterminism and Subset Construction
    4. L4 · Regular Expressions and Automata
    5. L5 · Minimal Machines and Nonregular Languages

  2. Grammars and Pushdown Automata

    1. L6 · Grammars, Derivations, and Parse Trees
    2. L7 · Pushdown Automata and Stack Memory

  3. Turing Machines and Decidability

    1. L8 · Turing Machines: A General Model
    2. L9 · Deciders, Recognizers, and Encodings

  4. Undecidability

    1. L10 · The Halting Problem and Diagonalization
    2. L11 · Reductions and Undecidable Problems

  5. Complexity

    1. L12 · Measuring Time and Space
    2. L13 · P, NP, and Efficient Verification
    3. L14 · NP-Completeness and Polynomial Reductions
    4. L15 · A Map of What Computation Can Do