計算理論
計算理論，也稱為遞歸理論，是數學邏輯，計算機科學和計算理論的一個分支，該理論源自1930年代，研究了可計算功能和圖靈程度。此後，該領域已擴展到包括廣義可計算性和確定性的研究。在這些領域，計算理論與證明理論和有效的描述性集理論重疊。
可計算理論解決的基本問題包括：
儘管在知識和方法方面存在相當大的重疊，但數學計算性理論家研究了相對可計算性，降低性概念和程度結構的理論。計算機科學領域的那些集中於亞賦形層次結構，形式方法和形式語言的理論。
介紹
| n | 2 | 3 | 4 | 5 | 6 | 7 | ... |
|---|---|---|---|---|---|---|---|
| σ（ n ） | 4 | 6 | 13 | 4098 ? | > 3.5 × 10 18 267 | > 10 10 10 10 18 705 353 | ? |
| 繁忙的海狸函數σ（ n ）的增長速度不超過任何可計算函數。 因此，這是不可計算的；只有少數值是已知的。 | |||||||
計算理論起源於1930年代，其作品是KurtGödel ， Alonzo Church ， RózsaPéter ， Alan Turing ， Stephen Kleene和Emil Post的作品。
研究人員獲得的基本結果確立了圖靈的可計算性，作為對有效計算的非正式觀念的正確形式化。 1952年，這些結果導致克萊恩（Kleene）將兩個名稱“教會的論文”和“圖靈論文”構成。如今，這些通常被認為是一個單一的假設，即教會論文，該論文指出，算法可計算的任何函數都是可計算的函數。儘管最初是懷疑的，但到1946年，戈德爾（Gödel）提出了這一論文的支持：
“塔斯基（Tarski）在他的演講中強調了（我認為是公正地）一般遞歸概念（或圖靈的可計算性）的重要性。在我看來，這種重要性很大程度上是由於這樣一個事實，即有了這樣的概念，一個人擁有第一個概念時間成功地給出了一個有趣的認識論觀念，即，一個不是根據所選擇的形式主義。”
通過對有效計算的定義，首先證明了數學中存在問題的問題。 1936年，教堂和圖靈受到戈德爾（Gödel）用來證明其不完整定理的技術的啟發 - 1931年，戈德爾（Gödel）獨立地證明了Entscheidungsproblem並非有效地決定。該結果表明，沒有算法過程可以正確決定任意數學命題是正確還是錯誤。
在建立這些初始示例之後，數學中的許多問題已被證明是不可決定的。 1947年，馬爾可夫和Post發表的獨立論文表明，無法有效地決定半群的問題。擴展了這一結果， Pyotr Novikov和William Boone在1950年代獨立地展示了組的單詞問題是無法有效解決的：沒有有效的程序，即在有限的群體中給定一個單詞，將決定是否由單詞來決定是組的身份元素。 1970年，尤里·馬蒂亞西維奇（Yuri Matiyasevich）證明了（使用朱莉婭·羅賓遜（ Julia Robinson ）的結果） Matiyasevich的定理，這意味著希爾伯特（Hilbert）的第十問題沒有有效的解決方案。這個問題詢問是否有一個有效的程序來決定整數上的雙方方程在整數中是否具有解決方案。不可確定的問題列表提供了沒有可計算解決方案的問題的其他示例。
可以有效執行數學結構的研究有時稱為遞歸數學。遞歸數學手冊涵蓋了該領域的許多已知結果。
圖靈的可計算性
在1936年，圖靈（ Turing如果n在集合中為n，則數字n ，停止輸出1，如果不在集合中，則停止輸出0。如果有一台在輸入n ，停止並返回輸出f （ n ）的圖靈機器，則從自然數到自然數的函數f是可計算或遞歸功能的（圖靈）或遞歸功能。在這裡使用圖靈機是不需要的；還有許多其他計算模型具有與圖靈機相同的計算能力。例如，從原始遞歸和μ算子獲得的μ回收函數。
可計算函數和集合的術語未完全標準化。根據μ回收函數以及哥德爾對rekursiv函數的不同定義，該定義導致了圖靈機可計算的集合和功能的傳統名稱遞歸。可定義的一詞源於德國單詞ientscheidungsproblem ，它在圖靈和其他文章的原始論文中使用。在當代用途中，“可計算函數”一詞具有各種定義：根據Nigel J. Cutland的說法，它是部分遞歸函數（對於某些輸入而言可能不確定），而根據RobertI 。等效地，一般遞歸）功能。本文遵循這些慣例的第二條。 1996年，Soare對術語發表了其他評論。
並非每組自然數都是可計算的。停止問題是在輸入0停止的圖靈機的一組（描述），這是一個不可歸結的集合的眾所周知的示例。許多不可誤的集合的存在源於以下事實：只有許多圖靈機器人可以計算在許多可計算的集合中，但是根據康托爾定理，有許多自然數量。
儘管停止問題是不可計算的，但可以模擬程序執行並產生停止程序的無限列表。因此，停止問題是一個可計算的（CE）集合的示例，該集合可以通過Turing Machine列舉（其他計算列出的術語），包括遞歸枚舉的枚舉和半決賽）。同等地，僅當它是某些可計算函數的範圍時，一組才是CE。 CE集雖然一般不是可決定的，但在計算理論中已詳細研究。
研究領域
從上述可計算集和功能的理論開始，計算性理論的領域已經發展到包括對許多密切相關主題的研究。這些不是獨立的研究領域：這些領域中的每個領域都從其他領域汲取了想法和結果，並且大多數可計算性理論家都熟悉其中的大多數。
相對計算性和圖靈度
傳統上，數學邏輯中的可計算性理論集中在相對可計算性上，這是圖靈在1939年提出的使用Oracle Turing Machines定義的Turing可計算性的概括。甲骨文圖靈機是一種假設的設備，除了執行常規圖靈機的動作外，能夠提出甲骨文的問題，這是一組特定的自然數。 Oracle機器只能提出“ oracle集合中的n ？”形式的問題。即使Oracle設置不可計算，每個問題也會立即正確回答。因此，具有不可算力的Oracle的Oracle計算機將能夠計算沒有Oracle無法使用的Turing機器。
非正式地，如果有正確的甲骨文機器正確地透露數字是否在A中，則一組自然數A可以還原為B集B。 （相對）可根據b計算，在b中遞歸）。如果一組A的圖林可還原為B集， B可以還原為A ，則據說這些集合具有相同的圖靈度（也稱為不可分辨性的程度）。一組的圖靈度可以精確地衡量該集合的不可兼容。
不可計算的集合的自然示例，包括編碼停止問題變體的許多不同集合，具有兩個共同的屬性：
- 它們是可以計算的，並且
- 每個都可以通過多個減少來翻譯成其他任何東西。也就是說，給定這樣的集合A和B ，有一個總可計算函數f ，使得a = { x ： f （ x ） ∈B }。據說這些集合是許多同等的（或同等）。
比圖靈的減少更強大：如果A集A可以減少為B集B ，則A可以還原為B ，但Converse並不總是保持。儘管不合格集的自然示例都是許多同等的，但可以構建可計算的枚舉集a和b的計算集，使得a可以還原為b ，但對b還原不是。可以證明，每個可計算的枚舉集都可以減少到停止問題，因此停止問題是相對於多個降低性和圖靈的降低性，最複雜的計算集合集。在1944年，Post詢問了每個計算的枚舉集是否都是可計算的還是相當於停止問題的圖片，也就是說，是否沒有計算的枚舉集，而這兩個之間的圖靈度中間有中間體。
作為中間結果，郵政定義的自然類型可計算的枚舉集，例如簡單，超氣和超級氣味套件。 POST顯示，這些集合嚴格在可計算集和停止問題之間相對於多一可降低。 POST還表明，其中一些是在其他可降低性概念中嚴格中間的，而不是簡化的可降低性。但是Post離開打開了存在一組中級圖靈度的存在的主要問題。這個問題被稱為Post的問題。十年後，Kleene和Post在1954年表明，可計算集的集合與停止問題之間存在中間的Turing度，但他們未能證明這些程度中的任何一個都包含一個可計算的枚舉集。此後不久，弗里德伯格（Friedberg）和曼尼克（Muchnik）通過建立可計算的列舉中級度的存在來獨立解決Post的問題。這種開創性的結果對可計算的列出集合的圖靈程度進行了廣泛的研究，事實證明，這些套件具有非常複雜且非平凡的結構。
無數的集合不可計算地枚舉，並且對所有集合的圖靈程度的研究在計算理論中與對可計算的圖靈度的研究一樣中心。構建了具有特殊特性的許多程度：無免疫度的度量，其中每個功能相對於該度的每個函數都通過（不偏變的）可計算函數進行了大量計算；高度相對於它可以計算的a函數f ，該函數f在每個可計算函數g中主導的函數，從某種意義上說，根據g ， c（x）<f（x）的所有x> c ;隨機程度包含算法隨機集； 1代1一代套件；以及低於限制集合的停止問題的程度。
任意（不一定是可計算的）圖靈度的研究涉及圖靈跳躍的研究。給定一個A ， Turing跳躍是一組自然數，編碼了使用Oracle A運行的Oracle Turing機器的停止問題的解決方案。任何集合的圖靈跳躍總是比原始集合更高的圖靈度，弗里德堡的定理表明，任何計算停止問題的集合都可以作為另一組的圖靈跳躍獲得。 Post的定理建立了Turing跳躍操作與算術層次結構之間的密切關係，該層次結構是根據自然數的某些子集的分類，該分類基於其算術性的確定性。
關於圖靈學位的許多最新研究集中在圖靈學位集的整體結構以及包含可計算的枚舉集的圖靈學位上。 Shore和Slaman的深度定理指出，將度X映射到其Turing跳躍程度的函數在圖靈度的部分順序上可以定義。 Ambos-Spies和Fejer的一項調查概述了這項研究及其歷史發展。
其他還原性
可降低降低性的計算性研究研究中持續的研究領域。 Post引入了幾種強大的降低性，因此命名是因為它們暗示了真理表的降低性。實施強大可降低的圖靈機將計算總體功能，而不管呈現哪種甲骨文。較弱的還原性是那些可能不會終止所有Oracles的過程；簡介可降低是一個例子。
強大的還原性包括：
- 一對一的降低性：如果存在總可計算的注射函數f ，則A是一對一可降低（或1-可還原），使每個n在a中，並且僅當f （ n ）在b中。
- 多一的可降低性：這本質上是一對一的降低性，而沒有限制的限制。如果存在總計可計算函數f ，則A多個可簡化（或M-可重還原）為B ，使每個n在a中，並且僅當f （ n ）在b中。
- 真實表的可降低性：如果A可以通過Oracle Turing機器降低為B的Turing，則A是可還原為B的，該機器不管給出了甲骨文，該機器都可以計算總功能。由於Cantor空間的緊湊性，這相當於說減少的問題同時向Oracle提出了一系列問題（僅取決於輸入），然後看到他們的答案能夠產生輸出而無需提出其他問題Oracle對初始查詢的答案。還研究了許多真實表降低的變體。
在文章降低（可計算理論）中討論了進一步的還原性（正，分離，結合性，線性及其弱和有限版本）。
關於強大降低性的主要研究是對其理論進行比較，無論是在所有可計算的集合的類別以及自然數的所有子集的類別的類別中。此外，還研究了還原性之間的關係。例如，眾所周知，每個圖靈程度都是真實的程度，或者是無限多個真理桌子的結合。
還已經研究了還研究可降低性的可還原性（即，通過降低的可降低性）也已經進行了研究。最著名的是算術降低性和過度降精性可降低性。這些還原性與算術標準模型的確定性緊密相關。
大米的定理和算術層次結構
稻米表明，對於每個非平凡的C類（包含一些但不是全部CE集）索引集E = { e ：e e th ce集合在c }中都有一個屬性，即停止問題或它的補充很多-一個可簡化E的，也就是說，可以使用多個降低來映射E （有關更多詳細信息，請參見Rice的定理）。但是，這些索引集中的許多比停止問題更為複雜。這些類型的集合可以使用算術層次結構進行分類。例如，所有有限集的類別的索引集列在級σ2上，所有遞歸集的類別的索引集REC在級σ3上，所有cofinite集的索引集合也在所有Turing-Complete集合σ4的等級σ3和索引集合。這些層次結構級別是歸納定義的，σN + 1僅包含所有相對於σN的所有集合； σ1包含可計算的枚舉集。此處給出的索引集甚至在其級別上都是完整的，也就是說，這些級別中的所有集合都可以降低到給定的索引集。
反向數學
反向數學的程序詢問哪些設置存在公理對於證明二階算術子系統中的數學定理是必要的。這項研究是由哈維·弗里德曼（Harvey Friedman）發起的，由斯蒂芬·辛普森（Stephen Simpson）和其他人詳細研究。 1999年，辛普森（Simpson）對該計劃進行了詳細討論。相關的設定公理非正式地對應於公理，說自然數的力量在各種可降低性概念下是關閉的。在反向數學中研究的最弱的公理是遞歸理解，它指出自然的力量在杜松子還原性下是封閉的。
編號
編號是函數的列舉；它具有兩個參數E和X ，並在輸入X上的編號中輸出e -th函數的值。儘管其一些成員是總計可計算功能，但數字可能是可以部分計算的。可接受的編號是所有其他人都可以翻譯成的編號。 Friedberg編號（以其發現者的名字命名）是所有可兼容函數的一對一編號；這一定不可接受的編號。後來的研究還涉及其他類別的數量，例如計算列出的集合。 Goncharov發現了一類計算的枚舉集，這些集合與可計算的同構相對於可計算的兩個類。
優先方法
郵政的問題通過一種稱為優先級方法的方法解決。使用此方法的證明稱為優先參數。此方法主要用於構建具有特定屬性的計算枚舉集。要使用此方法，要構造的集合的所需屬性被分解為無限的目標列表，稱為要求，因此滿足所有要求將導致構造的集合具有所需的屬性。每個要求都分配給代表要求優先級的自然數字；因此，0分配給了最重要的優先級，其中1分為第二重要，依此類推。然後，該集合分階段構造，每個階段都試圖通過在集合中添加數字，或者從集合中添加數字來滿足更多要求之一，以使最終集合滿足要求。滿足一個要求可能會導致另一個要求變得不滿意的情況可能會發生。優先順序用於決定在這種情況下該怎麼做。
已經採用了優先參數來解決計算理論中的許多問題，並根據其複雜性分類為層次結構。由於復雜的優先爭論可能是技術性的，而且很難遵循，因此傳統上認為沒有優先爭論證明結果，或者在沒有優先級論點的情況下查看結果是否證明結果也可以證明沒有它們。例如，庫默（Kummer）發表了一篇有關弗里德伯格（Friedberg）編號的證明的論文，而無需使用優先級方法。
計算枚舉集的晶格
當Post將簡單集的概念定義為具有無限含有任何無限CE集的無限補體的CE集時，他開始研究計算列出的概括集的結構。這個晶格成為了一個充分的結構。可以通過基本結果來定義可計算集的集合，即當且僅當集合及其補充都可以計算時，一個集合才能計算。無限CE集始終具有無限的可計算子集；但是，另一方面，存在簡單的集合，但並不總是具有可共同計算的超級集合。帖子引入了已經超氣和超級氣味套裝；後來構建了最大集合，這是CE集，使每個CE超集成是給定最大設置的有限變體，或者是共限定的。 Post在研究該晶格中的最初動機是找到一個結構概念，以至於每個滿足此屬性的集合都不是可計算集的Turing程度，也不是停止問題的圖靈程度。郵政沒有找到這樣的屬性，也沒有解決他的問題的解決方案。 1991年，哈靈頓和Soare最終發現了這樣的財產。
自態問題
另一個重要的問題是可計算性理論結構中的自動形態存在。這些結構之一是，在包含模量有限差的差異下列舉的集合之一。在此結構中， A僅當集合差B- A為有限時，A低於B。最大集合（如上一段中所定義）具有不能自動形態的屬性，即在剛剛提到的結構下計算的枚舉集的自動形態，則每個最大設置都會映射到每個最大設置另一個最大設置。 1974年，Soare表明，匡威保持，即每兩個最大集合都是自動形態的。因此，最大設置形成一個軌道，即，每種自動形態可保持最大性，任何兩個最大集合都通過某些自動形態互相轉換為彼此。哈靈頓為自動屬性提供了一個進一步的例子：創意套裝的屬性，這些集合與停止問題相當。
除了計算枚舉的集合的晶格外，還研究了所有集合的圖靈程度的結構以及CE集的Turing度的結構。在這兩種情況下，庫珀都聲稱已經建立了非平凡的自動形態，這些自動形態將一些程度映射到其他程度。但是，這種建築尚未得到驗證，一些同事認為該構建包含錯誤，並且關於圖靈學位是否存在非平凡的自動形態的問題仍然是該領域中未解決的主要問題之一。
Kolmogorov的複雜性
Kolmogorov的複雜性和算法隨機性是在1960年代和1970年代由Chaitin，Kolmogorov，Kolmogorov，Levin，Martin-Löf和Solomonoff開發的（此處以字母順序給出了名稱；許多研究是獨立的，並且是獨立的，並且是獨立的概念的統一性當時還不了解隨機性）。主要思想是考慮通用圖靈機U ，並測量數字（或字符串） X的複雜性作為最短輸入P的長度，以使u （ p ）輸出x 。這種方法徹底改變了早期的方法，以確定何時通過調用有限對象的隨機性概念來確定無限序列（等效地，自然數的特徵函數）是隨機的。 Kolmogorov的複雜性不僅成為一個獨立研究的主題，而且還適用於其他受試者，作為獲得證明的工具。該領域仍然有許多開放問題。約瑟夫·米勒（Joseph Miller）和安德烈·尼斯（AndréNies）保留了開放問題的清單。
頻率計算
該計算理論的這個分支分析了以下問題：對於固定的M和N ，用0 < m < n ，對於任何不同的n輸入x 1 ， x 2 ，... n數字y 1 ，y 2 ，.. .，y n ，使得方程a （ x k ）= y k的至少m為真。這樣的集合稱為（ M ， N ） - 捕集集。該計算性理論分支的第一個主要結果是Trakhtenbrot的結果是，如果某些m ， n為2 m > n ，則可以計算集合。另一方面，Jockusch的半循環套裝（在Jockusch介紹1968年之前已經非正式地知道）是一組的示例，即（ M ， N ） - 當且僅當2 m < n + 1時，有許多人無視。這些集合以及一些可計算的這種類型的但不可計算的集合。後來，DeGTEV建立了一個計算的枚舉集的層次結構，該集合為（1， n + 1） - 傳動性，但不是（1， n ） - 傳統。經過俄羅斯科學家的長時間研究，該主題通過貝格爾（Beigel）關於有限查詢的論文在西方重塑，該問題將頻率計算與上述有限的還原性和其他相關概念聯繫起來。主要結果之一是Kummer的基數理論，該理論指出，當且僅當存在N時， A組是可以計算的。 n與a相交的數字；這些選擇必須包含真正的基數，但至少遺漏了一個假的基數。
歸納推理
這是學習理論的可計算理論分支。它基於E. Mark Gold從1967年開始的限制學習模型，從那時起，它就越來越多地學習。一般方案如下：給定一個可計算函數的類S類，是否有學習者（即可計算功能），該函數為表單的任何輸入輸出（f（f（f（f（f（f（f（f （f）），f（ f （f（f（ f （1）），函數） （ n ））假設。如果幾乎所有假設都相對於先前商定的所有可接受的計算函數的可接受編號，則學習者M將學習一個功能F ； M可以學習M是否在s中學習每個f 。基本結果是，所有可計算的函數類都是可以學習的，而所有可計算功能的類REC都是不可學習的。已經考慮了許多相關模型，還從正面數據中學習了從正面數據列出的集合的類別，這是1967年Gold的開創性論文所研究的主題。
圖靈計算性的概括
可計算性理論包括研究該領域的廣義概念，例如算術降低性，過度降序性降低性和α-回歸理論，如Sacks在1990年所述。這些廣義概念包括Turing機器無法執行的降低概念，但絕對是自然概括的自然概括。還原性。這些研究包括研究分析層次結構的方法，該方法與算術層次結構不同，除了對單個數字進行定量之外，還允許對自然數集進行定量。這些領域與井井有條和樹木的理論相關。例如，對於沒有無限分支的所有可計算（非二進制）樹的索引的集合已完成
連續的可計算理論
數字計算的可計算理論開發得很好。在模擬計算機，模擬信號處理，模擬電子，神經網絡和連續時間控制理論中發生的模擬計算，可計算理論的發展較不那麼開發，該理論是由微分方程和連續的動態系統建模的。例如，諸如Blum -Shub -Smale機器模型之類的計算模型已對真實器進行形式化計算。
確定性，證明性和可計算性之間的關係
使用一階公式定義該設置的一組自然數的圖靈程度與難度（根據算術層次結構）之間存在密切的關係。 Post的定理確切地建立了一種這樣的關係。庫爾特·戈德爾（KurtGödel）在其完整定理和不完整定理的證據中證明了較弱的關係。戈德爾的證據表明，有效的一階理論的邏輯後果集是一個可計算的集合，如果該理論足夠強大，則該集合將是無法兼容的。同樣，可以根據確定性和可計算性來解釋Tarski的不可定力定理。
計算性理論還與二階算術相關，這是一種自然數和自然數的形式理論。某些集合是可計算或相對可計算的事實，通常意味著這些集可以在二階算術的弱子系統中定義。反向數學的程序使用這些子系統來測量眾所周知的數學定理中固有的非計算性。 1999年，辛普森討論了二階算術和反向數學的許多方面。
證明理論領域包括研究二階算術和佩尼奧算術的研究，以及比Peano算術弱的自然數的形式理論。對這些弱系統的強度進行分類的一種方法是表徵該系統可以被證明是總計的可計算函數。例如，在原始遞歸算術中，任何可證明總的可計算函數實際上都是原始的遞歸，而Peano算術證明，諸如Ackermann函數（不是原始遞歸）之類的函數是總的。但是，並非每個可計算函數在Peano算術中都均可; Goodstein定理提供了此類功能的一個示例。
姓名
自早期以來，數學邏輯及其概括性的數學邏輯領域被稱為“遞歸理論”。羅伯特一世（Robert I. Soare）是該領域的著名研究人員，他提出該領域應稱為“計算性理論”。他認為，使用“可計算”一詞的圖靈術語比使用克萊恩（Kleene）介紹的“遞歸”一詞更自然，更廣泛地理解。許多當代研究人員已經開始使用這種替代術語。這些研究人員還使用術語，例如部分可計算函數和計算的枚舉（ CE ）集，而不是部分遞歸功能，並遞歸枚舉（ RE ）集。但是，正如Fortnow和Simpson所解釋的那樣，並非所有研究人員都被說服了。一些評論員認為，名稱遞歸理論和計算性理論都無法傳達以下事實：在計算性理論中研究的大多數對像都是不可計算的。
1967年，羅傑斯（Rogers）提出，計算性理論的關鍵特性是，其結果和結構應在自然數的可計算射合下是不變的（該建議借鑒了幾何學中的Erlangen程序的思想）。這個想法是，可計算的二線只是在集合中重命名的數字，而不是指示集合中的任何結構，就像歐幾里得平面的旋轉不會改變其上繪製的線的任何幾何方面。由於任何兩個無限的可計算集都通過可計算的兩者進行鏈接，因此該建議識別所有無限的可計算集（有限的可計算集被視為微不足道）。根據羅傑斯的說法，計算理論的興趣集是不合格的集合，通過自然數的可計算射擊分為等效類。
專業組織
可計算性理論的主要專業組織是符號邏輯的關聯，該組織每年舉辦幾個研究會議。歐洲（ CIE ）的跨學科研究協會的可計算性還組織了一系列年度會議。