The Foundations of Computability Theory

From Mathematical Crisis to the Theory of Computation

Computability theory asks a disarmingly simple question: what can be computed? The answer, as Borut Robič shows, grows out of one of the most dramatic periods in modern mathematics. This second edition traces the conceptual journey from the paradoxes that shook set theory around 1900, through Hilbert’s program and Gödel’s incompleteness theorems, to the precise models of computation developed by Church, Turing, and their contemporaries.

Rather than presenting the subject as a wall of definitions and theorems, Robič connects each formal idea to the problem that motivated it. The result is a coherent, historically grounded introduction that helps readers see why computability theory took its particular shape.

Three Parts, One Clear Progression

The book is organized into three parts that move from informal algorithm to relative computability:

• Part I: The Origins — The intuitive concept of an algorithm, the foundational crisis in mathematics, formal axiomatic systems, and Hilbert’s program.
• Part II: Classical Computability — Competing formal models of computation, the Turing machine, universal machines, undecidability, and the Halting Problem.
• Part III: Relative Computability — Oracles, Turing reductions, Turing degrees, the jump operator, priority methods, and the arithmetical hierarchy.

Built for Clarity and Guided Study

Robič uses a two-level presentation: a fast track gives the essential narrative, while boxed detours provide detailed proofs, extra historical context, and more advanced material. This structure allows both first-time learners and those with some background to read at the depth they need.

The second edition also adopts contemporary terminology—computable functions, computably enumerable sets, partial computable functions—and includes a short route to relative computability for readers eager to reach the later chapters quickly.

Who Will Find This Useful

Undergraduate and beginning graduate students in computer science or mathematics will find a rigorous but readable foundation. Researchers working at the intersections of computer science, physics, biology, linguistics, and analytic philosophy can also use it to understand the limits of computation and the structure of unsolvable problems.

No previous course in computability is required, though some exposure to elementary logic helps. The appendix reviews the necessary set theory and algebra.

For anyone curious about what computation means at the deepest level, this is a thoughtful, carefully organized starting point. 🧠💻