--- title: Computability description: Computability theory studies which mathematical problems can be solved using an algorithm. You will understand the limits of computation through models like Turing machines, explore the halting problem, and distinguish between decidable and undecidable problems. category: mathematics subcategory: mathematical-logic difficulty: beginner, intermediate, advanced url: /subject/computability --- # Computability Computability theory studies which mathematical problems can be solved using an algorithm. You will understand the limits of computation through models like Turing machines, explore the halting problem, and distinguish between decidable and undecidable problems. ## Available Resources 4 Books • 1 Courses • 5 Websites • 1 Papers ## Websites ### 1. 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. **Difficulty:** Beginner | **Price:** Free **Link:** https://plato.stanford.edu/entries/computability/ **Tags:** computability, turing-machines, halting-problem, computational-complexity, philosophy-of-computation ### 2. 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. **Difficulty:** Beginner | **Price:** Free **Link:** https://ncatlab.org/nlab/show/computability **Tags:** computability, category-theory, type-theory, realizability ### 3. Incompleteness and Computability: An Open Introduction to Godel's Theorems **Author:** Richard Zach Richard Zach's free open textbook takes the logician's route: recursive functions, arithmetization of syntax, representability in Q, a computability chapter through Rice's theorem, both incompleteness theorems, models of arithmetic and the lambda calculus. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://ic.openlogicproject.org/ **Tags:** godel-incompleteness, recursive-functions, computability, lambda-calculus, open-textbook ### 4. Wolfram MathWorld **Author:** Eric W. Weisstein 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://mathworld.wolfram.com **Tags:** mathematics-reference, encyclopedia, abstract-algebra, number-theory, geometry ### 5. 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://plato.stanford.edu **Tags:** websites, mathematics-statistics, discrete-math ## Courses ### 1. Theory of Computation (MIT 18.404J) **Author:** Michael Sipser 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. **Difficulty:** Intermediate | **Price:** Free **Link:** https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/ **Tags:** automata-theory, computability, decidability, complexity-theory, np-completeness ## Books ### 1. Turing Computability: Theory and Applications **Author:** 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. **Difficulty:** Advanced | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/3642319327?tag=edmonddante07-20 **Tags:** computability, recursion-theory, turing-degrees, priority-method, arithmetical-hierarchy ### 2. Computability and Logic (5th Edition) **Author:** George S. Boolos, John P. Burgess, Richard C. Jeffrey 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. **Difficulty:** Advanced | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/0521701465?tag=edmonddante07-20 **Tags:** computability, mathematical-logic, recursive-functions, godel-incompleteness, undecidability ### 3. Introduction to the Theory of Computation (3rd Edition) **Author:** Michael Sipser Sipser's standard text builds automata, Turing machines, decidability, reducibility, Rice-style arguments and complexity from careful definitions and complete proofs. After it you can prove a problem undecidable by reduction and state the Church-Turing thesis precisely. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/113318779X?tag=edmonddante07-20 **Tags:** automata-theory, turing-machines, decidability, computational-complexity, formal-languages ### 4. Theory of Computation **Author:** 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/1846282977?tag=edmonddante07-20 **Tags:** books, mathematics-statistics, mathematical-logic ## Papers ### 1. On Computable Numbers, with an Application to the Entscheidungsproblem (1936) **Author:** Alan M. Turing The founding paper. Turing defines his machines, builds a universal machine, proves by diagonalisation that no machine decides halting, and settles Hilbert's Entscheidungsproblem negatively. Reading it shows where every later definition of computability came from. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf **Tags:** turing-machines, halting-problem, entscheidungsproblem, universal-machine, history-of-computing --- *This content is part of Dantes.io - Your Treasure Map to Knowledge* *Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).* View this page online: https://dantes.io/subject/computability