第419章 封閉類時，超計算

    黑洞分寒只是讓傳幾份超計算模型、圖靈-丘奇論題相關的論文而已，怎麼又惹得福地分寒那般失態，大腿都拍腫了？

    先說說什麼叫超計算模型。

    計算機理論的基礎是可計算性理論，而可計算性理論的基石是“圖靈機”與“丘奇-圖靈論題”。

    後者是以數學家阿隆佐·丘奇和阿蘭·圖靈命名，就彷彿熱力學第二定律一樣，有多種形式大相徑庭的表述方式。

    比如:所有計算或算法都可以由一臺圖靈機來執行。

    或者:以任何常規編程語言編寫的計算機程序都可以翻譯成一臺圖靈機，反之任何一臺圖靈機也都可以翻譯成大部分編程語言的程序。

    又或者:邏輯和數學中的有效或機械方法可由圖靈機來表示。

    大家雲山霧罩，不明所以了吧？

    其實主要是概念不熟。

    像質能方程，一切物質都潛藏著質量乘於光速平方的能量。大家立刻能理解，是因為對物質、質量、光速、能量的概念耳熟能詳。

    而丘奇-圖靈論題涉及的概念大家一般不那麼熟悉，於是字都認識，連起來就莫名奇妙了。

    事實上，如何界定有效方法、執行算法、有限步驟，這些也正是該論題重點討論的對象。

    比如第一章中曾經出現的蔡廷常數，為什麼叫不可計算數？

    就是因為若以數字為對象的集合，可計算數便是指圖靈機通過有限的通用算法可以得到的數字，基本就是所有實數。有理數靠加減乘除，無理數靠乘方開方，超越數可以用級數……

    想知道√2或者π的第一億位是多少，寫一段程序運行就是了。

    但不可計算數，雖然理論上是一個常數，但理論上也證明了，永遠也無法求出它來。

    因為求它的過程，會影響結果。

    就好像蝴蝶效應，你不想要現在的結局，回到從前試圖改變，但結局又會變成什麼樣子，迴歸迭代之前是不知道的。

    甚至在此之後還有更加詭異的，語言都無法定義的數字，叫做不可定義數。雖然目前還沒有數學家成功構造出來……

    總之，1936年的一篇論文中，阿蘭·圖靈引入了圖靈機，來證明“判定性問題”是無法解決的；

    而阿隆佐·邱奇利用遞歸函數和lambda可定義函數，做出了類似的論題，用來描述有效可計算性；

    還是1936年，圖靈根據邱奇的工作，進一步證明了圖靈機實際上描述的是同一集合的函數；

    再之後，更多用於描述有效計算的機制被提出來，比如寄存器機器、波斯特體系、組合可定義性以及馬可夫算法等等。

    這些都被證明在計算上和圖靈機擁有相同的能力，能與通用圖靈機互相模擬，就被稱為圖靈完全。

    《我的世界》就被證明是圖靈完全的，樂高積木據說也是，還有萬智牌……

    扯遠了，這一切有什麼意義呢？

    意義就是，數學家和計算學家們漸漸弄清楚了，雖然形式、語言、系統各有不同，現代計算機本質上都和圖靈機等價——現代計算機能完成的任務，圖靈機也一定能完成；圖靈機做不到的事情，現在計算機也做不到。

    這就叫可計算性。