Turing riducibilità implica mappatura riducibilità

Question

La questione è se la seguente dichiarazione è vera o falsa:

$ A \ leq_T B \ implica A \ B leq_m $

So che se $ A \ B leq_T $ poi c'è un oracolo che può decidere Un parente a B. So che questo non è sufficiente per dire che esiste una funzione calcolabile da A a B che può soddisfare la riduzione .

Non so come parola questo in modo corretto o se quello che sto dicendo è sufficiente dire che l'affermazione è falsa. Come potrei fare per mostrare questo?

EDIT: Questo non è un problema di per sé compiti a casa, sto rivedendo per un test. Dove $ \ leq_T $ è Turing riducibilità , e $ \ leq_m $ è mappatura riducibilità

Answer 1

L'affermazione è falsa.

Say B è il problema della terminazione e $ A = \ overline B $. Poi, data Oracle per il problema della terminazione si può facilmente decidere il suo complemento.

Tuttavia non è vero che $ A \ le_m B $ dal $ B \ in RE $ e $ A \ Core $ ma entrambi sono indecidibile (vale a dire, se $ A \ le_m B $ era vero, allora $ b = HP $ è sia in $ RE $ e $ CORE $, cioè, $ B \ in R $ che è una contraddizione).

Answer 2

E 'falso:. Prendere $ Diag = \ {\ langle M \ rangle \ metà M \ notin L (M) \} $ e il suo complemento

In generale $ \ leq_T $ può essere utilizzato per ridurre un problema per il suo complemento, mentre $ \ leq_m $ non possono.

Se vuoi sapere vedere più tipi di riduzioni e gli esempi che sono diversi Suggerisco di avere uno sguardo "teoria della ricorsione classica" di Odifreddi.

Answer 3

C'è un fatto generale che ogni grado di Turing non computabili contiene infiniti distinto $ m $ -degrees.

(Questo risultato segue almeno dai risultati di Jockusch, "Le relazioni tra riducibilità", Trans. Amer. Math. Soc. 142 (1969), 229-237. Si sarebbe potuto conosciuto prima.)