[科普中國(guó)]-一般遞歸函數(shù)

一般遞歸函數(shù)(general recursive function)亦稱遞歸函數(shù)，是指一類具有能行可計(jì)算的全數(shù)論函數(shù)。不僅如此，現(xiàn)在一般認(rèn)為，能行可計(jì)算的全數(shù)論函數(shù)恰好就是一般遞歸函數(shù)，一般遞歸函數(shù)的概念最初是由美籍奧地利數(shù)學(xué)家哥德爾于1934年定義的，也就是現(xiàn)在所謂的埃爾布朗-哥德爾可計(jì)算函數(shù)，即若一個(gè)數(shù)論函數(shù)可由某個(gè)等式系ε定義，則哥德爾稱f為一般遞歸的。1936年，美國(guó)邏輯學(xué)家、數(shù)學(xué)家克林(S.C.Kleene)引進(jìn)了μ遞歸函數(shù)的概念，并進(jìn)而證明了它恰好與哥德爾的一般遞歸函數(shù)類一致。此后，一般遞歸函數(shù)的概念便經(jīng)常用μ遞歸的形式給出。莫紹揆于1965年利用一般遞歸式的概念提出了一般遞歸函數(shù)的另一種等價(jià)定義形式：從本原函數(shù)出發(fā)，經(jīng)疊置和一般遞歸式作用而生成的函數(shù)稱為一般遞歸式。注意到，比起等式系或μ算子來，一般遞歸式更好地體現(xiàn)了一般遞歸的意義，因此，利用一般遞歸式引入一般遞歸函數(shù)概念當(dāng)是最為合理的。而且也是原始遞歸函數(shù)概念的一種自然推廣。此外，一般遞歸函數(shù)恰好是部分遞歸函數(shù)中的全函數(shù)，不過與全體部分遞歸函數(shù)不一樣，全體一般遞歸函數(shù)不是能行可列的1。

發(fā)展簡(jiǎn)要一般遞歸函數(shù)(gereral recursive function)是原始遞歸函數(shù)的推廣。二十世紀(jì)初，為了一般地定義能行過程便引進(jìn)了一般遞歸函數(shù)的概念。這個(gè)概念最初是哥德爾在厄爾勃朗的信的啟示下提出來的。后來，克林改進(jìn)了哥德爾的定義并發(fā)展了一般遞歸函數(shù)的理論。在此之前，邱吉引進(jìn)了記號(hào)，定義了可定義函數(shù)的概念。以后，波斯特和圖靈又引進(jìn)了圖靈機(jī)器并定義了可計(jì)算函數(shù)的概念。后來證明所有這些概念都與一般遞歸函數(shù)等價(jià)。由此可見，一般遞歸函數(shù)是非常重要的2。一般遞歸函數(shù)集包含原始遞歸函數(shù)集為其真子集。

基本介紹凡原始遞歸函數(shù)都是一般遞歸函數(shù)，反之不然。要找一個(gè)非原始遞歸函數(shù)的一般遞歸函數(shù)并不是一件容易的事。這就說明日常遇到的數(shù)論函數(shù)幾乎都是原始遞歸函數(shù)。第一個(gè)找出非原始遞歸函數(shù)的例子的是德國(guó)數(shù)學(xué)家阿克曼，從而證實(shí)了一般遞歸函數(shù)的確比原始遞歸函數(shù)為廣。

常見的一般遞歸函數(shù)的定義有兩種，第一種都是在原始遞歸函數(shù)的定義中加進(jìn)另一種則使用一般遞歸式，摹狀式而得。

一般遞歸式通常寫為：

其中，為歸宿于零的函數(shù)，即從任何一值(作為第一變?cè)?經(jīng)過有限次迭置之后的值必為零。

摹狀式一般寫為：

但要求對(duì)任何都有使得

其中，表示滿足(1)的最小自然數(shù)。

已經(jīng)證明這兩個(gè)定義是等價(jià)的。邱吉建議把一般遞歸函數(shù)考慮為能行可計(jì)算函數(shù)的數(shù)學(xué)定義。這個(gè)論斷被稱為邱吉論題。由于可計(jì)算函數(shù)是個(gè)無定義概念，所以，邱吉論題是無法證明的。但是，根據(jù)種種理由，大家都相信它是正確的 。這樣，凡是有一個(gè)計(jì)算過程或一個(gè)算法可以將函數(shù)值計(jì)算出來的函數(shù)便都是一般遞歸函數(shù)。利用這一結(jié)果解決了許多懸而未決的判定問題，重新研究了傳統(tǒng)的描述集合論，闡明了半直覺主義數(shù)學(xué)中所使用的能行性概念，促進(jìn)了新興的計(jì)算機(jī)科學(xué)的發(fā)展2。

本詞條內(nèi)容貢獻(xiàn)者為:

王海俠 - 副教授 - 南京理工大學(xué)