チューリングの削減は、マッピングの削減を意味します

Question

問題は、次のステートメントが真か虚偽かどうかです。

$ a leq_t b は leq_m b $を暗示しています

$ a leq_t b $の場合、Bとの関係を決定できるOracleがあることを知っています。これは、減少を満たすことができるAからBまでの計算可能な関数があると言うのに十分ではないことを知っています。

適切な方法でこれをどのように表現するか、または私が言っていることが声明が間違っていると言うのに十分であるかどうかはわかりません。これを見せるにはどうすればよいですか？

編集：これは宿題の問題ではなく、テストのためにレビューしています。ここで、$ leq_t $は チューリングの削減, 、および$ leq_m $はです マッピングの削減.

Answer 1

声明は偽です。

bは停止問題であり、$ a = overline b $です。次に、停止問題のOracleを考えると、その補完を簡単に決定できます。

ただし、$ a le_m b $は$ b in re $ in in re $ an、$ a in core $ on core $であるが、どちらも決定不可能です（すなわち、$ a le_m b $がtrueである場合、$ b = hp $は$ re $と$ core $、つまり$ b in r $の両方が矛盾です）。

Answer 2

それは偽です：$ diag = { langle m rangle mid m notin l（m）} $およびその補数を取得します。

通常、$ leq_t $を使用して問題を補完することができますが、$ leq_m $はできません。

知りたい場合は、より多くの種類の削減とそれらが異なっているという例をご覧になりたい場合は、Odifreddiによる「古典的な再帰理論」を見ることをお勧めします。

Answer 3

すべての非計算不可能なチューリングの学位には、無限に多くの異なる$ m $ -degreesが含まれているという一般的な事実があります。

（この結果は、少なくともJockuschの結果、「削減の関係」、Trans。Amer。Math。Soc。142（1969）、229-237の結果から続きます。それはその前に知られていたかもしれません。）