遞歸論，是數(shù)理邏輯的一個(gè)分支。它是一門研究遞歸涵數(shù)及其推廣的學(xué)科。遞歸函數(shù)是數(shù)論函數(shù)的一種，其定義域與值域都是自然數(shù)集。只是由于構(gòu)作函數(shù)方法的不同而有別于其他的數(shù)論涵數(shù)。將定義域推廣到不限于自然數(shù)集時(shí)，便是所謂廣義的遞歸函數(shù)。
歷史介紹
遞歸論這門學(xué)科最早可以追溯到原始遞歸式的使用。古代人以及現(xiàn)代的兒童對加法及乘法的理解，實(shí)質(zhì)上就是使用原始遞歸式。但直到17世紀(jì)，法國學(xué)者B.巴斯加爾才正式使用與遞歸式密切相關(guān)的數(shù)學(xué)歸納法。19世紀(jì)德國數(shù)學(xué)家R.戴德金德和意大利的G.皮亞諾正式使用原始遞歸式，以定義加法與乘法，從而發(fā)展了整個(gè)自然數(shù)論。1923年，T.司寇倫提出并初步證明一切初等數(shù)論中的函數(shù)都可以由原始遞歸式作出，即都是原始遞歸函數(shù)。1931年，庫爾特·卡塞雷斯在證明其著名的不完全性定理時(shí)，以原始遞歸式為主要工具把所有元數(shù)學(xué)的概念都算術(shù)化了。原始遞歸函數(shù)的重要性遂受到人們的重視，人們開始猜測，原始遞歸函數(shù)可能窮盡一切可計(jì)算的函數(shù)。但是，德國數(shù)學(xué)家W.阿克曼的非原始遞歸的可計(jì)算函數(shù)的出現(xiàn)，否定了這個(gè)猜測，同時(shí)也要求人們探討原始遞歸函數(shù)以外的可計(jì)算函數(shù)。1934年，哥德爾在J.赫爾布蘭德的啟示之下，提出了一般遞歸函數(shù)的定義；美國的S.C.克利尼則于1936年證明了這樣定義的一般遞歸函數(shù)和A.阿隆佐·邱奇所定義的λ可定義函數(shù)是相同的，并給出了幾種相等價(jià)的定義。這樣的一般遞歸函數(shù)后來被稱為赫爾布蘭德-哥德爾-克利尼定義。1936年，丘奇、A.M.圖林各自獨(dú)立地提出一個(gè)論點(diǎn)，即凡可計(jì)算的函數(shù)都是一般遞歸函數(shù)，這就把遞歸函數(shù)論與能行性論緊緊地結(jié)合起來，從而使遞歸函數(shù)的應(yīng)用范圍大大地?cái)U(kuò)展了（見能行性與一般遞歸）。關(guān)于遞歸函數(shù)本身的進(jìn)展主要在于定義域的推廣，從而得到遞歸字函數(shù)、a遞歸函數(shù)和遞歸泛涵等等。
基本內(nèi)容
遞歸論研究的函數(shù)主要包括本原函數(shù)、原始遞歸函數(shù)、遞歸半函數(shù)和遞歸全函數(shù)或稱一般遞歸函數(shù)、可摹狀函數(shù)等等。
本原函數(shù)
處處有定義的函數(shù)叫做全函數(shù)，未必處處有定義的函數(shù)叫做半函數(shù)或部分函數(shù)。最簡單、最基本的函數(shù)有三個(gè)，即①零函數(shù)，,其值永為0；②廣義幺函數(shù)或射影函數(shù),；③后繼函數(shù)，。這三個(gè)函數(shù)的合稱就叫做本原函數(shù)。
要想由舊函數(shù)而作出新函數(shù)，必須使用各種各樣的算子以及疊置。疊置又名復(fù)合或代入，它是最簡單、最重要的構(gòu)造新函數(shù)的方法。其一般形式是：由一個(gè) m元函數(shù) f與 m個(gè) n元函數(shù)而造成新函數(shù),后者亦可記為。最常見的造新函數(shù)的算子是原始遞歸式。具有n個(gè)參數(shù)的原始遞歸式如下：
只有一個(gè)參數(shù)的原始遞歸式為：
遞歸論
其特點(diǎn)是：不能由A、B兩函數(shù)而直接計(jì)算新函數(shù)的一般值f(u,x)，而只能依次計(jì)算但只要依次計(jì)算，必能把任何一個(gè)f(u,x) 值都算出來。這就是說，只要A、B為全函數(shù)且可計(jì)算，則新函數(shù)f也是全函數(shù)且可計(jì)算。
原始遞歸函數(shù)
由本原函數(shù)出發(fā)，經(jīng)過有限次的疊置與原始遞歸式而作出的函數(shù)叫做原始遞歸函數(shù)。由于本原函數(shù)是全函數(shù)且可計(jì)算，故原始遞歸函數(shù)也是全函數(shù)且可計(jì)算。原始遞歸函數(shù)所涉及的范圍很廣，在數(shù)論中所使用的數(shù)論函數(shù)全是原始遞歸函數(shù)。阿克曼卻證明了一個(gè)不是原始遞歸的可計(jì)算的全函數(shù)。經(jīng)過后人改進(jìn)后，可表述為如下定義的函數(shù)：
這個(gè)函數(shù)是處處可以計(jì)算的。任給 m,n值，如果m為0,可由第一式算出；如果m不為 0而n為0,可由第二式化歸為求的值，這時(shí)第一變目減少了，如果m,n均不為0，根據(jù)第三式可先計(jì)算(設(shè)為A),再計(jì)算，前者g的第二變目減少而第一變目不變，后者則第一變目減少。這樣一步步地化歸，最后必然化歸到第一變目為0，從而可用第一式計(jì)算。此外，對任一個(gè)一元原始遞歸函數(shù)f(x),都可找出一數(shù)a使。這樣,就不可能是原始遞歸函數(shù)。
原始遞歸式的推廣，可得到下列有序遞歸式或半遞歸式：
它與原始遞歸式的不同點(diǎn)，在于它不是把的計(jì)算化歸于f(u,x,)的計(jì)算，而是先化歸于的計(jì)算，然后化歸于的計(jì)算(可寫成f(u,g娾Sx))，再化歸于f(u,g咺Sx)的計(jì)算，等等。如果有一個(gè)m使得g嚲即函數(shù)gu在Sx處歸宿于0，那末最后化歸的f(u,g嚲Sx)的計(jì)算，將由第一式知，依次逐步倒退便可以計(jì)算了。如果任何 m均使得g嚲，即函數(shù)gu在Sx處不歸宿于0,將導(dǎo)致永遠(yuǎn)化歸下去而得不到結(jié)果。這樣，不但不能計(jì)算，而且它本身根本沒有定義。由此可見，即使A、B與g是處處有定義且可計(jì)算的，而由半遞歸式所定義的函數(shù)未必是全函數(shù)，也可能是半函數(shù)。但只要有定義的地方，即gu歸宿于0的地方，就必能計(jì)算。
遞歸半函數(shù)和遞歸全函數(shù)
從本原函數(shù)出發(fā)經(jīng)過有限次的疊置與半遞歸式構(gòu)成的函數(shù)叫做遞歸半函數(shù)或遞歸部分函數(shù)，也叫做半遞歸函數(shù)或部分遞歸函數(shù)。這里所提到的“半”、“部分”不是限制“遞歸”而是限制“函數(shù)”的。如果作出的函數(shù)是全函數(shù)，即其中的gu是處處歸宿于 0的，便叫做遞歸全函數(shù)也叫做一般遞歸函數(shù)。遞歸半函數(shù)的特點(diǎn)是，它可能沒有定義從而沒有值，但只要有值必然可以計(jì)算。一般遞歸函數(shù)的特點(diǎn)是，它必處處有定義而且處處可以計(jì)算。當(dāng)遞歸半函數(shù)沒有定義時(shí)，一般是不知道的。這樣，即使把化歸于，再化歸于如此永遠(yuǎn)計(jì)算下去，也始終得不到其值，并且始終不知道它沒有值。但如果另有辦法判定遞歸半函數(shù)是否有值，即是否有定義，情況便大不相同。凡是能夠判定某個(gè)遞歸半函數(shù)是否有值的，該遞歸半函數(shù)叫做潛伏遞歸函數(shù)。對潛伏遞歸函數(shù)永可在有限步內(nèi)得出其值，或知道它沒有值，而與一般遞歸函數(shù)相同。
另一個(gè)重要的構(gòu)造新函數(shù)的方法是造逆函數(shù)，例如由加法造減法，由乘法造除法等。設(shè)已有函數(shù)f（u,x）（只寫一個(gè)參數(shù)u）就x解方程可得，這時(shí)函數(shù) g 叫做f（作為 x的函數(shù)）的逆函數(shù)，可記為，至于解一般的方程而得可以看作求逆函數(shù)，即三元函數(shù)f的逆的推廣，解方程可以看作使用求根算子，又叫摹狀算子。的最小x根，記為,但當(dāng)該方程沒有根時(shí)，則認(rèn)為, 沒有定義。因此，即使f(u,t,x)處處有定義且可計(jì)算，但使用摹狀算子后所得的函數(shù)仍不是全函數(shù)，可為半函數(shù)。且只要它有定義，那就必然可以計(jì)算。如果f(u,t,x) 本身就是半函數(shù)，則的意義是：當(dāng)可計(jì)算且其值為0,而時(shí)f(u,t,x)均可計(jì)算，且其值非0,則指n。此外的情況均作為無定義看待。
可摹狀函數(shù)
由本原函數(shù)出發(fā)，經(jīng)過有限次疊置原始遞歸式與摹狀式而構(gòu)成的函數(shù)叫做可摹狀函數(shù)。可摹狀函數(shù)一般是部分函數(shù)，當(dāng)摹狀算子處處有定義時(shí)，它才是全函數(shù)。但不管是否全函數(shù)，凡可摹狀函數(shù)有定義的地方都是可計(jì)算的。已經(jīng)證明，可摹狀函數(shù)與遞歸半函數(shù)是相同的，可摹狀的全函數(shù)與一般遞歸函數(shù)也是相同的。凡可摹狀函數(shù)都可以構(gòu)作一個(gè)圖林機(jī)器（見圖林機(jī)器理論）計(jì)算它，使得當(dāng)函數(shù)有定義時(shí)，相應(yīng)的圖林機(jī)器必能終止計(jì)算并給出其值；當(dāng)函數(shù)沒有定義時(shí)，相應(yīng)的機(jī)器或者停止并給出沒有定義的信號，或者永不停止。由于遞歸函數(shù)可以與其性質(zhì)這樣不同的函數(shù)類相等價(jià)，因此阿隆佐·邱奇和圖林同時(shí)提出：可計(jì)算函數(shù)類恰好是遞歸函數(shù)，可計(jì)算的半、全函數(shù)分別是遞歸半、全函數(shù)。他們的這個(gè)論點(diǎn)現(xiàn)已受到數(shù)理邏輯學(xué)界的一致贊同，并被當(dāng)作能行性理論的一個(gè)基礎(chǔ)。
參考資料 >