更改

不可计算的集合的自然例子，包括许多不同的编码'''<font color="#ff8000">停机问题 halting problem</font>'''变体的集合，有两个共同的属性:

不可计算的集合的自然例子，包括许多不同的编码'''<font color="#ff8000">停机问题 halting problem</font>'''变体的集合，有两个共同的属性:

#They are [[recursively enumerable]], and

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

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>'''，并且每个元素都可以通过多一减法转化为其他任何一个。也就是说，给定这样的集合 a 和 b，存在总可计算函数''f''使得 ''A'' = {''x'' : ''f''(''x'') ∈ ''B''}。这些集合被称为多一等价集(或 m 等价集)。

 

#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'').

 

 

每一个都可以通过一个多一减法转化为其他任何一个。也就是说，给定这样的集合 a 和 b，存在总可计算函数 f 使得 a = { x: f (x)∈ b }。这些集合被称为多一等价集(或 m 等价集)。