递归论
维基百科，自由的百科全书
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论(effective descriptive set theory)有所重叠。
数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。
[编辑] 历史和范围
递归论理论起源自哥德尔、邱奇、图灵、Stephen Kleene 和 Emil Post 在 1930 年代的工作。他们获得的基本结果建立了图灵可计算性作为有效计算的非正式想法的正确的形式化。通过能行计算的严格定义带来了在数学中有些问题是不可有效判定的最初证明。邱奇和图灵独立的证明了停机问题不能能行判定，而 Post 证明了在 Thue 系统中确定一个字符串是否有规范形式(类似于在 λ 演算中一个项是否有规则形式)不能有效的确定。
不可解度结构的研究，包括图灵度、多一度和类似的结构，是这个领域的重要部分。图灵度的研究发起自 Kleene 和 Post [1954]。大量的可计算性理论中的研究已经投入到图灵度的性质的研究中。开始于 1970 年代，图灵度的研究焦点已经从局部结构性质转移到全局性质，比如图灵度的自同构(automorphism)和0'的可定义性。
在 1930 年代确定了最初的例子之后，很多数学问题已经被证实是不可判定的。Novikov 和 Boone 在 1950 年代证实，给出在一个有限出现群中的一个字，没有有效的过程来判定这个字所表示的元素是否是这个群的单位元素。这个结果被用来证实很多其他问题是不可判定的，比如两个有限单形(simplicial complex)是否表现同胚空间的问题。在 1970 年，Yuri Matiyasevich 对希尔伯特第十问题给出了否定答案，它提问是否有有效的过程来判定有有限多个有理数上的变量的丟番圖方程是否有在有理数上的解。这个否定解答是对 Martin Davis、Hilary Putnam 和 Julia Robinson 在 1961 年给出的部分解答的巩固。
递归论包括可计算性的一般概念的研究，比如超算术可归越性(hyperarithmetic)、α-递归论和可构成度(constructibility)。
[编辑] 链接
- 图灵度
- 多一归约
- 枚举归约
- 超算术理论
- 算术层次
- 分析层次
- 能行描述集合论
- 图灵机
[编辑] 引用
- S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, ISBN 1584882379 (textbook)
- Nigel J. Cutland, Computability, An introduction to recursive function theory, Cambridge University Press, ISBN 0521294657 (paperback), 1980.
- Herbert B. Enderton [1977] : Elements of Recursion Theory, in : Jon Barwise, ed., Handbook of Mathematical Logic, pp. 527-566.
- S. C. Kleene and E. L. Post [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379--407.
- Piergiorgio Odifreddi, Classical Recursion Theory, North-Holland, ISBN 0444872957 (textbook)
- Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0262680521 (paperback), ISBN 0070535221 (textbook)
- R. I. Soare, Computability and recursion, Bull. Symbolic Logic 2 (1996) 284-- 321.
- Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0387152997 (textbook)
