递归论

递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。

数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。

概述：计算的概念

递归论所考虑的基本问题是，给定一个从自然数到自然数的函数f，f是否是可以被计算的。“可以被计算”，我们先将其当作一个直观的概念。根据直觉，人们一般会认为，一个函数可以被计算是存在一个给定的过程，接受一个自然数n后，该过程进行一定的操作并给出f(n)作为输出。将计算这一直观的概念上升到数学层面的形式化定义这一工作是递归论的根本，并由哥德尔、邱奇、图灵、克莱尼和Emil Post等人在1930年代奠定。他们将图灵可计算性作为有效计算的形式化。

在递归论的基本概念被给定之后，一方面人们将该观念应用于数学中，从而证明了一系列自然的问题，如字问题，以及希尔伯特第十问题等问题是不可计算的。另一方面，理论家们进一步拓展，开始了相对可计算性，图灵度等问题的研究。如今，递归论仍是数理逻辑中活跃的领域。

历史

递归论理论起源自哥德尔、邱奇、图灵、克莱尼和Emil Post在1930年代的工作。他们获得的基本结果建立了图灵可计算性作为有效计算的非正式想法的正确的形式化。通过能行计算的严格定义带来了在数学中有些问题是不可有效判定的最初证明。邱奇和图灵独立的证明了停机问题不能进行判定，而Post证明了在Thue系统中确定一个字符串是否有规范形式（类似于在λ演算中一个项是否有规则形式）不能有效的确定。

不可解度结构的研究，包括图灵度、多一度和类似的结构，是这个领域的重要部分。图灵度的研究发起自Kleene和Post [1954]。大量的可计算性理论中的研究已经投入到图灵度的性质的研究中。开始于1970年代，图灵度的研究焦点已经从局部结构性质转移到全局性质，比如图灵度的自同构（automorphism）和 的可定义性。

在1930年代确定了最初的例子之后，很多数学问题已经被证实是不可判定的。Novikov和Boone在1950年代证实，给出在一个有限出现群中的一个字，没有有效的过程来判定这个字所表示的元素是否是这个群的单位元素。这个结果被用来证实很多其他问题是不可判定的，比如两个有限单形（simplicial complex）是否表现同胚空间的问题。在1970年，尤里·马季亚谢维奇对希尔伯特第十问题给出了否定答案，它提问是否有有效的过程来判定有有限多个有理数上的变量的丢番图方程是否有在有理数上的解。这个否定解答是对Martin Davis、Hilary Putnam和Julia Robinson在1961年给出的部分解答的巩固。

递归论包括可计算性的一般概念的研究，比如超算术可归约性（hyperarithmetic degrees）、α-递归论和可构成度（constructibility degrees）。

参见

  • μ算子
  • 图灵度
  • 多一归约
  • 枚举归约
  • 超算术理论
  • 算术层次
  • 分析层次
  • 能行描述集合论
  • 图灵机

引用

  • S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, ISBN 1-58488-237-9（textbook）
  • Nigel J. Cutland, Computability, An introduction to recursive function theory, Cambridge University Press, ISBN 0-521-29465-7 (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 0-444-87295-7（textbook）
  • Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1（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 0-387-15299-7（textbook）