Theory of Computation
by Dexter C. Kozen · Dexter C. Kozen
Kozen's graduate-level text organized as short lectures on automata, computability and complexity, including Turing machines, undecidability, the recursion theorem, NP-completeness, PSPACE and randomized and interactive computation, with exercises. It prepares readers for research-level theory coursework.
This link may earn us a small commission at no extra cost to you. Affiliate disclosure
More resources on Computability
Wolfram MathWorld
MathWorld is an online mathematics encyclopedia from Wolfram Research offering detailed, browsable articles on topics across the math spectrum, including algebra, geometry, calculus, and number theory. Each entry includes definitions, theorems, formulas, diagrams, worked examples, and links to further reading.
plato.stanford.edu
The Stanford Encyclopedia of Philosophy is a peer‑reviewed online encyclopedia of philosophy featuring in‑depth, scholarly articles written and regularly updated by experts, including comprehensive coverage of logic topics.
Stanford Encyclopedia of Philosophy: Computability
Neil Immerman's Stanford Encyclopedia of Philosophy entry on computability and complexity. It covers Turing machines, the halting problem, recursively enumerable sets and complexity classes such as P and NP, explaining their significance for logic and philosophy of mind.
nLab Computability
nLab wiki entry on computability, relating Turing machines, partial recursive functions, and realizability to type theory and category theory. Useful for readers who already know basic computability and want to see how it connects to constructive mathematics and topos theory.
Theory of Computation (MIT 18.404J)
Sipser's course on automata, computability and complexity: regular and context-free languages, decidability, reducibility, the recursion theorem, time and space complexity, NP-completeness, hierarchy theorems, probabilistic computation and interactive proofs. 25 lecture videos, slides, problem sets and exams support rigorous proof-based study.
Turing Computability: Theory and Applications
Soare's graduate reference on classical computability: computably enumerable sets, Turing reducibility and the degrees of unsolvability, the priority method, the arithmetical hierarchy and oracle constructions, with historical commentary on Turing's and Post's programmes.