Por que uma redução de muitos para um implica redutibilidade de Turing?

Assim, $A\leqslant_mB$ (muitos a uma redução) meios que língua pode ser reduzida a língua se existe uma função Turing-calculável assim e . $A$ $B$ $f$ $f(A) \subseteq B$ $f(\overline{A}) \subseteq \overline{B}$

$A\leqslant_TB$ (Turing reducibilidade) meios que língua pode ser Turing-reduzido a língua se existe uma máquina do Oracle que decide . $A$ $B$ $O^B$ $A$

Eu meio que os pego individualmente, mas não entendo por que implica . $\leqslant_m$ $\leqslant_T$

computability reductions FOKDIEKUL
fonte

Considere . então você tem essa função computável de Turing com essa propriedade. Agora considere uma palavra . Queremos decidir se . Mas então nós podemos apenas verificar se . Isso porque se , sabemos que e se , sabemos que portanto, a função basicamente é a máquina oracle que você precisa para determinar .

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 30/08/16

Respostas:

Para colocar informalmente, significa "Se eu tivesse uma sub-rotina para , então eu poderia resolver ", enquanto significa: "Se eu tinha uma sub-rotina para , então eu poderia resolver usando um programa que chama a sub-rotina apenas uma vez e, além disso, apenas retorna a resposta da sub-rotina sem fazer nenhum cálculo adicional ". $A\leq_{\mathrm{T}}B$ $B$ $A$ $A\leq_{\mathrm{m}}B$ $B$ $A$

Se você puder resolver um problema usando uma sub-rotina, como blá, blá, blá, poderá resolver esse problema usando a sub-rotina.

David Richerby
fonte