-
一般遞歸函數
鎖定
一般遞歸函數(general recursive function)亦稱遞歸函數，是指一類具有能行可計算的全數論函數。不僅如此，現在一般認為，能行可計算的全數論函數恰好就是一般遞歸函數，一般遞歸函數的概念最初是由美籍奧地利數學家哥德爾於1934年定義的，也就是現在所謂的埃爾布朗-哥德爾可計算函數，即若一個數論函數可由某個等式系ε定義，則哥德爾稱f為一般遞歸的。1936年，美國邏輯學家、數學家克林(S.C.Kleene)引進了μ遞歸函數的概念，並進而證明了它恰好與哥德爾的一般遞歸函數類一致。此後，一般遞歸函數的概念便經常用μ遞歸的形式給出。莫紹揆於1965年利用一般遞歸式的概念提出了一般遞歸函數的另一種等價定義形式：從本原函數出發，經疊置和一般遞歸式作用而生成的函數稱為一般遞歸式。注意到，比起等式系或μ算子來，一般遞歸式更好地體現了一般遞歸的意義，因此，利用一般遞歸式引入一般遞歸函數概念當是最為合理的。而且也是原始遞歸函數概念的一種自然推廣。此外，一般遞歸函數恰好是部分遞歸函數中的全函數，不過與全體部分遞歸函數不一樣，全體一般遞歸函數不是能行可列的
[1]
。
- 中文名
- 一般遞歸函數
- 外文名
- general recursive function
- 別 名
- 遞歸函數
- 屬 性
- 一類具有能行可計算的全數論函數
- 相關概念
- 原始遞歸函數
- 提出者
- 哥德爾
一般遞歸函數發展簡要
一般遞歸函數(gereral recursive function)是原始遞歸函數的推廣。二十世紀初，為了一般地定義能行過程便引進了一般遞歸函數的概念。這個概念最初是哥德爾在厄爾勃朗的信的啓示下提出來的。後來，克林改進了哥德爾的定義並發展了一般遞歸函數的理論。在此之前，邱吉引進了
記號，定義了
可定義函數的概念。以後，波斯特和圖靈又引進了圖靈機器並定義了可計算函數的概念。後來證明所有這些概念都與一般遞歸函數等價。由此可見，一般遞歸函數是非常重要的
[2]
。一般遞歸函數集包含原始遞歸函數集為其真子集。
一般遞歸函數基本介紹
凡原始遞歸函數都是一般遞歸函數，反之不然。要找一個非原始遞歸函數的一般遞歸函數並不是一件容易的事。這就説明日常遇到的數論函數幾乎都是原始遞歸函數。第一個找出非原始遞歸函數的例子的是德國數學家阿克曼，從而證實了一般遞歸函數的確比原始遞歸函數為廣。
常見的一般遞歸函數的定義有兩種，第一種都是在原始遞歸函數的定義中加進另一種則使用一般遞歸式，摹狀式而得。
一般遞歸式通常寫為：
摹狀式一般寫為：
已經證明這兩個定義是等價的。邱吉建議把一般遞歸函數考慮為能行可計算函數的數學定義。這個論斷被稱為邱吉論題。由於可計算函數是個無定義概念，所以，邱吉論題是無法證明的。但是，根據種種理由，大家都相信它是正確的 。這樣，凡是有一個計算過程或一個算法可以將函數值計算出來的函數便都是一般遞歸函數。利用這一結果解決了許多懸而未決的判定問題，重新研究了傳統的描述集合論，闡明瞭半直覺主義數學中所使用的能行性概念，促進了新興的計算機科學的發展
[2]
。
