Stanford Encyclopedia of Philosophy: Computability
Unknown
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.
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.
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.
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.