遞歸論

遞歸論或可計算性理論，是一個數理邏輯分支。它起源於可計算函數和圖靈度的研究。它的領域增長為包括一般性的可計算性和可定義性的研究。在這些領域中，這門理論同證明論和能行描述集合論（effective descriptive set theory）有所重疊。

數理邏輯中的可計算性理論家經常研究相對可計算性、可歸約性概念和程度結構的理論。相對於計算機科學家，他們研究次遞歸層次，可行的計算和公用於可計算性理論研究的形式語言。在這兩個社區之間有着相當大的知識和方法上的重疊，而沒有明顯的界限。

概述：計算的概念

遞歸論所考慮的基本問題是，給定一個從自然數到自然數的函數f，f是否是可以被計算的。「可以被計算」，我們先將其當作一個直觀的概念。根據直覺，人們一般會認為，一個函數可以被計算是存在一個給定的過程，接受一個自然數n後，該過程進行一定的操作並給出f(n)作為輸出。將計算這一直觀的概念上升到數學層面的形式化定義這一工作是遞歸論的根本，並由哥德爾、邱奇、圖靈、克萊尼和Emil Post等人在1930年代奠定。他們將圖靈可計算性作為有效計算的形式化。

在遞歸論的基本概念被給定之後，一方面人們將該觀念應用於數學中，從而證明了一系列自然的問題，如字問題，以及希爾伯特第十問題等問題是不可計算的。另一方面，理論家們進一步拓展，開始了相對可計算性，圖靈度等問題的研究。如今，遞歸論仍是數理邏輯中活躍的領域。

歷史

遞歸論理論起源自哥德爾、邱奇、圖靈、克萊尼和Emil Post在1930年代的工作。他們獲得的基本結果建立了圖靈可計算性作為有效計算的非正式想法的正確的形式化。通過能行計算的嚴格定義帶來了在數學中有些問題是不可有效判定的最初證明。邱奇和圖靈獨立的證明了停機問題不能進行判定，而Post證明了在Thue系統中確定一個字符串是否有規範形式（類似於在λ演算中一個項是否有規則形式）不能有效的確定。

不可解度結構的研究，包括圖靈度、多一度和類似的結構，是這個領域的重要部分。圖靈度的研究發起自Kleene和Post [1954]。大量的可計算性理論中的研究已經投入到圖靈度的性質的研究中。開始於1970年代，圖靈度的研究焦點已經從局部結構性質轉移到全局性質，比如圖靈度的自同構（automorphism）和$0'$的可定義性。

在1930年代確定了最初的例子之後，很多數學問題已經被證實是不可判定的。Novikov和Boone在1950年代證實，給出在一個有限出現群中的一個字，沒有有效的過程來判定這個字所表示的元素是否是這個群的單位元素。這個結果被用來證實很多其他問題是不可判定的，比如兩個有限單形（simplicial complex）是否表現同胚空間的問題。在1970年，尤里·馬季亞謝維奇對希爾伯特第十問題給出了否定答案，它提問是否有有效的過程來判定有有限多個有理數上的變量的丟番圖方程是否有在有理數上的解。這個否定解答是對Martin Davis、Hilary Putnam和Julia Robinson在1961年給出的部分解答的鞏固。

遞歸論包括可計算性的一般概念的研究，比如超算術可歸約性（hyperarithmetic degrees）、α-遞歸論和可構成度（constructibility degrees）。

參見

• μ算子
• 圖靈度
• 多一歸約
• 枚舉歸約
• 超算術理論
• 算術層次
• 分析層次
• 能行描述集合論
• 圖靈機

引用

• S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, ISBN 1-58488-237-9（textbook）
• Nigel J. Cutland, Computability, An introduction to recursive function theory, Cambridge University Press, ISBN 0-521-29465-7 (paperback), 1980.
• Herbert B. Enderton [1977] : Elements of Recursion Theory, in : Jon Barwise, ed., Handbook of Mathematical Logic, pp. 527-566.
• S. C. Kleene and E. L. Post [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379--407.
• Piergiorgio Odifreddi, Classical Recursion Theory, North-Holland, ISBN 0-444-87295-7（textbook）
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1（textbook）
• R. I. Soare, Computability and recursion, Bull. Symbolic Logic 2 (1996) 284-- 321.
• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7（textbook）