307
个编辑
更改
跳到导航
跳到搜索
第209行：
第209行： + − + 第218行：
第219行： − + 第226行：
第227行： − 强还原性包括:+ 第232行：
第233行： − 1-1可约性: a 是 b 的1-1可约(或1-可约) ，如果存在一个可计算的单射 f，使得每个 n 在 a 中当且仅当 f (n)在 b 中。+ 第238行：
第239行： − + 第244行：
第245行： − + 第250行：
第251行： − 进一步的还原性(正的、析取的、连接的、线性的以及它们的弱的和有界的版本)在文章还原(可计算性理论)中进行了讨论。+ 第258行：
第259行： − 关于强可约性的主要研究是比较它们的理论，包括所有递归可枚举集的类和自然数的所有子集的类。此外，还研究了还原度之间的关系。例如，众所周知，每个图灵度要么是一个真表度，要么是无穷多个真表度的集合。+ 第266行：
第267行： − + − −
→Other reducibilities
===Other reducibilities===
===Other reducibilities===
其他可约性
{{Main|Reduction (recursion theory)}}
{{Main|Reduction (recursion theory)}}
约简(递归理论)
An ongoing area of research in recursion theory studies reducibility relations other than Turing reducibility. Post (1944) introduced several strong reducibilities, so named because they imply truth-table reducibility. A Turing machine implementing a strong reducibility will compute a total function regardless of which oracle it is presented with. Weak reducibilities are those where a reduction process may not terminate for all oracles; Turing reducibility is one example.
An ongoing area of research in recursion theory studies reducibility relations other than Turing reducibility. Post (1944) introduced several strong reducibilities, so named because they imply truth-table reducibility. A Turing machine implementing a strong reducibility will compute a total function regardless of which oracle it is presented with. Weak reducibilities are those where a reduction process may not terminate for all oracles; Turing reducibility is one example.
可计算性理论的一个正在进行的研究领域是图灵可约性之外的可约性关系。波斯特(1944)引入了几种强还原性，之所以这样命名是因为它们意味着真值表还原性。实现强可约性的图灵机将计算出一个总函数，而不管它是哪个预言。弱还原性是指还原过程对于所有预言不可能终止的情况; 图灵还原性就是一个例子。
可计算性理论的一个正在进行的研究领域是图灵可约性之外的可约性关系。波斯特(1944)引入了几种强可约性，之所以这样命名是因为它们意味着真值表可约性。实现强可约性的图灵机将计算出一个总函数，而不管它是哪个预言。弱可约性是指约简过程对于所有预言不可能终止的情况; 图灵可约性就是一个例子。
The strong reducibilities include:
The strong reducibilities include:
强可约性包括:
;[[Many-one reduction|One-one reducibility]]: ''A'' is ''one-one reducible'' (or ''1-reducible'') to ''B'' if there is a total computable [[injective function]] ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''.
;[[Many-one reduction|One-one reducibility]]: ''A'' is ''one-one reducible'' (or ''1-reducible'') to ''B'' if there is a total computable [[injective function]] ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''.
One-one reducibility: A is one-one reducible (or 1-reducible) to B if there is a total computable injective function f such that each n is in A if and only if f(n) is in B.
One-one reducibility: A is one-one reducible (or 1-reducible) to B if there is a total computable injective function f such that each n is in A if and only if f(n) is in B.
'''<font color="#ff8000">一一可约性 One-one reducibility</font>''': a 是 b 的一一可约(或一可约) ，如果存在一个可计算的'''<font color="#ff8000">单射函数 injective function</font>''' f，使得每个 n 在 a 中当且仅当 f (n)在 b 中。
;[[Many-one reduction|Many-one reducibility]]: This is essentially one-one reducibility without the constraint that ''f'' be injective. ''A'' is ''many-one reducible'' (or ''m-reducible'') to ''B'' if there is a total computable function ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''.
;[[Many-one reduction|Many-one reducibility]]: This is essentially one-one reducibility without the constraint that ''f'' be injective. ''A'' is ''many-one reducible'' (or ''m-reducible'') to ''B'' if there is a total computable function ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''.
Many-one reducibility: This is essentially one-one reducibility without the constraint that f be injective. A is many-one reducible (or m-reducible) to B if there is a total computable function f such that each n is in A if and only if f(n) is in B.
Many-one reducibility: This is essentially one-one reducibility without the constraint that f be injective. A is many-one reducible (or m-reducible) to B if there is a total computable function f such that each n is in A if and only if f(n) is in B.
多一可约性: 本质上是一一可约性，没有 f 是内射的约束。当且仅当 f (n)在 b 中时，a 是 b 的多可计算函数可约(或 m 可约)。
'''<font color="#ff8000">多一可约性 Many-one reducibility</font>''': 本质上是一一可约性，没有 f 是单射的约束。当且仅当 f (n)在 b 中时，a 是 b 的多一可约(或 m 可约)。
;[[Truth table reduction|Truth-table reducibility]]: ''A'' is truth-table reducible to ''B'' if ''A'' is Turing reducible to ''B'' via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of [[Cantor space]], this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied.
;[[Truth table reduction|Truth-table reducibility]]: ''A'' is truth-table reducible to ''B'' if ''A'' is Turing reducible to ''B'' via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of [[Cantor space]], this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied.
Truth-table reducibility: A is truth-table reducible to B if A is Turing reducible to B via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of Cantor space, this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied.
Truth-table reducibility: A is truth-table reducible to B if A is Turing reducible to B via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of Cantor space, this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied.
真值表可约性: a 是真值表可约性到 b，如果 a 是图灵可约性到 b，通过 oracle 图灵机计算一个总函数，而不管给定的是什么样的图灵机。由于 Cantor 空间的紧凑性，这相当于说缩减同时向 oracle 提供一个问题列表(仅取决于输入) ，然后看到它们的答案就能够产生一个输出，而不需要询问其他问题，而不需要考虑 oracle 对初始查询的答案。还研究了真值表可约性的许多变体。
'''<font color="#ff8000">真值表可约性 Truth-table reducibility</font>''':如果 a 通过预言图灵机计算一个总函数，而不管给定的是什么样的图灵机，图灵可约性到 b，则 a 真值表可约到 b。由于'''<font color="#ff8000">康托空间 Cantor space</font>'''的紧凑性，这相当于约简的同时向预言提供一个问题列表(仅取决于输入) ，然后看到它们的答案就能够产生一个输出，而不需要询问其他问题，不需要考虑预言对初始查询的答案。人们还研究了真值表可约性的许多变体。
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article [[Reduction (recursion theory)]].
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article [[Reduction (recursion theory)]].
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article Reduction (recursion theory).
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article Reduction (recursion theory).
'''<font color="#ff8000">约简（递归理论） Reduction (recursion theory)</font>'''文中进一步讨论了可约性(正的、析取的、合的、线性的以及它们的弱和有界的版本)。
The major research on strong reducibilities has been to compare their theories, both for the class of all recursively enumerable sets as well as for the class of all subsets of the natural numbers. Furthermore, the relations between the reducibilities has been studied. For example, it is known that every Turing degree is either a truth-table degree or is the union of infinitely many truth-table degrees.
The major research on strong reducibilities has been to compare their theories, both for the class of all recursively enumerable sets as well as for the class of all subsets of the natural numbers. Furthermore, the relations between the reducibilities has been studied. For example, it is known that every Turing degree is either a truth-table degree or is the union of infinitely many truth-table degrees.
关于强可约性的主要研究是比较它们的理论，包括所有递归可枚举集的类和自然数的所有子集的类。此外，还研究了可约性之间的关系。例如，众所周知，每个图灵度要么是一个真表度，要么是无穷多个真表度的集合。
Reducibilities weaker than Turing reducibility (that is, reducibilities that are implied by Turing reducibility) have also been studied. The most well known are arithmetical reducibility and hyperarithmetical reducibility. These reducibilities are closely connected to definability over the standard model of arithmetic.
Reducibilities weaker than Turing reducibility (that is, reducibilities that are implied by Turing reducibility) have also been studied. The most well known are arithmetical reducibility and hyperarithmetical reducibility. These reducibilities are closely connected to definability over the standard model of arithmetic.
还研究了弱于图灵可约性(即图灵可约性所暗示的可约性)的可约性。最著名的是算术还原和超算术还原。这些还原性与标准算术模型的可定义性密切相关。
还研究了弱于图灵可约性(即图灵可约性所表示的可约性)的可约性。最著名的是'''<font color="#ff8000">算术可约性 arithmetical reducibility</font>'''和'''<font color="#ff8000">超算术可约性 hyperarithmetical reducibility</font>'''。这些可约性与标准算术模型的可定义性密切相关。
===Rice's theorem and the arithmetical hierarchy===
===Rice's theorem and the arithmetical hierarchy===