递归函数的历史和家族

                  作者：张寅生

图灵机是数字电子计算机的理论模型，但不是一个纯粹的数学模型，因为它有物理装置的描述，而不是纯粹数或数学结构的描述。

如果用纯数学的语言描述图灵机的本质，这已有定论：图灵计算是递归可枚举计算。简单地说，递归是将函数计算结果带入本函数参数进行迭代计算的方法；枚举是递归函数的退化，简单说就是查数，其结果可以没有逻辑值（不管对错，只要依次映射到某个值，就算“枚举（生成转换）”到了这个对象）。

1936年，邱奇和图灵分别发现了通过可计算性实现可判定性的方法，这一点从他们阐述可计算性的论文标题----《论初等数论的不可解问题》[1]（邱奇）、《论可计算的数及其在判定问题上的应用》（图灵）[2]即可看出这一点。这两篇文章研究的背景是丢番图问题的判定问题，即对1900年希尔伯特提出的第10问题的求解：如何对于“给定了一个有任意个未知数的、系数为有理数的丢番图方程，设计一种方法，根据这种方法可以通过有限步运算来判别该方程是否有有理整数解”[3]。这在本质上是一个递归可枚举集上的命题的判定问题。

由于图灵机是图灵设计的，因此知道图灵的人很多，但是递归函数的设计者却容易被忽略了。实际上递归函数的设计者比图灵更早。换言之，图灵计算的数学模型不是图灵提出的，而是早于图灵。

1923年，斯科伦提出的递归函数的概念。追溯起来，递归的方法应用历史会更早，例如斐波那契（Leonardo Pisano，Fibonacci，Leonardo Bigollo，1175年-1250年）数列的计算。但是递归函数的概念首次提出和模型化的第一人是斯克伦（Thoralf Skolem，1887~1963年，挪威数学家）[4]。这个斯克伦，就是计算机领域更为大家所熟知的逻辑表达式量词“斯克伦化”的那个斯克伦。

此后，哥德尔于1931年提出“原始递归”的概念，将常值函数、后继函数和投影函数合称之为基本函数；而基本函数的复合则称为原始递归函数[5]。原始递归函数仍然局限于有穷计算，其无穷计算（如无穷除法或无理数计算）则依赖于一个误差函数最小化的近似计算，即所谓的最小值计算（μ-算符）。当然除了原始递归和μ-算符计算也有其他的递归运算，目前已经发现的是阿克曼递归函数，即所谓的超级指数递归(Superexponential Function Arithmetic，SEFA)[6]，因为它的递归速度比单指数递归更快！

1934年，哥德尔扩展了海伯伦（Herbrand）的递归定义，使用了“一般递归函数”或“广义递归函数”这一称呼表示除Herbrand所定义的递归函数外更为广泛的递归函数；而海伯伦对递归函数的定义相当于μ-递归函数[7]。

综合起来，递归函数从构建到目前，其家族和分类情况如何？

下表是我综合整理出的递归函数的逻辑结构分类：

        递归函数（广义递归函数）的分类^[6]

参考文献：

[1]Alonzo Church. An Unsolvable Problem of Elementary Number Theory,AmericanJournal of Mathematics , Vol. 58, No. 2. (Apr., 1936), pp. 345-363.          

[2] AlanTuring.On Computable Numbers, with an application to the Entscheidungsproblem,

Proceedingsof the London Mathematical Society, 42(1936-37):230,231,262.

[3] 希尔伯特.数学问题,编译：李文林、袁向东.大连：大连理工大学出版社，2009（ 66）。

[4]Thoralf Skolem.The foundation of elementary arithmetic established by means of therecursion mode of thought,without the use of apparent variables ranging overinfinite domains./FromFrege to Godel//A Source Book in Mathematical Logic,1879~1931.Havard UniversityPress,1977:302~333.

[5] Kurt Godel.On FormallyUndecidable Propositions of Principia Mathematica and Related SystemI.From Frege to Godel,Harvard University Press,pp.592-.617.

[6]张寅生.证明方法与理论。国防工业出版社，2015.

[7]Bobert Soar. Computebility and Recursion,Bulletin of Symbolic Logic,Vol.2,Num.3,1996:284-321.