更改

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

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

===Inductive inference===

===Inductive inference===