计算理论

此词条暂由小竹凉翻译，翻译字数共4929，未经人工整理和审校，带来阅读不便，请见谅。

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability 模板:Dn. In these areas, recursion theory overlaps with proof theory and effective descriptive set theory.

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, recursion theory overlaps with proof theory and effective descriptive set theory.

可计算性理论，也被称为递归理论，是数理逻辑 mathematical logic、计算机科学 computer science和计算理论 theory of computation的一个分支，它起源于20世纪30年代，主要研究可计算函数 computable function和图灵度 Turing degree。这个领域已经扩展到包括广义可计算性 computability和定义性 definability的研究。在这些领域，可计算性理论与验证理论 proof theory和有效描述集合论 effective descriptive set theory重叠。

Basic questions addressed by recursion theory include:

递归理论提出的基本问题包括:

What does it mean for a function on the natural numbers to be computable? 关于自然数 natural number的一个函数 function可计算是什么意思？

How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? 不可计算的函数如何根据它们的不可计算性水平被分类为层次结构？

Although there is considerable overlap in terms of knowledge and methods, mathematical recursion theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages.

虽然在知识和方法方面有相当多的重叠，数学递归理论家研究相对可计算性、可还原性概念和度结构的理论; 计算机科学领域的专家致力于递归层次结构 subrecursive hierarchies、形式方法 formal methods和形式语言 formal language。

Computable and uncomputable sets

可计算和不可计算集

Recursion theory originated in the 1930s, with work of Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post.^[1]^[2]

Recursion theory originated in the 1930s, with work of Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post.

递归理论起源于20世纪30年代，由库尔特·戈德尔 Kurt Gödel，阿隆佐·丘奇 Alonzo Church，雷扎·佩特 Rózsa Péter，阿兰·图灵 Alan Turing，斯蒂芬·克莱恩 Stephen Kleene 和 埃米尔·波斯特 Emil Post 共同提出。

The fundamental results the researchers obtained established Turing computability as the correct formalization of the informal idea of effective calculation. These results led Stephen Kleene (1952) to coin the two names "Church's thesis" (Kleene 1952:300) and "Turing's Thesis" (Kleene 1952:376). Nowadays these are often considered as a single hypothesis, the Church–Turing thesis, which states that any function that is computable by an algorithm is a computable function. Although initially skeptical, by 1946 Gödel argued in favor of this thesis:

研究人员获得的基本结果将图灵可计算性 Turing computability是对有效计算的非正式思想的正确形式化。这些结果导致斯蒂芬·克莱恩 Stephen Kleene(1952)创造了两个名字“丘奇的论点”(克莱恩1952:300)和“图灵的论点”(克莱恩1952:376)。如今，这些通常被认为是一个单一的假设----丘奇-图灵论文 Church–Turing thesis，该论文指出，任何可由算法 algorithm计算的函数都是可计算函数 computable function。虽然最初持怀疑态度，但到了1946年，哥德尔还是支持这个观点:

"Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.*"(Gödel 1946 in Davis 1965:84).^[3]

"Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.*"(Gödel 1946 in Davis 1965:84).

“塔斯基在他的演讲中强调了一般递归概念(或者图灵的可计算性)的重要性。在我看来，这种重要性在很大程度上是由于人们第一次成功地把一个绝对的概念赋予了一个有趣的认识论的概念，即一个不依赖于所选择的形式主义的概念。*"(哥德尔 1946 在戴维斯 1965:84).

With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. Church (1936a, 1936b) and Turing (1936), inspired by techniques used by Gödel (1931) to prove his incompleteness theorems, independently demonstrated that the Entscheidungsproblem is not effectively decidable. This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false.

有效计算的定义首次证明了数学中存在着无法有效判定 decided的问题。丘奇(1936a，1936b)和图灵(1936)受到哥德尔(1931)用来证明其不完备性定理技巧的启发，独立证明了可判定性 Entscheidungsproblem是不能有效判定的。这一结果表明，没有算法程序可以正确判定任意数学命题的正确与否。

Many problems in mathematics have been shown to be undecidable after these initial examples were established. In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved (using results of Julia Robinson) Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers. The list of undecidable problems gives additional examples of problems with no computable solution.

许多数学 mathematics问题在这些初始例子建立之后已被证明是不可判定的。马尔科夫和波斯特在1947年发表的独立论文表明，半群代数字符问题不能有效地判定。推广该结果，彼得·诺维科夫Pyotr Novikov和威廉·布恩 William Boone在1950年代分别证明了群代数字符问题 word problem for groups不是有效可解的: 没有给定有限表示群 group代数中的一个字符的有效程序，来决定该字符所表示的元素是否是群代数的单位元素 identity element。1970年，尤里·马季亚谢维奇 Yuri Matiyasevich使用朱莉娅·罗宾逊 Julia Robinson的结果证明了马季亚谢维奇定理 Matiyasevich's theorem ，这意味着希尔伯特第十问题 Hilbert's tenth problem没有有效的解;该问题提出，是否存在一个有效的程序来决定一个整数上的刁番图方程 Diophantine equation有整数解。不可判定问题列表 list of undecidable problems提供了更多无法计算的问题的例子。

The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics; the Handbook of Recursive Mathematics (Ershov et al. 1998) covers many of the known results in this field.

The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics; the Handbook of Recursive Mathematics (Ershov et al. 1998) covers many of the known results in this field.

对哪些数学结构可以有效地执行的研究有时被称为递归数学 ; 《递归数学手册》（1998）涵盖了这一领域的许多已知成果。

Turing computability

图灵可计算性

The main form of computability studied in recursion theory was introduced by Turing (1936). A set of natural numbers is said to be a computable set (also called a decidable, recursive, or Turing computable set) if there is a Turing machine that, given a number n, halts with output 1 if n is in the set and halts with output 0 if n is not in the set. A function f from the natural numbers to themselves is a recursive or (Turing) computable function if there is a Turing machine that, on input n, halts and returns output f(n). The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example the μ-recursive functions obtained from primitive recursion and the μ operator.

The main form of computability studied in recursion theory was introduced by Turing (1936). A set of natural numbers is said to be a computable set (also called a decidable, recursive, or Turing computable set) if there is a Turing machine that, given a number n, halts with output 1 if n is in the set and halts with output 0 if n is not in the set. A function f from the natural numbers to themselves is a recursive or (Turing) computable function if there is a Turing machine that, on input n, halts and returns output f(n). The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example the μ-recursive functions obtained from primitive recursion and the μ operator.

图灵介绍了递归理论中可计算性的主要形式(1936)。一组自然数被称为可计算集 computable set(也称为可判定的、递归的或图灵可计算集) ，在图灵机 Turing machine中，给定一个数字 n，如果 n 在集合中，则停止并输出1，如果 n 不在集合中，则停止并输出0。从自然数到自身的函数 f 是一个递归可计算函数 computable function，即于图灵机中在输入 n 上停止并返回输出 f (n)。在这里使用图灵机是不必要的; 还有许多其他的计算模型 models of computation具有与图灵机相同的计算能力; 例如由本原递归得到的μ 递归函数 μ-recursive functions 和 μ 算子。。

The terminology for recursive functions and sets is not completely standardized.

递归函数和集合的术语没有完全标准化。

The definition in terms of μ-recursive functions as well as a different definition of rekursiv functions by Gödel led to the traditional name recursive for sets and functions computable by a Turing machine. The word decidable stems from the German word Entscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according to Cutland (1980), it is a partial recursive function (which can be undefined for some inputs), while according to Soare (1987) it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. Soare (1996) gives additional comments about the terminology.

The definition in terms of μ-recursive functions as well as a different definition of rekursiv functions by Gödel led to the traditional name recursive for sets and functions computable by a Turing machine. The word decidable stems from the German word Entscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according to Cutland (1980), it is a partial recursive function (which can be undefined for some inputs), while according to Soare (1987) it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. Soare (1996) gives additional comments about the terminology.

哥德尔用 μ 递归函数的定义以及递归函数的不同定义导致了传统的图灵机可计算集合和函数的递归名称。可判定的这个词来源于德语中的在图灵和其他人的原始论文中使用过的可判定性。在当代使用中，术语“可计算函数”有各种各样的定义: 根据卡特兰(1980)的定义，它是一个部分递归函数(对于某些输入可能没有定义) ，而根据苏雷(1987)的定义，它是一个完全递归函数(等价地，一般递归)。本文采用第二个定义。苏雷(1996)对相关术语作了补充说明。

Not every set of natural numbers is computable. The halting problem, which is the set of (descriptions of) Turing machines that halt on input 0, is a well-known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only countably many Turing machines, and thus only countably many computable sets, but according to the Cantor's theorem, there are uncountably many sets of natural numbers.

不是所有的自然数都是可计算的。停机问题 halting problem是指在输入0上停机的图灵机的集合(或描述) ，是不可计算集合的一个著名例子。许多不可计算集合的存在是基于这样一个事实: 只有可数的 countably many图灵机，因此只有可数的可计算集合，但是根据康托定理 Cantor's theorem，存在不可数的 uncountably many自然数集合。

Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a recursively enumerable set, which is a set that can be enumerated by a Turing machine (other terms for recursively enumerable include computably enumerable and semidecidable). Equivalently, a set is recursively enumerable if and only if it is the range of some computable function. The recursively enumerable sets, although not decidable in general, have been studied in detail in recursion theory.

Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a recursively enumerable set, which is a set that can be enumerated by a Turing machine (other terms for recursively enumerable include computably enumerable and semidecidable). Equivalently, a set is recursively enumerable if and only if it is the range of some computable function. The recursively enumerable sets, although not decidable in general, have been studied in detail in recursion theory.

虽然停机问题是不可计算的，但是可以模拟程序执行并生成一个无限的程序列表来做停机。因此，停止问题就是一个递归可枚举集合 recursively enumerable set的例子，它是图灵机可以枚举的集合(递归枚举的其他术语包括可计算枚举和半可计数)。等价地，集合是递归可枚举的当且仅当它是某些可计算函数的范围。递归可枚举集合虽然在一般情况下是不可判定的，但在递归理论中得到了详细的研究。

Areas of research

研究领域

Beginning with the theory of recursive sets and functions described above, the field of recursion theory has grown to include the study of many closely related topics. These are not independent areas of research: each of these areas draws ideas and results from the others, and most recursion theorists are familiar with the majority of them.

从上面描述的递归集合和函数的理论开始，递归理论领域已经发展到包括许多密切相关的主题的研究。它们都不是彼此独立的研究领域: 每个领域都从其他领域吸取思想和成果，大多数递归理论专家对其中的大部分都很熟悉。

Relative computability and the Turing degrees

相对可计算性与图灵度

图灵归约 Turing reduction和图灵度 Turing degree

Recursion theory in mathematical logic has traditionally focused on relative computability, a generalization of Turing computability defined using oracle Turing machines, introduced by Turing (1939). An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an oracle, which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Is n in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that a Turing machine without an oracle cannot.

Recursion theory in mathematical logic has traditionally focused on relative computability, a generalization of Turing computability defined using oracle Turing machines, introduced by Turing (1939). An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an oracle, which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Is n in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that a Turing machine without an oracle cannot.

图灵(1939)介绍，传统上，使用预言图灵机 oracle Turing machine定义，数理逻辑的递归理论专注于相对可计算性，这是图灵可计算性的一种泛化。预言图灵机是一种假想的设备，它除了能够执行普通图灵机的操作之外，还能够向预言提问，预言是一组特定的自然数。预言机只能提出“ n 在预言集合中吗? ”这样的问题。即使预言集是不可计算的，每个问题也都将立即得到正确答案。因此，一台具有不可计算预言的预言机将能够计算集合，而没有预言的图灵机则不能。

Informally, a set of natural numbers A is Turing reducible to a set B if there is an oracle machine that correctly tells whether numbers are in A when run with B as the oracle set (in this case, the set A is also said to be (relatively) computable from B and recursive in B). If a set A is Turing reducible to a set B and B is Turing reducible to A then the sets are said to have the same Turing degree (also called degree of unsolvability). The Turing degree of a set gives a precise measure of how uncomputable the set is.

Informally, a set of natural numbers A is Turing reducible to a set B if there is an oracle machine that correctly tells whether numbers are in A when run with B as the oracle set (in this case, the set A is also said to be (relatively) computable from B and recursive in B). If a set A is Turing reducible to a set B and B is Turing reducible to A then the sets are said to have the same Turing degree (also called degree of unsolvability). The Turing degree of a set gives a precise measure of how uncomputable the set is.

非正式地，一组自然数 a 是图灵可约 Turing reducible地化为一组 b，如果有一台预言机正确地告诉数字是否在 a 中，当 b 作为预言集运行时(在这种情况下，集合 a 也被称为(相对地)可由 b 计算，在 b 中是递归的)。如果一个集合 a 是图灵可约的集合 b，而 b 是图灵可约的集合 a，那么这两个集合被称为具有相同的图灵度 Turing degree(也称为不可解度)。一个集合的图灵度可以精确地度量该集合的不可计算性。

The natural examples of sets that are not computable, including many different sets that encode variants of the halting problem, have two properties in common:

不可计算的集合的自然例子，包括许多不同的编码停机问题 halting problem变体的集合，有两个共同的属性:

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

它们是递归可枚举的 recursively enumerable，并且每个元素都可以通过多一约简 many-one reduction转化为其他任何一个。也就是说，给定这样的集合 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)问道，是否每个递归可枚举集合都是可计算的或图灵等价 Turing equivalent于停机问题---- 换句话说，在这两者之间是否存在图灵度的递归可枚举集合。

As intermediate results, Post defined natural types of recursively enumerable sets like the simple, hypersimple and hyperhypersimple sets. Post showed that these sets are strictly between the computable sets and the halting problem with respect to many-one reducibility. Post also showed that some of them are strictly intermediate under other reducibility notions stronger than Turing reducibility. But Post left open the main problem of the existence of recursively enumerable sets of intermediate Turing degree; this problem became known as Post's problem. After ten years, Kleene and Post showed in 1954 that there are intermediate Turing degrees between those of the computable sets and the halting problem, but they failed to show that any of these degrees contains a recursively enumerable set. Very soon after this, Friedberg and Muchnik independently solved Post's problem by establishing the existence of recursively enumerable sets of intermediate degree. This groundbreaking result opened a wide study of the Turing degrees of the recursively enumerable sets which turned out to possess a very complicated and non-trivial structure.

As intermediate results, Post defined natural types of recursively enumerable sets like the simple, hypersimple and hyperhypersimple sets. Post showed that these sets are strictly between the computable sets and the halting problem with respect to many-one reducibility. Post also showed that some of them are strictly intermediate under other reducibility notions stronger than Turing reducibility. But Post left open the main problem of the existence of recursively enumerable sets of intermediate Turing degree; this problem became known as Post's problem. After ten years, Kleene and Post showed in 1954 that there are intermediate Turing degrees between those of the computable sets and the halting problem, but they failed to show that any of these degrees contains a recursively enumerable set. Very soon after this, Friedberg and Muchnik independently solved Post's problem by establishing the existence of recursively enumerable sets of intermediate degree. This groundbreaking result opened a wide study of the Turing degrees of the recursively enumerable sets which turned out to possess a very complicated and non-trivial structure.

作为中间结果，波斯特定义了递归可枚举集的自然类型，如单纯 simple集、超单纯 hypersimple集和超超单纯集。波斯特证明了这些集合严格介于可计算集合和关于多一可约性的停机问题之间。波斯特还证明了在其他比图灵可约性更强的可约性概念下，其中一些是严格中间的。但是波斯特留下了一个主要的问题: 中等图灵度的可递归枚举集是否存在; 这个问题后来被称为波斯特问题 Post's problem。10年后，克莱恩和波斯特在1954年证明了在可计算集合和停机问题之间存在着中间的图灵度，但是他们没有证明这些度中有任何一个包含递归可枚举集合。此后不久，弗里德伯格和穆赫尼克通过建立递归可枚举集的中间度，独立地解决了波斯特问题。这个突破性的结果开启了对递归可枚举集合的图灵度的广泛研究，这些可枚举集合具有非常复杂和非平凡的结构。

There are uncountably many sets that are not recursively enumerable, and the investigation of the Turing degrees of all sets is as central in recursion theory as the investigation of the recursively enumerable Turing degrees. Many degrees with special properties were constructed: hyperimmune-free degrees where every function computable relative to that degree is majorized by a (unrelativized) computable function; high degrees relative to which one can compute a function f which dominates every computable function g in the sense that there is a constant c depending on g such that g(x) < f(x) for all x > c; random degrees containing algorithmically random sets; 1-generic degrees of 1-generic sets; and the degrees below the halting problem of limit-recursive sets.

There are uncountably many sets that are not recursively enumerable, and the investigation of the Turing degrees of all sets is as central in recursion theory as the investigation of the recursively enumerable Turing degrees. Many degrees with special properties were constructed: hyperimmune-free degrees where every function computable relative to that degree is majorized by a (unrelativized) computable function; high degrees relative to which one can compute a function f which dominates every computable function g in the sense that there is a constant c depending on g such that g(x) < f(x) for all x > c; random degrees containing algorithmically random sets; 1-generic degrees of 1-generic sets; and the degrees below the halting problem of limit-recursive sets.

不计其数的许多集合是不可递归枚举的，对所有集合的图灵度研究与递归可计数图灵度的研究一样，是递归理论的核心。人们构造了许多具有特殊性质的度: 超免疫自由度，其中每个可计算的相对于该度的函数由一个(无关联的)可计算函数控制; 高度相关于计算一个支配每个可计算函数 g 的函数 f，因此存在一个依赖于 g 的常数 c ，使得对所有x > c成立时有g(x) < f(x);包含算法随机集 algorithmically random sets的随机度;1-1-泛型集的泛型度；以及极限-递归 limit-recursive集停止问题下的阶数。

The study of arbitrary (not necessarily recursively enumerable) Turing degrees involves the study of the Turing jump. Given a set A, the Turing jump of A is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracle A. The Turing jump of any set is always of higher Turing degree than the original set, and a theorem of Friedburg shows that any set that computes the Halting problem can be obtained as the Turing jump of another set. Post's theorem establishes a close relationship between the Turing jump operation and the arithmetical hierarchy, which is a classification of certain subsets of the natural numbers based on their definability in arithmetic.

The study of arbitrary (not necessarily recursively enumerable) Turing degrees involves the study of the Turing jump. Given a set A, the Turing jump of A is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracle A. The Turing jump of any set is always of higher Turing degree than the original set, and a theorem of Friedburg shows that any set that computes the Halting problem can be obtained as the Turing jump of another set. Post's theorem establishes a close relationship between the Turing jump operation and the arithmetical hierarchy, which is a classification of certain subsets of the natural numbers based on their definability in arithmetic.

对任意(不一定是递归可枚举)图灵度的研究涉及到图灵跳的研究。给定A集，A的图灵跳 Turing jump是一组自然数，编码了与预言A一起运行的预言图灵机停止问题的解决方案。任何集合的图灵跳总是高于原集合的图灵度，弗里德堡的一个定理表明，任何计算停机问题的集合都可以作为另一个集合的图灵跳得到。波斯特定理 Post's theorem在图灵跳运算和自然数算数谱系 arithmetical hierarchy之间建立了紧密的联系，后者是基于自然数的某些子集在算术上的可定义性而对其进行的分类。

Much recent research on Turing degrees has focused on the overall structure of the set of Turing degrees and the set of Turing degrees containing recursively enumerable sets. A deep theorem of Shore and Slaman (1999) states that the function mapping a degree x to the degree of its Turing jump is definable in the partial order of the Turing degrees. A recent survey by Ambos-Spies and Fejer (2006) gives an overview of this research and its historical progression.

最近很多关于图灵度的研究都集中在图灵度集的总体结构和包含递归可枚举集的图灵度集上。索尔和斯拉曼(1999)的一个深刻定理指出，映射一个度x到其图灵跳度的函数可以按照图灵度的偏序定义。安博斯-斯皮尔斯和费耶尔(2006)最近的一项调查给出了这项研究及其历史进展的概述。

Other reducibilities

其他可约性

约简(递归理论)

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)引入了几种强可约性，之所以这样命名是因为它们意味着真值表可约性。实现强可约性的图灵机将计算出一个总函数，而不管它是哪个预言。弱可约性是指约简过程对于所有预言不可能终止的情况; 图灵可约性就是一个例子。

The strong reducibilities include:

强可约性包括:

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 是 b 的一一可约(或一可约) ，如果存在一个可计算的单射函数 injective function f，使得每个 n 在 a 中当且仅当 f (n)在 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.

多一可约性 Many-one reducibility: 本质上是一一可约性，没有 f 是单射的约束。当且仅当 f (n)在 b 中时，a 是 b 的多一可约(或 m 可约)。

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 通过预言图灵机计算一个总函数，而不管给定的是什么样的图灵机，图灵可约性到 b，则 a 真值表可约到 b。由于康托空间 Cantor space的紧凑性，这相当于约简的同时向预言提供一个问题列表(仅取决于输入) ，然后看到它们的答案就能够产生一个输出，而不需要询问其他问题，不需要考虑预言对初始查询的答案。人们还研究了真值表可约性的许多变体。

Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article Reduction (recursion theory).

约简（递归理论） Reduction (recursion theory)文中进一步讨论了可约性(正的、析取的、合的、线性的以及它们的弱和有界的版本)。

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.

还研究了弱于图灵可约性(即图灵可约性所表示的可约性)的可约性。最著名的是算术可约性 arithmetical reducibility和超算术可约性 hyperarithmetical reducibility。这些可约性与标准算术模型的可定义性密切相关。

Rice's theorem and the arithmetical hierarchy

赖斯定理和算数层次

Rice showed that for every nontrivial class C (which contains some but not all r.e. sets) the index set E = {e: the eth r.e. set W_e is in C} has the property that either the halting problem or its complement is many-one reducible to E, that is, can be mapped using a many-one reduction to E (see Rice's theorem for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the arithmetical hierarchy. For example, the index set FIN of class of all finite sets is on the level Σ₂, the index set REC of the class of all recursive sets is on the level Σ₃, the index set COFIN of all cofinite sets is also on the level Σ₃ and the index set COMP of the class of all Turing-complete sets Σ₄. These hierarchy levels are defined inductively, Σ_n+1 contains just all sets which are recursively enumerable relative to Σ_n; Σ₁ contains the recursively enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.

Rice showed that for every nontrivial class C (which contains some but not all r.e. sets) the index set E = {e: the eth r.e. set W_e is in C} has the property that either the halting problem or its complement is many-one reducible to E, that is, can be mapped using a many-one reduction to E (see Rice's theorem for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the arithmetical hierarchy. For example, the index set FIN of class of all finite sets is on the level Σ₂, the index set REC of the class of all recursive sets is on the level Σ₃, the index set COFIN of all cofinite sets is also on the level Σ₃ and the index set COMP of the class of all Turing-complete sets Σ₄. These hierarchy levels are defined inductively, Σ_n+1 contains just all sets which are recursively enumerable relative to Σ_n; Σ₁ contains the recursively enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.

赖斯证明了对于每一个非平凡的类 c (包含一些但不是全部的 r.e.集)的索引集 e = {e: 第 e个r.e. 集 W_e 在 C中} 具有停机问题或其补问题是多一可约到 e 的性质，也就是说，可以使用多一可约映射到 e (详见赖斯定理)。但是，这些索引集中的许多甚至比停机问题更加复杂。这些类型的集合可以使用算数层次分类法进行分类。例如，所有有限集类的指数集 FIN 在Σ₂水平上，所有递归集类的指数集 REC 在Σ₃水平上，所有余有限集的指数集 COFIN 也在Σ₃ 水平上，所有图灵完备集类的指数集 COMP Σ₄水平上。这些层次级别是归纳定义的，Σ_n+1只包含相对于 Σ_n的递归可枚举集;Σ₁包含递归可枚举集。这里给出的索引集对于它们的级别是完整的，也就是说，这些级别中的所有集合可以是多一可约到给定的索引集。

Reverse mathematics

逆数学

The program of reverse mathematics asks which set-existence axioms are necessary to prove particular theorems of mathematics in subsystems of second-order arithmetic. This study was initiated by Harvey Friedman and was studied in detail by Stephen Simpson and others; Simpson (1999) gives a detailed discussion of the program. The set-existence axioms in question correspond informally to axioms saying that the powerset of the natural numbers is closed under various reducibility notions. The weakest such axiom studied in reverse mathematics is recursive comprehension, which states that the powerset of the naturals is closed under Turing reducibility.

The program of reverse mathematics asks which set-existence axioms are necessary to prove particular theorems of mathematics in subsystems of second-order arithmetic. This study was initiated by Harvey Friedman and was studied in detail by Stephen Simpson and others; Simpson (1999) gives a detailed discussion of the program. The set-existence axioms in question correspond informally to axioms saying that the powerset of the natural numbers is closed under various reducibility notions. The weakest such axiom studied in reverse mathematics is recursive comprehension, which states that the powerset of the naturals is closed under Turing reducibility.

逆数学 reverse mathematics程序要求证明二阶算术 second-order arithmetic二阶算术子系统中的特定数学定理需要哪些集合存在公理。这项研究由哈维·弗里德曼 Harvey Friedman发起，斯蒂芬·辛普森 Steve Simpson等人对其进行了详细的研究; 辛普森(1999)对该项目进行了详细的讨论。所讨论的集合存在性公理非正式地对应于自然数的幂集在各种可约性概念下是封闭的公理。逆数学中研究的最薄弱的定理是递归理解，即自然物的幂集在图灵可约性下是封闭的。

Numberings

编号

A numbering is an enumeration of functions; it has two parameters, e and x and outputs the value of the e-th function in the numbering on the input x. Numberings can be partial-recursive although some of its members are total recursive, that is, computable functions. Admissible numberings are those into which all others can be translated. A Friedberg numbering (named after its discoverer) is a one-one numbering of all partial-recursive functions; it is necessarily not an admissible numbering. Later research dealt also with numberings of other classes like classes of recursively enumerable sets. Goncharov discovered for example a class of recursively enumerable sets for which the numberings fall into exactly two classes with respect to recursive isomorphisms.

编号是函数的枚举；它有两个参数，e和x，并在输入x的编号中输出第e函数的值。编号可以是部分递归的，尽管它的一些成员是完全递归的，即可计算的函数。容许编号 Admissible numbering是所有其他编号都可以翻译成的编号。弗里德伯格编号 Friedberg numbering(以其发现者命名)是所有部分递归函数的一对一编号; 它不一定是容许编号。后来的研究也涉及到其他类的编号，比如递归可枚举集的类。例如，贡恰罗夫发现了一类递归可枚举集，对于这类集合，根据递归同构，其编号恰好分为两个类。

The priority method

优先级方法

For further explanation, see the section Post's problem and the priority method in the article Turing degree.

For further explanation, see the section Post's problem and the priority method in the article Turing degree.

有关进一步的解释，请参阅文章图灵度 Turing degree中波斯特问题 Post's problem和优先级方法 the priority method一节。

Post's problem was solved with a method called the priority method; a proof using this method is called a priority argument. This method is primarily used to construct recursively enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known as requirements, so that satisfying all the requirements will cause the set constructed to have the desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy the requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event.

Post's problem was solved with a method called the priority method; a proof using this method is called a priority argument. This method is primarily used to construct recursively enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known as requirements, so that satisfying all the requirements will cause the set constructed to have the desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy the requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event.

波斯特问题通过优先级方法得到了解决; 使用这个方法的证明称为优先级参数。此方法主要用于构造具有特定属性的递归可枚举集。使用这种方法，要构造的集合的期望属性被分解成一个无限的目标列表，称为需求，因此满足所有需求将使所构造的集合具有所需的属性。每个需求被分配给一个自然数，代表需求的优先级; 因此0被分配给最重要的优先级，1被分配给第二重要的优先级，依此类推。然后集合被分阶段构建，每个阶段都试图通过向集合中添加数字或者禁止集合中的数字来满足更多的需求中的一个，以便最终集合满足这个需求。满足一个需求可能会导致另一个需求得不到满足; 优先级顺序用于决定在此类事件中要做什么。

Priority arguments have been employed to solve many problems in recursion theory, and have been classified into a hierarchy based on their complexity (Soare 1987). Because complex priority arguments can be technical and difficult to follow, it has traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them. For example, Kummer published a paper on a proof for the existence of Friedberg numberings without using the priority method.

优先级参数被用来解决递归理论中的许多问题，并根据其复杂性被划分为一个层次结构(Soare 1987)。因为复杂的优先权论证可能是技术性的，很难遵循，所以传统上认为最好证明没有优先级参数的结果，或者去看用优先级参数证明的结果是否也可以在没有优先级参数的情况下得到证明。例如，库默发表了一篇论文，证明了在不使用优先级方法的情况下弗里德伯格数值的存在性。

The lattice of recursively enumerable sets

递归可枚举集的格

When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

当波斯特将单纯集定义为一个具有无限补集且不包含任何无限r.e.集的r.e.集时，他开始研究其包含的可递归枚举集的结构。晶格成为一个研究得很好的结构。在这种结构中，递归集合可以通过以下基本结果定义:当且仅当集合及其补集都是递归可枚举时，集合是递归的。无限r.e.集总是有无限递归子集。但另一方面，单纯集存在，但没有无限递归超集。波斯特(1944)引入了已有的超单纯集和超超单纯集，后来又构造了极大集，让每一个 r.e.超集要么是给定极大集的有限变形，要么是共有限变形。波斯特研究格的最初动机是找到一个结构性的概念，这样每个满足这个性质的集合既不在递归集合的图灵度中，也不在停止问题的图灵度中。波斯特没有找到这样一个性质，他的问题的解决方案采用了优先级方法，哈林顿和索尔(1991)最终找到了这样一个性质。

Automorphism problems

自同构问题

Another important question is the existence of automorphisms in recursion-theoretic structures. One of these structures is that one of recursively enumerable sets under inclusion modulo finite difference; in this structure, A is below B if and only if the set difference B − A is finite. Maximal sets (as defined in the previous paragraph) have the property that they cannot be automorphic to non-maximal sets, that is, if there is an automorphism of the recursive enumerable sets under the structure just mentioned, then every maximal set is mapped to another maximal set. Soare (1974) showed that also the converse holds, that is, every two maximal sets are automorphic. So the maximal sets form an orbit, that is, every automorphism preserves maximality and any two maximal sets are transformed into each other by some automorphism. Harrington gave a further example of an automorphic property: that of the creative sets, the sets which are many-one equivalent to the halting problem.

另一个重要问题是递归理论结构中自同构的存在性。其中一个结构是递归可枚举集的模差分; 在这个结构中，a 低于 b 当且仅当集合差B − A是有限的。极大集 Maximal set(如前文所定义)具有不能自守为非极大集的性质，即在上述结构下存在递归可枚举集的自同构，则每个极大集映射为另一个极大集。索尔(1974)证明了逆向持有，即每两个极大集都是自守的。所以极大集构成一个轨道，即每一个自同构都保持极大性，任意两个极大集通过某种自同构互相转化。哈林顿又举了一个自同构性质的例子: 创造性集合的自同构性质，创造性集合等价于停机问题。

Besides the lattice of recursively enumerable sets, automorphisms are also studied for the structure of the Turing degrees of all sets as well as for the structure of the Turing degrees of r.e. sets. In both cases, Cooper claims to have constructed nontrivial automorphisms which map some degrees to other degrees; this construction has, however, not been verified and some colleagues believe that the construction contains errors and that the question of whether there is a nontrivial automorphism of the Turing degrees is still one of the main unsolved questions in this area (Slaman and Woodin 1986, Ambos-Spies and Fejer 2006).

除了递归可数集的格外，还研究了所有集的图灵度的结构以及r.e.集的图灵度的结构的自同构。在这两种情况下，库珀声称已经构造了非平凡的自同构，它将一些度映射到其他度;然而，这种构造尚未得到验证，一些同事认为这种构造存在错误，而且图灵度是否存在非平凡自同构的问题仍然是该领域尚未解决的主要问题之一(斯拉曼和伍丁，1986年，安博斯-斯皮尔斯和费耶尔2006)。

Kolmogorov complexity

柯尔莫哥洛夫复杂性

柯尔莫哥洛夫复杂性 Kolmogorov complexity

The field of Kolmogorov complexity and algorithmic randomness was developed during the 1960s and 1970s by Chaitin, Kolmogorov, Levin, Martin-Löf and Solomonoff (the names are given here in alphabetical order; much of the research was independent, and the unity of the concept of randomness was not understood at the time). The main idea is to consider a universal Turing machine U and to measure the complexity of a number (or string) x as the length of the shortest input p such that U(p) outputs x. This approach revolutionized earlier ways to determine when an infinite sequence (equivalently, characteristic function of a subset of the natural numbers) is random or not by invoking a notion of randomness for finite objects. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs.

柯尔莫哥洛夫复杂性 Kolmogorov complexity和算法随机性 algorithmic randomness领域是在20世纪60年代和70年代由蔡廷，柯尔莫哥洛夫，莱文，马丁洛夫和索罗门诺芙发展起来的(这些名字是按字母顺序列出的;许多研究都是独立进行的，而且当时人们并不理解随机性概念的统一性)。其主要思想是考虑一个通用图灵机 universal Turing machine u，并用最短输入 p 的长度来度量一个数字(或字符串) x 的复杂度，这样 u (p)就可以输出 x。这种方法通过引用有限对象的随机性概念，彻底改变了早期确定无限序列(等价地，自然数子集的特征函数)是否是随机的方法。柯尔莫哥洛夫复杂性不仅成为一个独立的研究对象，而且也被应用到其他学科，作为获得证据的工具。

There are still many open problems in this area. For that reason, a recent research conference in this area was held in January 2007^[4] and a list of open problems^[5] is maintained by Joseph Miller and Andre Nies.

There are still many open problems in this area. For that reason, a recent research conference in this area was held in January 2007 and a list of open problems is maintained by Joseph Miller and Andre Nies.

这个领域还有许多悬而未决的问题。因此，2007年1月在这一领域举行了一次最近的研究会议，约瑟夫·米勒和安德烈·尼斯列出了一份尚未解决的问题清单。

Frequency computation

频率计算

This branch of recursion theory analyzed the following question: For fixed m and n with 0 < m < n, for which functions A is it possible to compute for any different n inputs x₁, x₂, ..., x_n a tuple of n numbers y₁,y₂,...,y_n such that at least m of the equations A(x_k) = y_k are true. Such sets are known as (m, n)-recursive sets. The first major result in this branch of Recursion Theory is Trakhtenbrot's result that a set is computable if it is (m, n)-recursive for some m, n with 2m > n. On the other hand, Jockusch's semirecursive sets (which were already known informally before Jockusch introduced them 1968) are examples of a set which is (m, n)-recursive if and only if 2m < n + 1. There are uncountably many of these sets and also some recursively enumerable but noncomputable sets of this type. Later, Degtev established a hierarchy of recursively enumerable sets that are (1, n + 1)-recursive but not (1, n)-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's Cardinality Theory which states that a set A is computable if and only if there is an n such that some algorithm enumerates for each tuple of n different numbers up to n many possible choices of the cardinality of this set of n numbers intersected with A; these choices must contain the true cardinality but leave out at least one false one.

This branch of recursion theory analyzed the following question: For fixed m and n with 0 < m < n, for which functions A is it possible to compute for any different n inputs x₁, x₂, ..., x_n a tuple of n numbers y₁,y₂,...,y_n such that at least m of the equations A(x_k) = y_k are true. Such sets are known as (m, n)-recursive sets. The first major result in this branch of Recursion Theory is Trakhtenbrot's result that a set is computable if it is (m, n)-recursive for some m, n with 2m > n. On the other hand, Jockusch's semirecursive sets (which were already known informally before Jockusch introduced them 1968) are examples of a set which is (m, n)-recursive if and only if 2m < n + 1. There are uncountably many of these sets and also some recursively enumerable but noncomputable sets of this type. Later, Degtev established a hierarchy of recursively enumerable sets that are (1, n + 1)-recursive but not (1, n)-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's Cardinality Theory which states that a set A is computable if and only if there is an n such that some algorithm enumerates for each tuple of n different numbers up to n many possible choices of the cardinality of this set of n numbers intersected with A; these choices must contain the true cardinality but leave out at least one false one.

递归理论的这个分支分析了以下问题: 对于m < n的固定 m 和 n，对于其中的函数A可以计算任意 n 个输入x₁, x₂, ..., x_n的n个元组y₁,y₂,...,y_n，使得至少m个方程A(x_k) = y_k是真的。这样的集合称为(m, n)-递归集。这个递归理论分支的第一个主要结果是特拉赫滕布罗特的结果，即一个集合对于某些 m，n 和2m > n，若(m, n)是递归的则集合是可计算的。另一方面，乔库什的半递归 semirecursive集合(在乔库什于1968年介绍它们之前已经非正式地被知道)是(m, n)-递归集合的例子当且仅当 2m < n + 1。这些集合中有不可数的许多集合，还有一些可递归枚举但不可计算的此类集合。后来，德格特夫建立了递归可枚举集的层次结构，这些可枚举集是(1, n + 1)递归的，而不是(1, n)递归的。经过俄罗斯科学家长时间的研究，贝格尔关于有界查询的论文将频率计算与上述有界约化及其他相关概念联系起来，使这一课题在西方重新流行起来。其中一个主要的结果是库默的基数理论，该理论认为当且仅当存在一个n，使得某个算法枚举了n个不同数的每个元组，最多n个与a相交的n个数的基数的许多可能的选择，集合a是可计算的;这些选项必须包含真正的基数，但至少要去掉一个错误的基数。

Inductive inference

归纳推理

This is the recursion-theoretic branch of learning theory. It is based on Gold's model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class S of computable functions, is there a learner (that is, recursive functional) which outputs for any input of the form (f(0),f(1),...,f(n)) a hypothesis. A learner M learns a function f if almost all hypotheses are the same index e of f with respect to a previously agreed on acceptable numbering of all computable functions; M learns S if M learns every f in S. Basic results are that all recursively enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of recursively enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards.

这是学习理论的递归理论分支。它是基于1967年戈尔德的极限学习模型，并从那时起发展了越来越多的学习模型。一般情况如下: 给定一类可计算函数 s，是否有一个学习者(即递归函数)由形式(f(0),f(1),...,f(n))的任何输入，输出一个假设。一个学习者M学习一个函数f，如果关于所有可计算函数的容许编号，几乎所有的假设都与f的指数e相同;如果M学S中的每一个f，那么M就学习S，基本结果是，所有递归枚举的函数类都是可学习的，而所有可计算函数的类REC是不可学习的。许多相关的模型已经被考虑，而且从正数据中学习递归枚举集的类是哥德尔在1967年的先驱论文中研究的主题。

Generalizations of Turing computability

图灵可计算性的推广

Recursion theory includes the study of generalized notions of this field such as arithmetic reducibility, hyperarithmetical reducibility and α-recursion theory, as described by Sacks (1990). These generalized notions include reducibilities that cannot be executed by Turing machines but are nevertheless natural generalizations of Turing reducibility. These studies include approaches to investigate the analytical hierarchy which differs from the arithmetical hierarchy by permitting quantification over sets of natural numbers in addition to quantification over individual numbers. These areas are linked to the theories of well-orderings and trees; for example the set of all indices of recursive (nonbinary) trees without infinite branches is complete for level [math]\displaystyle{ \Pi^1_1 }[/math] of the analytical hierarchy. Both Turing reducibility and hyperarithmetical reducibility are important in the field of effective descriptive set theory. The even more general notion of degrees of constructibility is studied in set theory.

递归理论包括这个领域的广义概念的研究，如算术可约性 arithmetic reducibility，超算可约性 hyperarithmetical reducibility和 α- 递归理论 α-recursion theory，如萨克斯(1990)所描述的，这些广义概念包括不能由图灵机执行的可约性，但仍然是图灵机可约性的自然推广。这些研究包括研究解析分层 analytical hierarchy的方法，这种分析层次结构不同于算术谱系 arithmetical hierarchy，它允许对自然数集进行量化，同时也允许对单个数进行量化。这些区域与良序理论和树理论相联系; 例如，对于层次分析法的层次 [math]\displaystyle{ \Pi^1_1 }[/math]，没有无限分支的递归(非二叉)树的所有索引集是完整的。图灵可约性和超算术可约性在有效描述集合论 effective descriptive set theory领域都很重要。在集合论 set theory中研究了更一般的可构造性度 degrees of constructibility的概念。

Continuous computability theory

连续的可计算性理论

Computability theory for digital computation is well developed. Computability theory is less well developed for analog computation that occurs in analog computers, analog signal processing, analog electronics, neural networks and continuous-time control theory, modelled by differential equations and continuous dynamical systems (Orponen 1997; Moore 1996).

数字计算的可计算性理论已经发展的很好。可计算性理论在模拟计算 analog computation方面发展较差，模拟计算发生在模拟计算机 analog computer、模拟信号处理 analog signal processing、模拟电子学 analog electronics、神经网络 neural networks和连续时间控制理论 control theory，由微分方程 differential equation和连续动力系统 dynamical system建模(奥波宁 1997; 摩尔1996)。

Relationships between definability, proof and computability

可定义性、证明性和可计算性之间的关系

There are close relationships between the Turing degree of a set of natural numbers and the difficulty (in terms of the arithmetical hierarchy) of defining that set using a first-order formula. One such relationship is made precise by Post's theorem. A weaker relationship was demonstrated by Kurt Gödel in the proofs of his completeness theorem and incompleteness theorems. Gödel's proofs show that the set of logical consequences of an effective first-order theory is a recursively enumerable set, and that if the theory is strong enough this set will be uncomputable. Similarly, Tarski's indefinability theorem can be interpreted both in terms of definability and in terms of computability.

一组自然数的图灵程度与用一阶公式 first-order formula定义该集合的难度(就算术谱系 arithmetical hierarchy而言)之间存在密切关系。波斯特定理 Post's theorem使这种关系变得精确。库尔特·哥德尔 Kurt Gödel在他的完备性定理 completeness theorem和不完备性定理 incompleteness theorems的证明中证明了一个较弱的关系。哥德尔的证明表明，一个有效的一阶理论的逻辑结果集是一个递归可枚举集 recursively enumerable set，如果这个理论足够强大，这个集合将是无法计算的。类似地，塔斯基的不可定义定理 Tarski's indefinability theorem可以从可定义性和可计算性两方面来解释。

Recursion theory is also linked to second order arithmetic, a formal theory of natural numbers and sets of natural numbers. The fact that certain sets are computable or relatively computable often implies that these sets can be defined in weak subsystems of second order arithmetic. The program of reverse mathematics uses these subsystems to measure the noncomputability inherent in well known mathematical theorems. Simpson (1999) discusses many aspects of second-order arithmetic and reverse mathematics.

递归理论也与二阶算术 second order arithmetic有关，二阶算术是一种关于自然数和自然数集合的形式理论。某些集合是可计算的或相对可计算的这一事实通常意味着这些集合可以在二阶算术的弱子系统中定义。逆数学 reverse mathematics的程序使用这些子系统来测量众所周知的数学定理所固有的不可计算性。辛普森(1999)讨论了二阶算术和逆数学的许多方面。

The field of proof theory includes the study of second-order arithmetic and Peano arithmetic, as well as formal theories of the natural numbers weaker than Peano arithmetic. One method of classifying the strength of these weak systems is by characterizing which computable functions the system can prove to be total (see Fairtlough and Wainer (1998)). For example, in primitive recursive arithmetic any computable function that is provably total is actually primitive recursive, while Peano arithmetic proves that functions like the Ackermann function, which are not primitive recursive, are total. Not every total computable function is provably total in Peano arithmetic, however; an example of such a function is provided by Goodstein's theorem.

验证理论 proof theory包括二阶算术和皮亚诺算术 Peano arithmetic的研究，以及比皮亚诺算术弱的自然数的形式化理论。对这些弱系统的强度进行分类的一种方法是通过描述系统可以证明的全部 total可计算功能(见费尔托夫和韦纳 (1998))。例如，在原始递归算法 primitive recursive arithmetic中，任何可计算的可证明总函数实际上是原始递归 primitive recursive，而皮亚诺算术 Peano arithmetic证明了像阿克曼函数 Ackermann function这样的函数，不是原始递归的，是总函数。然而，并不是所有的可计算函数在皮亚诺算术中都是可证明的总和，此类函数的一个例子就是古德斯坦定理 Goodstein's theorem。

Name

命名

The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days. Robert I. Soare, a prominent researcher in the field, has proposed (Soare 1996) that the field should be called "computability theory" instead. He argues that Turing's terminology using the word "computable" is more natural and more widely understood than the terminology using the word "recursive" introduced by Kleene. Many contemporary researchers have begun to use this alternate terminology.^[6] These researchers also use terminology such as partial computable function and computably enumerable (c.e.) set instead of partial recursive function and recursively enumerable (r.e.) set. Not all researchers have been convinced, however, as explained by Fortnow^[7] and Simpson.^[8]

The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days. Robert I. Soare, a prominent researcher in the field, has proposed (Soare 1996) that the field should be called "computability theory" instead. He argues that Turing's terminology using the word "computable" is more natural and more widely understood than the terminology using the word "recursive" introduced by Kleene. Many contemporary researchers have begun to use this alternate terminology. These researchers also use terminology such as partial computable function and computably enumerable (c.e.) set instead of partial recursive function and recursively enumerable (r.e.) set. Not all researchers have been convinced, however, as explained by Fortnow and Simpson.

处理可计算性及其推广的数理逻辑领域自早期就被称为“递归理论”。这一领域的杰出研究者罗伯特·I·索尔 Robert I. Soare提出(索尔1996) ，这一领域应该被称为“可计算性理论”。他认为，图灵使用的术语“可计算”比克莱恩引入的术语“递归”更自然，也更广泛地被理解。许多当代研究人员已经开始使用这个替代术语。这些研究人员还使用部分可计算函数和可计算枚举(c.e.)集等术语来代替部分递归函数和递归可枚举(r.e.)集。然而，正如福特诺和辛普森所解释的，并非所有的研究人员都被说服了。

Some commentators argue that both the names recursion theory and computability theory fail to convey the fact that most of the objects studied in recursion theory are not computable.^[9]

Some commentators argue that both the names recursion theory and computability theory fail to convey the fact that most of the objects studied in recursion theory are not computable.

一些评论家认为，递归理论和可计算性理论这两个名字都不能表达这样一个事实，即大多数在可计算性理论中研究的对象是不可计算的。

Rogers (1967) has suggested that a key property of recursion theory is that its results and structures should be invariant under computable bijections on the natural numbers (this suggestion draws on the ideas of the Erlangen program in geometry). The idea is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). According to Rogers, the sets of interest in recursion theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.

罗杰斯(1967)建议，递归理论的一个关键性质是，它的结果和结构应该在自然数的可计算双射 bijection下不变(这个建议借鉴了几何学中爱尔兰根纲领 Erlangen program的思想)。这个想法是，一个可计算的双射只是重命名一个集合中的数字，而不是指出集合中的任何结构，就像欧几里德平面的旋转不会改变画在它上面的线的任何几何方面一样。由于任意两个无限可计算集合通过一个可计算的双射联系在一起，这个方案确定了所有无限可计算集合(有限可计算集合被视为平凡集合)。根据罗杰斯的说法，递归理论中感兴趣的集合是不可计算的集合，通过可计算的自然数的双射划分成等价类。

Professional organizations

行业组织

The main professional organization for recursion theory is the Association for Symbolic Logic, which holds several research conferences each year. The interdisciplinary research Association Computability in Europe (CiE) also organizes a series of annual conferences.

The main professional organization for recursion theory is the Association for Symbolic Logic, which holds several research conferences each year. The interdisciplinary research Association Computability in Europe (CiE) also organizes a series of annual conferences.

递归理论的主要专业组织是符号逻辑协会 Association for Symbolic Logic，每年举行几次研究会议。欧洲可计算性 Computability in Europe(CiE)科际整合协会也组织了一系列的年度会议。

Notes

↑ Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
↑ Soare, Robert Irving (22 December 2011). "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. Retrieved 23 August 2017.
↑ The full paper can also be found at pages 150ff (with commentary by Charles Parsons at 144ff) in Feferman et al. editors 1990 Kurt Gödel Volume II Publications 1938-1974, Oxford University Press, New York, . Both reprintings have the following footnote * added to the Davis volume by Gödel in 1965: "To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f (p. 150).
↑ Conference on Logic, Computability and Randomness -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-的存檔，存档日期2007-12-26., January 10–13, 2007.
↑ The homepage of Andre Nies has a list of open problems in Kolmogorov complexity
↑ Mathscinet searches for the titles like "computably enumerable" and "c.e." show that many papers have been published with this terminology as well as with the other one.
↑ Lance Fortnow, "Is it Recursive, Computable or Decidable?," 2004-2-15, accessed 2018-3-22.
↑ Stephen G. Simpson, "What is computability theory?," FOM email list, 1998-8-24, accessed 2006-1-9.
↑ Harvey Friedman, "Renaming recursion theory," FOM email list, 1998-8-28, accessed 2006-1-9.

References

Undergraduate level texts

Undergraduate level texts

本科课程

Cooper, S.B. (2004). Computability Theory. Chapman & Hall/CRC. ISBN 1-58488-237-9.

Cutland, N. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7. https://archive.org/details/computabilityint0000cutl.

Matiyasevich, Y. (1993). Hilbert's Tenth Problem. MIT Press. ISBN 0-262-13295-8.

Advanced texts

Advanced texts

高级文本

Jain, S.; Osherson, D.; Royer, J.; Sharma, A. (1999). Systems that learn, an introduction to learning theory (2nd ed.). Bradford Book. ISBN 0-262-10077-0.

Kleene, S. (1952). Introduction to Metamathematics. North-Holland. ISBN 0-7204-2103-9.

Lerman, M. (1983). Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-12155-2.

Nies, Andre (2009). Computability and Randomness. Oxford University Press. ISBN 978-0-19-923076-1.

Odifreddi, P. (1989). Classical Recursion Theory. North-Holland. ISBN 0-444-87295-7. https://archive.org/details/classicalrecursi0000odif.

Odifreddi, P. (1999). Classical Recursion Theory. II. Elsevier. ISBN 0-444-50205-X.

Rogers, Jr., H. (1987). The Theory of Recursive Functions and Effective Computability (2nd ed.). MIT Press. ISBN 0-262-68052-1.

Sacks, G. (1990). Higher Recursion Theory. Springer-Verlag. ISBN 3-540-19305-7. https://archive.org/details/higherrecursiont0000sack.

Simpson, S.G. (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 3-540-64882-8.

Soare, R.I. (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 0-387-15299-7.

Survey papers and collections

Survey papers and collections

调查文件和收藏品

Ambos-Spies, K.; Fejer, P. (2006). "Degrees of Unsolvability" (PDF). Archived from the original (PDF) on 2013-04-20. Retrieved 2006-10-27. Unpublished preprint.

Unpublished preprint.

未出版的预印本。

Enderton, H. (1977). "Elements of Recursion Theory". In Barwise, J.. Handbook of Mathematical Logic. North-Holland. pp. 527–566. ISBN 0-7204-2285-X. https://archive.org/details/handbookofmathem0090unse/page/527.

Ershov, Y.L.; Goncharov, S.S.; Nerode, A.; Remmel, J.B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 0-7204-2285-X. https://archive.org/details/handbookofmathem0090unse.

Fairtlough, M.; Wainer, S.S. (1998). "Hierarchies of Provably Recursive Functions". In Buss, S.R.. Handbook of Proof Theory. Elsevier. pp. 149–208. ISBN 978-0-08-053318-6. https://books.google.com/books?id=MfTMDeCq7ukC&pg=PA149.

Soare, R.I. (1996). "Computability and recursion" (PDF). Bulletin of Symbolic Logic. 2 (3): 284–321. doi:10.2307/420992. JSTOR 420992.

Research papers and collections

Research papers and collections

研究论文和收藏

Burgin, M.; Klinger, A. (2004). "Experience, Generations, and Limits in Machine Learning". Theoretical Computer Science. 317 (1–3): 71–91. doi:10.1016/j.tcs.2003.12.005.

Church, A. (1936). "An unsolvable problem of elementary number theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Reprinted in 脚本错误：没有“Footnotes”这个模块。.

Reprinted in .

转载。

Church, A. (1936). "A note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. Reprinted in 脚本错误：没有“Footnotes”这个模块。.

Reprinted in .

转载。

Davis, Martin, ed. (2004) [1965]. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Courier. ISBN 978-0-486-43228-1. https://books.google.com/books?id=qW8x7sQ4JXgC.

}}

}}

Friedberg, R.M. (1958). "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition". The Journal of Symbolic Logic. 23 (3): 309–316. doi:10.2307/2964290. JSTOR 2964290.

{{Cite journal

{{Cite journal

{ Cite journal

 | last=Gold | first=E. Mark

 | last=Gold | first=E. Mark

| last = Gold | first = e.马克

 | title=Language Identification in the Limit

 | title=Language Identification in the Limit

| title = 极限中的语言识别

 | volume=10

 | volume=10

10

 | issue=5

 | issue=5

第五期

| pages=447–474

| pages=447–474

| 页数 = 447-474

 | url=http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf

 | url=http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf

Http://web.mit.edu/~6.863/www/spring2009/readings/gold67limit.pdf

 | journal=Information and Control | year=1967

 | journal=Information and Control | year=1967

1967年

 | doi=10.1016/s0019-9958(67)91165-5}} [1]

 | doi=10.1016/s0019-9958(67)91165-5}} [2]

| doi = 10.1016/s0019-9958(67)91165-5}[ https://web.archive.org/web/20090125120159/http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html ]

Harrington, L.; Soare, R.I. (1991). "Post's Program and incomplete recursively enumerable sets". Proc. Natl. Acad. Sci. U.S.A. 88 (22): 10242–6. Bibcode:1991PNAS...8810242H. doi:10.1073/pnas.88.22.10242. PMC 52904. PMID 11607241.

Jockusch jr, C.G. (1968). "Semirecursive sets and positive reducibility". Trans. Amer. Math. Soc. 137 (2): 420–436. doi:10.1090/S0002-9947-1968-0220595-7. JSTOR 1994957.

Kleene, S.C.; Post, E.L. (1954). "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics. Second. 59 (3): 379–407. doi:10.2307/1969708. JSTOR 1969708.

Moore, C. (1996). "Recursion theory on the reals and continuous-time computation". Theoretical Computer Science. 162 (1): 23–44. CiteSeerX 10.1.1.6.5519. doi:10.1016/0304-3975(95)00248-0.

Myhill, J. (1956). "The lattice of recursively enumerable sets". The Journal of Symbolic Logic. 21: 215–220. doi:10.1017/S002248120008525X.

Orponen, P. (1997). "A survey of continuous-time computation theory". Advances in Algorithms, Languages, and Complexity: 209–224. CiteSeerX 10.1.1.53.1991. doi:10.1007/978-1-4613-3394-4_11. ISBN 978-1-4613-3396-8.

Post, E. (1944). "Recursively enumerable sets of positive integers and their decision problems". Bulletin of the American Mathematical Society. 50 (5): 284–316. doi:10.1090/S0002-9904-1944-08111-1. MR 0010514.

Post, E. (1947). "Recursive unsolvability of a problem of Thue". Journal of Symbolic Logic. 12 (1): 1–11. doi:10.2307/2267170. JSTOR 2267170. Reprinted in 脚本错误：没有“Footnotes”这个模块。.

Reprinted in .

转载。

Shore, Richard A.; Slaman, Theodore A. (1999). "Defining the Turing jump" (PDF). Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. MR 1739227.

Slaman, T.; Woodin, W.H. (1986). "Definability in the Turing degrees". Illinois J. Math. 30 (2): 320–334. doi:10.1215/ijm/1256044641. MR 0840131.

Soare, R.I. (1974). "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets". Annals of Mathematics. 100 (1): 80–120. doi:10.2307/1970842. JSTOR 1970842.

Turing, A. (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. s2-42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. Turing, A.M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction". Proceedings of the London Mathematical Society. s2-43 (1): 544–6. doi:10.1112/plms/s2-43.6.544. Reprinted in 脚本错误：没有“Footnotes”这个模块。. PDF from comlab.ox.ac.uk

Reprinted in . PDF from comlab.ox.ac.uk

转载。Http://web.comlab.ox.ac.uk/oucl/research/areas/ieg/e-library/sources/tp2-ie.PDF : http://www.ecauses.org/

Turing, A.M. (1939). "Systems of logic based on ordinals". Proceedings of the London Mathematical Society. s2-45 (1): 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. Reprinted in 脚本错误：没有“Footnotes”这个模块。.

Reprinted in .

转载。

External links

模板:Commonscat

Association for Symbolic Logic homepage

Computability in Europe homepage

Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes

German language lecture notes on inductive inference

模板:Computer science

模板:Mathematical logic

C