Direkt zum Inhalt

Lexikon der Mathematik: Theorie der Unlösbarkeitsgrade

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos