高型遞歸論（higher recursion theory）是一種遞歸理論。是把自然數上的遞歸論推廣到高型對象上得到的數學理論。事實上，一型的遞歸對象(遞歸函式)與二型遞歸對象(遞歸泛函)可以劃入經典遞歸論的範疇，這種遞歸性可以成功地被推廣到更高型對象上.通過重複從較低型對象向較高型對象推廣的一致過程，可得到較高型對象上的遞歸性定義.例如，一型對象的計算相當於有一個執行機械過程的機器M，對M輸人數n後可得到輸出m一抓n。二型對象F(f,n)的計算相當於在上述M處再加上一個外部信息源f.對輸人f,n,M在計算n時，要問到f對某些變元的值.三型象.(F,f,n)相當於在M之上加上兩個外部信息源f和G其圖象的基數為2'，當計算n時，M要問到f對某變元集，同時還要問到F對某變元的值.在問到F對變元g的值時，要計算g的圖象，因此M的計算不再有窮.類似可有更高型對象的計算。
基本介紹
- 中文名：高速遞歸論
- 外文名：higher recursion theory
介紹
高型遞歸論(higher recursion theory)一種遞歸理論.是把自然數上的遞歸論推廣到高型對象上得到的數學理論.事實上，一型的遞歸對象(遞歸函式)與二型遞歸對象(遞歸泛函)可以劃入經典遞歸論的範疇，這種遞歸性可以成功地被推廣到更高型對象上.通過重複從較低型對象向較高型對象推廣的一致過程，可得到較高型對象上的遞歸性定義.例如，一型對象的計算相當於有一個執行機械過程的機器M，對M輸人數n後可得到輸出m一抓n.二型對象F(f,n)的計算相當於在上述M處再加上一個外部信息源f.對輸人f,n,M在計算n時，要問到f對某些變元的值.三型象.(F,f,n)相當於在M之上加上兩個外部信息源f和G(其圖象的基數為2')，當計算n時，M要問到f對某變元集，同時還要問到F對某變元的值.在問到F對變元g的值時，要計算g的圖象，因此M的計算不再有窮.類似可有更高型對象的計算.
對高型對象而言，緊緻性不再成立，“計算”的概念也不再有原來的“能行性”了.產運算元也失去了它在經典遞歸定義中的中心地位(從上面的例子看出，在高型對象的計算中，搜尋範圍可能不再是可數無窮了)，因此其研究變得為複雜了.這一方向的研究最早由美國邏輯學家、數學家克林(Kleene , S.C.)提出的.
將遞歸論推廣到高型對象的另一條途徑是通過緊緻性、單調性和連續性進行的.這一方向的研究是由美國學者戴維斯(Davis,M. D. )、克林和克雷塞爾Kreisel , G.提出的.他們的基本觀點是:計算樹仍然是有窮的.這一方向的研究發展成為可數泛函理論.
