不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

原始递归函数溯源

已有 501 次阅读 2022-5-19 02:50 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

在可计算性理论中,原始递归函数大致是指可以由计算机程序计算的函数,其循环都是“for”循环(也就是说,在进入循环之前就可以确定每个循环的迭代次数的上限)。原始递归函数构成了一般递归函数的一个严格的子集。


1. 历史


递归定义以前在数学中被形式或非形式使用过,但原始递归函数的构造可以追溯到理查德·戴德金 "Was sind und was sollen die Zahlen? (1888). 这项工作是第一个给出某个递归结构定义了唯一函数的证明。


原始递归算术是由Thoralf Skolem首次提出的1923年。


目前的原始递归函数术语是由Rózsa Péter提出(1934年),在阿克曼1928年证明了今天以他名字命名的函数不是原始递归函数之后,这一事件促使人们需要重新命名在那之前被简单称为递归函数的东西。


2. 阿克曼函数


在可计算性理论中,以威廉-阿克曼(Wilhelm Ackermann)命名的阿克曼函数,是最早发现的非原始递归的完全可计算函数的最简单例子之一。所有的原始递归函数都是完全可计算的,但阿克曼函数说明了并非所有完全可计算的函数都是原始递归的。


20世纪20年代末,大卫-希尔伯特的学生加布里埃尔-苏丹和威廉-阿克曼正在研究计算的基础。苏丹和阿克曼都被认为发现了非原始递归的全部可计算函数(在一些参考文献中被简单地称为 "递归")


在《论无限》中,大卫-希尔伯特假设阿克曼函数不是原始递归,希尔伯特的学生阿克曼在他的论文《论希尔伯特的实数构造》中证明了这个假设。

Rózsa PéterRaphael Robinson后来开发了一个阿克曼函数的双变量版本,就是现在人们所谈及的:

A(0, n) = n+1

A(m+1, 0) = A(m, 1)

A(m+1, n+1) = A(m, A(m+1,n))


Reference :

[1] https://en.wikipedia.org/wiki/Primitive_recursive_function#:~:text=In%20computability%20theory%2C%20a%20primitive,determined%20before%20entering%20the%20loop).

[2] https://en.wikipedia.org/wiki/Ackermann_function





https://blog.sciencenet.cn/blog-2322490-1339183.html

上一篇:Rózsa Péter,递归函数理论的创始人
下一篇:亚历山大·格罗滕迪克,代数几何的创始人

1 杨正瓴

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

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-7-2 04:22

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部