原始遞歸函數
維基百科,自由的 encyclopedia
在可計算性理論中,原始遞歸函數(英語:primitive recursive functions)對計算的完全的形式化而言是形成重要構造板塊的一類函數。它們使用遞歸和複合作為中心運算來定義,並且是遞歸函數的嚴格的子集,它們完全是可計算函數。通過補充允許偏函數和介入無界尋找運算可以定義出遞歸函數的更廣泛的類。
通常在數論中研究的很多函數,近似於實數值函數,比如加法、除法、階乘、指數,找到第 n 個質數等等是原始遞歸的(Brainerd and Landweber, 1974)。實際上,很難設計不是原始遞歸的函數,儘管某些函數是已知的(比如阿克曼函數)。所以,通過研究它們,我們能發現有廣泛影響的結論的那些性質。