递归论（Recursion theory）是数理逻辑的重要分支之一，研究解决问题的可行的计算方法和计算的复杂程度的一门学科，尤其是研究递归函数及其推广。递归论研究的函数主要包括本原函数、原始递归函数、递归半函数和递归全函数或称一般递归函数、可摹状函数等等。
中文名递归论
类型数理逻辑的重要分支之一
外文名Recursion theory
研究函数
递归论简介
递归论亦称可计算性理论(computability theory)，数理逻辑分支之一。它是研究关于可计算性与可定义性的数学理论，主要关注于事物的可计算性，可定义性及其分层。递归论起源于20 世纪30 年哥德尔、丘奇、图灵、克林和波斯特(E.Post) 等关于自然数集合的可计算性的研究。
经典递归论
经典的递归论关注于自然数集合的可计算性。绝大多数自然数集合都是不可计算的。对于不可计算的集合，可以加以复杂性比较。例如图灵归约就是一种典型的比较方式。这些比较可以看作一种广义上的分层。递归论关注于这些比较方式及其产生的代数结构。对于这些比较方式产生的代数结构的研究已经形成门被称为度论的比较成熟的领城。这些度结构中以图灵度的研究最为广泛。它们的研究起源于克林和波斯特。
对于一般图灵度的结构的研究，早期经过克林、弗赖德贝格(R.M.Fiedberg)、斯佩克特(C Spector)、萨克斯(G.Sacks)、休恩菲尔德、耶茨(C.E M.Yates)、库珀(S.B.Coper) 等的长期积累，证明了大量的关于图灵度的局部性质并且引入了许多构造图灵度的方法。
20 世纪80年代开始图灵度的结构研究开始转向大范围结构的研究，即更加关注于图灵度结构的模型论性质及其理论的可判定性。
关于图灵度结构理论的可判定性，1977 年辛普森(S.Simpson) 证明了图灵度的结构理论与二阶算术是递归同构的，从而刻画了图灵度结构理论的复杂性。
对于图灵度结构理论的片段，克林和波斯特事实上已经证明了图灵度的理论是可判定的。
施梅尔(J.Schmerl) 证明了图灵度的理论是不可判定的。莱尔曼(M.Lerman) 和肖尔(R.Shore) 最终证明了理论是不可判定的。
关于图灵度结构的模型论性质有两个非常重要也非常困难的问题。第一个问题: 图灵跃变是否在一般图灵度结构中可定义? 第二个问题: 是否存在图灵度的非平凡自同构? 有不少人曾致力于解决这些问题。最后，第一个问题由思莱曼(T.Slaman) 和肖尔于1999 年在思莱曼和武丁工作的基础上用完全不同于以前的方法肯定地解决。而迄今为止，第二个问题依然悬而未决。最近的进展是思莱曼和武丁证明了图灵度结构的自同构群至多可数。
递归可枚举的图灵度的结构问题也是这一领域广受关注的课题之一。它起源于波斯特关于是否存在严格介于递归集和停机问题（即图灵跃变） 的递归可枚举图灵度的问题。
这一问题被穆奇尼克(A.Muchnik) 和弗赖德贝格分别给予了肯定的答案。他们引入的现在被称为有穷损害的方法已经成为这一领域的基本工具之一。后来休恩菲尔德、萨克斯、拉克伦(A.Lachlan) 分别引入了无穷损害以及所谓的0'''优先方法，这些方法现在已经成为强有力的构造递归可枚举图灵度的工具。
20 世纪80 年代开始研究开始转向递归可枚举图灵度的模型论结构理论。
可判定性方面，1982 年哈林顿和谢拉赫证明了递归可枚举图灵度结构的理论是不可判定的。
萨克斯证明了递归可枚举图灵度的理论是可判定的。兰普(S.Lempp)、尼斯(A.Nies) 和思莱曼证明了递归可枚举图灵度的理论是不可判定的。关于递归可枚举图灵度的理论是否可判定仍然未知。
哈林顿和思莱曼，思莱曼和武丁，尼斯和肖尔以及思莱曼先后用不同的编码方法证明了递归可枚举图灵度的理论与一阶算术理论是递归同构的，因此刻画了递归可枚举图灵度理论的复杂性。模型论方面，尼斯、肖尔和思莱曼证明了递归可枚举度中许多类是可定义的。但递归可枚举度低度是否在递归可枚举图灵度中可定义仍然未知。
广义递归论
广义的递归论研究一般数学事物的可计算性和可定义性。一般有两种方式推广经典的递归论。一种是把图灵机加以推广。例如，把图灵机推广到实数上就能研究实数集合的可计算性，把图灵机推广到序数上，就能研究序数集合的可计算性。魏劳赫(K.Weihrauch) 提出的实数上的图灵机以及布卢姆(L Blum).舒布(M.Shub) 和斯梅尔(S.Smale) 提出的BSS 机器都是这一方向比较流行的理论。另外一种推广方式是研究可定义性。可定义性本身可以看作可计算性的推广。因此递归论学家可以运用经典的递归论工具研究一类特定的可定义集合的性质。这一方向往往与集合论相交叉。例如，博雷尔集就是超算术实数集的“相对化”，可构成集合可以看成一种广义的递归的集合等。
应用
近来递归论更多地关注于它对其他学科的应用。例如，递归模型论、反推数学、算法随机性理论都是现在广泛关注的领城，递归论在这些领城中都有成功的应用。[1]
相关推荐
最新文章