在可计算性理论中，原始递归函数大致是指可以由计算机程序计算的函数，其循环都是“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éter和Raphael 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 :
[2] https://en.wikipedia.org/wiki/Ackermann_function
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1339183.html?mobile=1
收藏
