更改

They are recursively enumerable, and each can be translated into any other via a many-one reduction. That is, given such sets A and B, there is a total computable function f such that A = {x : f(x) ∈ B}. These sets are said to be many-one equivalent (or m-equivalent).

They are recursively enumerable, and each can be translated into any other via a many-one reduction. That is, given such sets A and B, there is a total computable function f such that A = {x : f(x) ∈ B}. These sets are said to be many-one equivalent (or m-equivalent).

它们是'''<font color="#ff8000">递归可枚举的 recursively enumerable</font>'''，并且每个元素都可以通过'''<font color="#ff8000">多至一简化 many-one reduction</font>'''转化为其他任何一个。也就是说，给定这样的集合 a 和 b，存在总可计算函数''f''使得 ''A'' = {''x'' : ''f''(''x'') ∈ ''B''}。这些集合被称为多一等价集(或 m 等价集)。

它们是'''<font color="#ff8000">递归可枚举的 recursively enumerable</font>'''，并且每个元素都可以通过'''<font color="#ff8000">多一约简 many-one reduction</font>'''转化为其他任何一个。也就是说，给定这样的集合 a 和 b，存在总可计算函数''f''使得 ''A'' = {''x'' : ''f''(''x'') ∈ ''B''}。这些集合被称为多一等价集(或 m 等价集)。

Many-one reductions are "stronger" than Turing reductions: if a set A is many-one reducible to a set B, then A is Turing reducible to B, but the converse does not always hold. Although the natural examples of noncomputable sets are all many-one equivalent, it is possible to construct recursively enumerable sets A and B such that A is Turing reducible to B but not many-one reducible to B. It can be shown that every recursively enumerable set is many-one reducible to the halting problem, and thus the halting problem is the most complicated recursively enumerable set with respect to many-one reducibility and with respect to Turing reducibility. Post (1944) asked whether every recursively enumerable set is either computable or Turing equivalent to the halting problem, that is, whether there is no recursively enumerable set with a Turing degree intermediate between those two.

Many-one reductions are "stronger" than Turing reductions: if a set A is many-one reducible to a set B, then A is Turing reducible to B, but the converse does not always hold. Although the natural examples of noncomputable sets are all many-one equivalent, it is possible to construct recursively enumerable sets A and B such that A is Turing reducible to B but not many-one reducible to B. It can be shown that every recursively enumerable set is many-one reducible to the halting problem, and thus the halting problem is the most complicated recursively enumerable set with respect to many-one reducibility and with respect to Turing reducibility. Post (1944) asked whether every recursively enumerable set is either computable or Turing equivalent to the halting problem, that is, whether there is no recursively enumerable set with a Turing degree intermediate between those two.

多一约简比图灵约简“更强” : 如果一个集合 a 是多一可约到一个集合 b，那么 a 是图灵可约到 b，但是逆向并不总是成立。虽然不可计算集合的自然例子都是多一等价的，但是可以构造递归可枚举集合 a 和 b，使得 a 是图灵可约的集合 b，而不是多一可约的集合 b。我们可以证明，每个递归可枚举集合都是停机问题的多一可约性，因此停机问题是多一可约性和图灵可约性方面最复杂的递归可枚举集合。波斯特(1944)问道，是否每个递归可枚举集合都是可计算的还是图灵等价于停机问题---- 也就是说，是否在这两者之间没有图灵学位的递归可枚举集合。

多一约简比图灵约简“更强” : 如果一个集合 a 是多一可约到一个集合 b，则 a 图灵可约到 b，但是逆向并不总是成立。虽然不可计算集合的自然例子都是多一等价的，但是可以构造递归可枚举集合 a 和 b，使得 a 是图灵可约到集合 b，而不多一可约到集合 b。我们可以证明，每个递归可枚举集合都是停机问题的多一可约性，因此停机问题是关于多一可约性和图灵可约性的最复杂的递归可枚举集合。波斯特(1944)问道，是否每个递归可枚举集合都是可计算的或'''<font color="#ff8000">图灵等价 Turing equivalent</font>'''于停机问题---- 换句话说，在这两者之间是否存在图灵度的递归可枚举集合。