Turing Computability: Theory and Applications
by Robert I. Soare
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.
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.
Computability and Logic (5th Edition)
The mathematical-logic counterpart to Sipser: Turing and abacus machines, recursive functions, Church's thesis, uncomputability, undecidability of first-order logic, Godel's theorems and second-order logic, in short self-contained chapters with proofs worked in full.