Eine Beziehung zwischen Entscheidungsproblemen (Mengen) A und B, wobei A turing-reduzierbar auf B ist, wenn es eine Turingmaschine gibt, die die Zugehörigkeit zu A entscheidet, wenn sie ein Orakel für B hat; äquivalent: A ist relativ zu B berechenbar.

Prinzip

Die grundlegende Idee ist der Zugang zu B als Orakel: die Maschine darf adaptive Anfragen zur Zugehörigkeit in B stellen und die Antworten nutzen, um A zu entscheiden; relative Berechenbarkeit erlaubt Interaktion statt einer einzelnen uniformen Übersetzung.

Demonstration

Ein typisches Beispiel ist, dass das Halteproblem H turing-reduzierbar ist, wenn ein Orakel für eine passende Menge O bestimmte konstruktive Anfragen beantwortet, die eine Simulation ermöglichen; konkreter reduzieren viele unentscheidbare Mengen auf H mittels Orakelmaschinen, die Anfragen adaptiv basierend auf früheren Antworten stellen.

Fehlanwendung

Den Begriff so zu verwenden, dass er eine einmalige berechenbare Transformation (many-one) impliziert, oder adaptive Anfragen nicht zuzulassen — also Turing-Reduzierbarkeit zu behaupten, wo nur nicht-adaptive Reduktionen existieren — oder die Ressourcenbeschränkungen der Modelle zu übersehen.

Konsequenz

Gilt A ≤_T B, dann liefert jede Orakelprozedur für B durch Nutzung des Orakels eine Prozedur für A; die Relation induziert Turing-Grade, die Mengen nach relativer Berechenbarkeit klassifizieren, und bildet die Grundlage für Relativierungsergebnisse in der Berechenbarkeitstheorie und Komplexitätstheorie.

Umkehrung

Kehrt man die Reduktion um (B ≤_T A), ändert sich, welches Problem als Orakel dient; wechselseitige Turing-Reduzierbarkeit ergibt Turing-Äquivalenz und gemeinsamen Grad, während eine einseitige Reduktion nur relative Berechenbarkeit von A durch B zeigt.

Abgrenzung

Gilt für klassische Rechenmodelle mit Orakelzugang; schließt in unbeschränkter Weise nicht-uniforme Reduktionen aus, und Unterschiede treten auf, wenn man Ressourcenbeschränkungen wie polynomiellen Zeitaufwand einführt, die die Notion verfeinern (z. B. p-Turing-Reduzierbarkeit).

Semantische Spannung

Turing-Reduzierbarkeit liegt zwischen many-one-Reduzierbarkeit (stärker, nicht-adaptiv) und schwächeren Notionen wie truth-table-Reduzierbarkeit; sie steht auch im Gegensatz zu logischen Interpretierbarkeitsbegriffen, da Turing-Reduzierbarkeit computationell statt syntaktisch oder modelltheoretisch ist.

Synthese

Turing-Reduzierbarkeit fasst relative Berechenbarkeit durch Orakelzugang zusammen: eine Entscheidungsprozedur für A kann durch eine Maschine realisiert werden, die adaptiv ein Orakel für B abfragt, wodurch Äquivalenzklassen (Turing-Grade) entstehen, die gegenseitige Berechenbarkeitsbeziehungen repräsentieren.