图灵的可还原性意味着绘制可降低性

Question

问题是以下陈述是对还是错：

$ a leq_t b 暗示a leq_m b $

我知道，如果$ a leq_t b $，那么有一个可以决定的甲骨文。我知道这还不足以说出可以从a到b的可计算函数可以满足减少的功能。

我不知道如何以正确的方式或我所说的话说话足以说陈述是错误的。我将如何展示这个？

编辑：这本身不是家庭作业问题，我正在审查测试。 $ leq_t $是 杜松子酒可降低, ，$ leq_m $是 映射可降低性.

Answer 1

该语句是错误的。

说B是停止问题，$ a = edline b $。然后，将Oracle解决到停止问题，我们可以轻松地决定其补充。

但是，$ a le_m b $是不正确的，因为$ b in re $ $ $和core $ in core $ in Core $不正确（即，如果$ a le_m b $是真实的，那么$ 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 $度量。

（这个结果至少取决于Jockusch的结果，“还原性之间的关系”，Trans。Amer。Math。Soc。142（1969），229-237。在此之前可能已经知道了。）