更改

===Generalizations of Turing computability===

===Generalizations of Turing computability===

Recursion theory includes the study of generalized notions of this field such as [[arithmetic reducibility]], [[hyperarithmetical reducibility]] and [[alpha recursion theory|α-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>\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 [[Degree of constructibility|degrees of constructibility]] is studied in [[set theory]].

Recursion theory includes the study of generalized notions of this field such as [[arithmetic reducibility]], [[hyperarithmetical reducibility]] and [[alpha recursion theory|α-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>\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 [[Degree of constructibility|degrees of constructibility]] is studied in [[set theory]].

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

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

可计算性理论包括这个领域的广义概念的研究，如算术还原，超算还原和 α- 递归理论，如 Sacks (1990)所描述的。这些广义概念包括图灵机不能执行的还原性，但仍然是图灵还原性的自然推广。这些研究包括的方法，调查分析层次，这不同于美国算数阶层，允许量化集的自然数除了量化个别数字。这些区域与良序理论和树理论相联系; 例如，对于层次分析法的层次 < math > Pi ^ 1 </math > ，没有无限分支的递归(非二叉)树的所有索引集是完整的。图灵可约性和超算术可约性在有效描述集合论领域都很重要。在集合论中研究了更一般的可构造性度的概念。

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

 

 

===Continuous computability theory===

===Continuous computability theory===