Computability Theory

Turing machines, recursive functions, and the arithmetic hierarchy.

foundation tier

Computability Theory. Turing machines, recursive functions, and the arithmetic hierarchy. This page collects canonical references that organise the subject and provide entry points to its main techniques.

Foundations and canonical references

The standard treatments of computability theory approach the subject from complementary angles. Cooper, Computability Theory (2004) is the anchor reference for the subject and lays out the core definitions, theorems, and worked examples that practitioners return to. Rogers, Theory of Recursive Functions and Effective Computability (1987) provides historical context and an early systematic exposition of the material.

Open methodological questions for computability theory include sharpening the bridges between foundational theory and computational practice, extending classical results to broader or more structured settings, and integrating the techniques surveyed above with adjacent mathematical disciplines. The references listed in this page are the entry points that current work builds on.

Prerequisites

Sources

  • textbook · primary · 2004
    Computability Theory
    cooper-2004
  • textbook · historical · 1987
    Theory of Recursive Functions and Effective Computability
    rogers-1987

In context

Where this topic sits in the prerequisite graph. Click any node to jump.

Open in full atlas →

Explore

  1. 01

    Degrees of Unsolvability

    Turing degrees, the Friedberg–Muchnik theorem, and priority arguments.
  2. 02

    Reverse Mathematics

    Calibrating proof strength via subsystems of second-order arithmetic.

Review this topic

This page was drafted by an agent and is waiting on expert review. Spotted a wrong prerequisite, a missing concept, a misattributed source, or a factual slip? Tell us — your review opens a tracked issue maintainers act on.