张寅生的个人博客分享 http://blog.sciencenet.cn/u/zhangbeijing 探索者:数理逻辑、人工智能

博文

递归函数的历史和家族

已有 4504 次阅读 2016-4-17 09:43 |个人分类:超数学|系统分类:论文交流|关键词:递归函数| 递归函数

           

   递归函数的历史和家族


                  作者:张寅生


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

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

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.




http://blog.sciencenet.cn/blog-320682-970653.html

上一篇:希尔伯特第24个数学问题
下一篇:逻辑的灵魂与意义

3 郑波尽 yangb919 zjzhaokeqin

该博文允许注册用户评论 请点击登录 评论 (4 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-12-10 08:55

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部