Warum bedeuten viele zu einer Reduktion Turing-Reduzierbarkeit?

So, (viele zu einer Reduktion), dass Sprache auf Sprache reduziert werden kann , wenn es existiert eine Turing-berechenbare Funktion so und . $A\leqslant_mB$ $A$ $B$ $f$ $f(A) \subseteq B$ $f(\overline{A}) \subseteq \overline{B}$

$A\leqslant_TB$ (Turing-Reduzierbarkeit) bedeutet, dass Sprache auf Sprache Turing-reduziert werden kann, wenn eine Orakelmaschine die über entscheidet . $A$ $B$ $O^B$ $A$

Ich Art sie beide einzeln, aber ich verstehe nicht , warum impliziert . $\leqslant_m$ $\leqslant_T$

computability reductions FOKDIEKUL
quelle

Betrachten . dann haben Sie diese Turing-berechenbare Funktion mit dieser Eigenschaft. Betrachten Sie nun ein Wort . Wir wollen entscheiden , ob . Aber dann können wir nur prüfen , ob . Das liegt daran , wenn , dann wissen wir , dass und wenn dann wissen wir , dass daher die Funktion im Grunde ist das Orakel Maschine , die Sie benötigen um zu bestimmen .

A \leq_{m} B

$A \leq_m B$

f

$f$

w

$w$

w \in A

$w \in A$

f (w) \in B

$f(w) \in B$

w \in A

$w \in A$

f (w) \in B

$f(w) \in B$

w \notin A

$w \notin A$

f (w) \notin B

$f(w) \notin B$

f

$f$

O^{B}

$O^B$

A \leq_{T} B

$A \leq_T B$

Bakuriu

Antworten:

Informell ausgedrückt bedeutet "Wenn ich eine Unterroutine für , dann könnte ich lösen ", während bedeutet "Wenn ich hatte eine Unterroutine für , dann konnte ich mit einem Programm lösen , das die Unterroutine nur einmal aufruft und außerdem nur die Antwort der Unterroutine zurückgibt, ohne weitere Berechnungen durchzuführen. " $A\leq_{\mathrm{T}}B$ $B$ $A$ $A\leq_{\mathrm{m}}B$ $B$ $A$

Wenn Sie ein Problem mit einer Unterroutine lösen können, so dass bla bla bla, können Sie dieses Problem mit der Unterroutine lösen.

David Richerby
quelle