Grad-Theorie, Turing-Grad-Theorie, befaßt sich mit der Struktur der Turing-Grade.

Diese bilden einen oberen Halbverband bzgl. der Relation ≤_T (Orakel-Turing-Maschine). Zu je zwei Turing-Graden existiert immer eine kleinste obere Schranke, nicht notwendigerweise aber eine größte untere Schranke. Das kleinste Element dieser Struktur bildet der Turing-Grad der entscheidbaren Mengen (Entscheidbarkeit).

Ferner existieren minimale Paare von Turing-Graden, deren größte untere Schranke der Turing-Grad der entscheidbaren Mengen ist.