廣義遞迴論

　　把自然數集上定義的遞迴論推廣到其他數學結構上去而得到的數學理論。常見的有有窮類型對象上的遞迴論和序數上的遞迴論。

　　有窮類型物件如下定義：自然數稱為0型對象。由n型物件到自然數集的全函數稱為n+1型物件。一型物件φ的計算相當於有一個執行機械過程的機器M，對M輸入數n後可得到到輸出m=φ(n)。二型對象F(f，n)的計算相當於上述機器M外加上一個外部信息源即f的圖形。對輸入f，n，M對輸入n的計算時，常要問機外信息源f對某個變目的值，根據值的不同而依不同的步驟進行計算，最後給出輸出m=F(f，n)。上述兩類計算都是有窮步內完成的計算。三型對象F(F，f，n)的計算相當於上述機器M外加上兩個外部信息源即f的圖形(基數為堗₀)和F的圖形（基數為2

）。 M對輸入 n的計算時要問到 f對某變元的值，和問到 F對某變元的值。在問到 F對變元 g的值時要計算 g的圖形，因此此時 M的計算不再是有窮步內可停止的計算瞭。相仿地可有更高類型對象的計算。

　　還可以把遞歸論推廣到序數上去。最初是用集合論的工具，如降S-L定理，推廣到一切序數上去。後來發展為推廣到序數的某些前節上去。最主要的是推廣到可允許序數上去，稱為α－遞歸論。當α＞ω後出現瞭許多ω-遞歸論中不存在的現象，例如有界和有窮不再是相同的概念瞭，這就使α-遞歸論的證明大大地復雜瞭。

　　ω-遞歸論的某些結果可以推廣到一切可允許序數α上去，例如波斯特問題的解決。有些結果隻在某些可允許序數上成立，而在另一些可允許序數上不成立，如極大集的存在性定理。再如當α＞ω後，O′以下ω-度的結構和O′以α-度的結構不同構。