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