Turing-Reduzierbarkeit impliziert Mapping-Reduzierbarkeit

Die Frage ist, ob die folgende Aussage richtig oder falsch ist:

$A \leq_T B \implies A \leq_m B$

Ich weiß, dass es bei ein Orakel gibt, das A relativ zu B entscheiden kann. Ich weiß, dass dies nicht ausreicht, um zu sagen, dass es eine berechenbare Funktion von A nach B gibt, die die Reduktion erfüllen kann.$A \leq_T B$

Ich weiß nicht, wie ich das richtig ausdrücken soll oder ob das, was ich sage, ausreicht, um zu sagen, dass die Aussage falsch ist. Wie würde ich das zeigen?

EDIT: Dies ist an sich kein Hausaufgabenproblem, ich überprüfe es für einen Test. Wo $\leq_T$ ist Reduzierbarkeit Turing und $\leq_m$ ist Mapping Reduzierbarkeit .

Die Aussage ist falsch.

Say B ist das Halteproblem und $A = \overline B$ . Dann können wir angesichts des Orakels des Halteproblems leicht über dessen Ergänzung entscheiden.

Es ist jedoch nicht wahr, dass seit und aber beide sind unentscheidbar (dh wenn wahr ist, dann ist sowohl in als auch in , was ein Widerspruch ist).$A \le_m B$$B\in RE$$A\in coRE$$A \le_m B$$B=HP$$RE$$coRE$$B\in R$

Es ist falsch: nimm und sein Komplement.$Diag = \{\langle M \rangle \mid M \notin L(M) \}$

Im kann verwendet werden, um ein Problem auf sein Komplement zu reduzieren, während dies nicht kann.$\leq_T$$\leq_m$

Wenn Sie mehr Arten von Reduktionen und Beispiele sehen möchten, die sich unterscheiden, empfehle ich einen Blick auf "Classical Recursion Theory" von Odifreddi.

Es gibt eine allgemeine Tatsache, dass jeder nicht berechenbare Turing-Grad unendlich viele verschiedene Grad enthält .$m$

(Dieses Ergebnis folgt zumindest aus den Ergebnissen von Jockusch, "Beziehungen zwischen Reduzierbarkeiten", Trans. Amer. Math. Soc. 142 (1969), 229-237. Es könnte vorher bekannt gewesen sein.)