Turing-Reduzierbarkeit

- Natural & Formal Sciences -
Mathematics & Logic Dictionary
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.