基本介紹
- 中文名：可計算論
- 外文名：Computability theory
- 所屬分支：證明論和能行描述集合論
簡介,概述：計算的概念,歷史,
簡介
可計算論，是一個數理邏輯分支。它起源於可計算函式和圖靈度的研究。它的領域增長為包括一般性的可計算性和可定義性的研究。在這些領域中，這門理論同證明論和能行描述集合論(effective descriptive set theory)有所重疊。
數理邏輯中的可計算性理論家經常研究相對可計算性、可歸約性概念和程度結構的理論。相對於計算機科學家，他們研究次遞歸層次，可行的計算和公用於可計算性理論研究的形式語言。在這兩個社區之間有著相當大的知識和方法上的重疊，而沒有明顯的界限。
概述：計算的概念
可計算論所考慮的基本問題是，給定一個從自然數到自然數的函式f，f是否是可以被計算的。“可以被計算”，我們先將其當作一個直觀的概念。根據直覺，人們一般會認為，一個函式可以被計算是存在一個給定的過程，接受一個自然數n後，該過程進行一定的操作並給出f(n)作為輸出。將計算這一直觀的概念上升到數學層面的形式化定義這一工作是可計算論的根本，並由哥德爾、邱奇、圖靈、克萊尼和 Emil Post等人在1930年代奠定。他們將圖靈可計算性作為有效計算的形式化。
在可計算論的基本概念被給定之後，一方面人們將該觀念套用於數學中，從而證明了一系列自然的問題，如字問題，以及希爾伯特第十問題等問題是不可計算的。另一方面，理論家們進一步拓展，開始了相對可計算性，圖靈度等問題的研究。如今，可計算論仍是數理邏輯中活躍的領域。
歷史
可計算論理論起源自哥德爾、邱奇、圖靈、克萊尼和Emil Post 在 1930 年代的工作。他們獲得的基本結果建立了圖靈可計算性作為有效計算的非正式想法的正確的形式化。通過能行計算的嚴格定義帶來了在數學中有些問題是不可有效判定的最初證明。邱奇和圖靈獨立的證明了停機問題不能能行判定，而 Post 證明了在Thue系統中確定一個字元串是否有規範形式(類似於在λ演算中一個項是否有規則形式)不能有效的確定。
不可解度結構的研究，包括圖靈度、多一度和類似的結構，是這個領域的重要部分。圖靈度的研究發起自 Kleene 和 Post [1954]。大量的可計算性理論中的研究已經投入到圖靈度的性質的研究中。開始於 1970 年代，圖靈度的研究焦點已經從局部結構性質轉移到全局性質，比如圖靈度的自同構(automorphism)和O的可定義性。
在 1930 年代確定了最初的例子之後，很多數學問題已經被證實是不可判定的。Novikov 和 Boone 在 1950 年代證實，給出在一個有限出現群中的一個字，沒有有效的過程來判定這個字所表示的元素是否是這個群的單位元素。這個結果被用來證實很多其他問題是不可判定的，比如兩個有限單形(simplicial complex)是否表現同胚空間的問題。在1970 年，尤里·馬季亞謝維奇對希爾伯特第十問題給出了否定答案，它提問是否有有效的過程來判定有有限多個有理數上的變數的丟番圖方程是否有在有理數上的解。這個否定解答是對 Martin Davis、Hilary Putnam 和 Julia Robinson 在 1961 年給出的部分解答的鞏固。
可計算論包括可計算性的一般概念的研究，比如超算術可歸越性(hyperarithmetic degrees)、α-可計算論和可構成度(constructibility degrees)。
