該論題最基本的觀點表明，所有計算或算法都可以由一台圖靈機來執行。
邱奇-圖靈論題(The Church-Turing thesis)是計算機科學中以數學家阿隆佐·邱奇(Alonzo Church)和阿蘭·圖靈命名的論題。該論題最基本的觀點表明，所有計算或算法都可以由一台圖靈機來執行。以任何常規程式語言編寫的電腦程式都可以翻譯成一台圖靈機，反之任何一台圖靈機也都可以翻譯成大部分程式語言大程式，所以該論題和以下說法等價：常規的程式語言可以足夠有效的來表達任何算法。該論題被普遍假定為真，也被稱為邱奇論題或邱奇猜想和圖靈論題。
基本介紹
- 中文名：邱奇-圖靈論
- 外文名：The Church-Turing thesis
- 命名者：阿隆佐·邱奇和阿蘭·圖靈
- 另名：邱奇論題或邱奇猜想和圖靈論題
論題形式,論題之起源,論題之成功,哲學內涵,補充材料,參考文獻,
論題形式
本論題的另外一種說法就是邏輯和數學中的有效或機械方法可由圖靈機來表示。通常我們假定這些方法必須滿足以下的要求：
一個方法由有限多個簡單和精確的指令組成，這些指令可由有限多的符號來描述。
該方法總會在有限的步驟內產生出一個結果。
基本上人可以僅用紙張和鉛筆來執行。
該方法的執行不需人類的智慧來理解和執行這些指令。
此類方法的一個範例便是用於確定兩個自然數的最大公約數的歐基里德算法。
“有效方法”這個想法在直覺上是清楚的，但卻沒有在形式上加以定義，因為什麼是“一個簡單而精確的指令”和什麼是“執行這些指令所需的智力”這兩個問題並沒有明確的答案。 (如需歐幾里得算法之外的範例，請參見數論中的有效結果。)
論題之起源
在他1936年年的論文“論可計算數字，及其在判定性問題(Entscheidungsproblem--德語，譯者注)中的套用”中，阿蘭·圖靈試圖通過引入圖靈機來形式地展示這一想法。在此篇論文中，他證明了“判定性問題”是無法解決的。幾個月之前，阿隆佐·邱奇在“關於判定性問題的解釋”(A Note on the Entscheidungsproblem)一文中證明出了一個相似的論題，但他採用但是遞歸函式和Lambda可定義函式來形式地描述有效可計算性。Lambda可定義函式由阿隆佐·邱奇和史蒂芬·克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)，而遞歸函式由庫爾特·歌德爾(Kurt G?del)和雅克斯·赫爾不蘭特(Jacques Herbrand) (G?del 1934, Herbrand 1932)提出的。這兩個機制描述的是同一集合的函式，正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整數函式那樣。在聽說了邱奇的建議後，圖靈很快就證明了他的圖靈機實際上描述的是同一集合的函式(Turing 1936, 263ff).y
論題之成功
之後用於描述有效計算的許多其他機制也被提了出來，比如暫存器機器(register machine), 埃米爾·波斯特(Emill Post)的波斯特體系, 組合可定義性(combinatory definability)以及馬可夫算法(Markov 1960)等。所有這些體系都已被證明在計算上和圖靈機擁有基本相同的能；類似的系統被稱為圖靈完全。因為所有這些不同的試圖描述算法的努力都導致了等價的結果，所以普遍認為邱奇.圖靈論題是正確的。但是，該論題不據有數學定理一般的地位，也無法被證明;如果能有一個方法能被普遍接受為一個有效的算法但卻無法在圖靈機上允許，則該論題也是可以被駁斥的。在20世紀初期，數學家們經常使用一種非正式的說法即可有效計算, 所以為這個概念尋找一個好的形式描述也是十分重要的。當代的數學家們則使用圖靈可計算 (或簡寫為可計算)這一定義良好的概念. 由於這個沒有定義的用語在使用中已經淡去，所以如何定義它的問題已經不是那么重要了。
哲學內涵
邱奇.圖靈論題對於心智哲學(philosophy of mind)有很多寓意。有很多重要而懸而未決的問題也涵蓋了邱奇.圖靈論題和物理學之間的關係，還有超計算性(hypercomputation)的可能性。套用到物理學上，該論題有很多可能的意義：
宇宙是一台圖靈機(由此，在物理上對非遞歸函式的計算是不可能的)。此被定義為大邱奇.圖靈論題.
宇宙不是一台圖靈機(也就是說，物理的定律不是圖靈可計算的)，但是不可計算的物理事件卻不能阻礙我們來創建 超計算機(hypercomputer)。比如，一個物理上實數作為可計算實數的宇宙就可以被劃為此類。
宇宙是一台超計算機, 因為建造物理設備來控制這一特徵並來計算非遞歸函式是可能的。比如，一個懸而未決的問題是量子力學的的事件是圖靈可計算的，儘管我們已經證明了任何由qubit所構成的系統都是(最佳)圖靈完全的。 約翰·盧卡斯 (和羅格·本羅澤(Roger Penrose) 曾經建議說人的心靈可能是量子超計算的結果。
實際上在這三類之外或其中還有許多其他的技術上的可能性，但這三類只是為了闡述這一概念。
補充材料
Hofstadter, Douglas R., G?del, Escher, Bach: an Eternal Golden Braid, Chapter 17.
參考文獻
Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
G?del, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
