Theory of Computation

Mort Yao

Textbook:

  • Michael Sipser. Introduction to the Theory of Computation, 3rd edition.

Supplementary reading:

  • Neil Jones. Computability and Complexity: From a Programming Perspective.

1 Languages and Automata

1.1 Formal Language and Automaton

Formal definition of a language.

1.2 Regular Language

1.3 Context-Free Language

2 Computability

2.1 Church-Turing Thesis

2.2 Automata Theory and Models of Computation

2.2.1 Turing Machine

2.2.2 Pushdown Automaton (PDA)

2.2.3 Finite State Machine (FSM)

2.2.4 Combinational Logic

2.2.5 λ-Calculus

2.2.6 Recursive Function

2.2.7 Combinatory Logic

2.2.8 Cellular Automaton

2.2.9 Abstract Rewriting System

2.3 Algorithm

2.4 Decidability

2.4.1 Undecidability

2.5 Reducibility

2.5.1 Many-One Reduction

2.5.2 Turing Reduction, Turing Equivalence and Turing Degree

3 Complexity

3.1 Time Complexity

3.1.1 NP-Completeness

3.2 Space Complexity

3.3 Intractability

3.4 Advanced Topics

3.4.1 Approximation Algorithms

3.4.2 Probabilistic Algorithms

3.4.3 Alternation

3.4.4 Interactive Proof Systems

3.4.5 Parallel Computation

3.4.6 Cryptography