# Computability Theory

**Type:** Concept  
**Domain:** foundations-logic  
**Codex URL:** /mathematics/foundations-logic/computability-theory/  
**Entry status:** Live — v1.0 (2026-07-09)

## Summary
Studies which problems are solvable by any algorithm. Turing 1936 halting problem undecidable; Rice's theorem; arithmetical hierarchy; Turing degrees; priority method (Friedberg-Muchnik 1957).

## Sources
- [Tier 1] Turing, A.M. (1936). On computable numbers. Proc. London Math. Soc., 42(1), 230-265.
- [Tier 1] Soare, R.I. (2016). Turing Computability: Theory and Applications. Springer.
- [Tier 2] Sipser, M. (2012). Introduction to the Theory of Computation. 3rd ed.
- [Tier 3] Hodges, A. (1983). Alan Turing: The Enigma.

---
*Mathematics Codex entry v1.0 — added 2026-07-09 — thecodex.expert/mathematics/*