我們都知道，圓周率是無限不循環小數（3.14159265359……）。通過測量多邊形的邊長，我們可以把圓周率近似到想要的精度。當多邊形的邊數趨于無窮，邊的長度趨于零時，近似值就會更接近。

• 用五邊形、六邊形和八邊形來近似圓周率的上界和下界。

阿基米德（約287- 212）發明了這種早期的“多邊形算法”，作為計算圓周率的最有效的方法，它統治了1000多年，可以達到任何期望的精度。這個非常原始的幾何算法函數用于估算實數π，由于π不能表示為有理數，因此必須取一個近似值。

現代對可計算性的研究始于1900年左右，當時希爾伯特提出了“希爾伯特計劃”，以公理化數學的基礎。在此之前，希爾伯特本人在1899年曾表示，幾何的一緻性變成實數的一緻性，而實數一緻性又變成戴德金的算術結果。因此，希爾伯特計劃是為了類似地利用數學證明的有限性來證明不會産生矛盾。如果這樣的基礎能夠建立起來，數學證明就完全可以用邏輯符号來表達。如果實現了，所有的證明，包括費馬大定理、黎曼假說和龐加萊猜想，都将是它們所表達的數學系統的必然結果。如果這是真的，我們就能造出一台足夠強大的機器，讓它運行足夠長的時間，最終所有的數學真理都會被揭示出來。

不到30年後，奧地利邏輯學家庫爾特哥德爾（1906-1978）發表了一篇著名的論文——《論數學原理及有關系統的形式不可判定命題》，其中他的“定理6”粉碎了希爾伯特公理化數學基礎的夢想。哥德爾的研究表明，這樣一個系統（無論多麼強大），從本質上來說總是不完整的。在這個系統中，總有一些表述是根據公理而無法證明的：

第一不完全性定理（哥德爾, 1931a）

任何可以進行一定數量初等運算的一緻形式系統F都是不完整的；也就是說，有些F語言的表述在F中既不能被證明也不能被證僞。

這篇論文有效地結束了希爾伯特計劃。當哥德爾上台展示他的成果時（那時僅25歲），約翰·馮·諾伊曼（1903-1957）恰巧作為希爾伯特項目的代表在觀衆席上。馮·諾伊曼被一些人認為是有史以來最聰明的人，他立即意識到希爾伯特計劃結束了。

馮·諾伊曼花了幾周的時間準備一個相關定理的證明，該證明基于哥德爾不完備性證明的算術運算，證明“形式系統”不僅不能證明其中的每一個陳述，而且也不能保證證明其自身的一緻性。後來他向哥德爾提交了證明，據說哥德爾禮貌地表示感謝，并告訴他，幾周前他自己（哥德爾）也寫過同樣的證明，而且已經提交發表了。這個定理是：

第二不完全性定理（哥德爾, 1931b）

沒有一個包含皮亞諾算術的一緻公理系統能證明其自身的一緻性。

更通俗地說，任何能夠形成自身一緻性的正式系統，隻有當且僅當它不一緻時才能證明這一點。該定理證明了第二個希爾伯特計劃的内在謬誤，該計劃于1918年啟動，名為判定問題，是否有可能提供一個判定程序，允許一個人決定一個句子的有效性。

因此，20世紀30年代的數學家們再次面臨數學缺陷的實際含義，19世紀80年代，康托爾首次證明了這一點。

我們的故事從這裡開始。

定義

阿基米德常數（π）、畢達哥拉斯常數（√2）和黃金比例（φ）等衆所周知的數都是可以計算的實數，盡管它們也是無理數。這些可計算數可以定義為：

可以通過有限終止算法計算到任何所需精度的實數。

換句話說，我們判斷一個實數為可計算的方法：如果有一種算法，給定n，返回該數字的前n位。非正式地說，我們可以把一個可計算的數想象成馬文·明斯基所做的那樣，即有一個圖靈機，在初始磁帶上給定n，以該數字（編碼在磁帶上）的第n位結束。

從形式上來說，實數a是可計算的，如果它可以用從自然數N到實數Z的某個可計算函數來近似，給定任意正整數N，該函數産生整數f(n)，從而：

• 給定的正整數n, f（n），可計算實數a的現代定義

可計算數的一個等價定義是存在這樣一個函數，給定任意正有理誤差界ε，得到一個有理數r，使其絕對值|r - a|小于或等于誤差界ε。

曆史

正如康托在19世紀研究對角線論證所産生的不可數集一樣，普林斯頓大學的研究人員在20世紀30年代研究不可計算數的含義。曆史特别突出了阿隆佐·邱奇（Alonzo Church）和艾倫·圖靈（Alan Turing）這兩個人的貢獻。

阿隆佐·邱奇

阿隆佐·邱奇是一位美國數學家和邏輯學家，20世紀20年代在普林斯頓大學的奧斯瓦爾德·維布倫手下獲得博士學位。他發表的第一篇論文是關于洛倫茲變換的。他最著名的成果包括證明希爾伯特的判定（決策）問題是不可判定的（被稱為邱奇定理），皮亞諾算術是不可判定的，他發明了λ演算，并闡明了後來被稱為邱奇-圖靈論題的關于可計算函數本質的論文。

艾倫·圖靈

艾倫·圖靈是一位英國數學家，他因協助軍方破解德國的著名密碼系統Enigma而聞名。對于數學家來說，圖靈的名字是天才的同義詞，不僅是因為他在應用理論方面的工作，還因為他在純數學和邏輯方面傑出的貢獻。

• 艾倫·圖靈和《論可計算數，及其在判定問題中的應用》，載于1936年《倫敦數學學會學報》

圖靈于1912年出生在倫敦，但在他17歲的時候就去了劍橋大學國王學院學習數學。1934年，他以優異的成績畢業，同年被選為國王學院的研究員（僅僅因為他的論文證明了中心極限定理）。1936年，他發表了他的著名論文《論可計算數，及其在判定問題中的應用》。它分兩部分發表在1936年11月30日和12月23日的《倫敦數學學會學報》上。同年9月，圖靈前往普林斯頓大學，在邱奇手下攻讀數學博士學位。他于1938年獲得博士學位。他的論文名為《基于序數的邏輯系統》，引入了序數邏輯和相對計算的概念——用所謂的甲骨文機器來擴充他之前設計的圖靈機，從而研究圖靈機無法解決的問題。盡管馮·諾伊曼博士想讓圖靈在獲得博士學位後擔任博士後研究助理，但圖靈拒絕了，回到了英國。

不可計算性

在1931年，将邏輯應用于可計算性是年輕人的遊戲。哥德爾（生于1906年），25歲時證明了形式系統的不完備性。邱奇在33歲時，基于λ演算，發明了“有效可計算性”的概念，證明了判定問題的不可判定性。圖靈，獨立地證明了同樣的結果，同年他發明了圖靈機，當時年僅24歲。

判定問題

“判定問題”的概念，即尋找一種算法，能夠根據有限的公理集确定輸入的真僞的問題，可以追溯到17世紀，當時萊布尼茨首次提出了這個概念。後來，對于各種形式系統，這個問題也分别由施羅德（1895年）、洛文海姆（1915年）和希爾伯特（1918年）提出，直到希爾伯特和阿克曼（1928年）在《數學邏輯原理》（Grundzuge der theorem Logik）上共同發表了正式聲明：

當我們知道一個過程允許任何給定的邏輯表達式通過有限次運算來決定其有效性時，判定問題就解決了。

邱奇的解決方案

1933年，圖靈的論文導師阿隆佐·邱奇開始研究這個問題。1934年3月左右，他向哥德爾提出了他的解決方案，其中包括他所謂的有效可計算函數。據推測，哥德爾否定了邱奇的方法。基于λ演算，邱奇的第一個命題是：

可計算性的第一個定義（1934）

一個函數是有效可計算的當且僅當它是λ可定義的。

自1931年起，邱奇就緻力于将函數定義為λ可定義函數。到1934年，他們已經證明了所有一般數論函數都是λ可定義的。然而，哥德爾在1931年的論文中所述的原始遞歸函數并沒有包括所有可計算的函數，因此對于斷言所有數的有效可計算性來說，這是一個不充分的。為了說明這一點，1934年春，哥德爾擴展了傑出的赫爾不蘭特（1908-1931）定理，定義了赫爾不蘭特-哥德爾遞歸函數。在參加了哥德爾舉辦的關于這個主題的講座後，邱奇和克林最終修改了他們對可計算性的定義，改為基于赫爾不蘭特-哥德爾的遞歸函數：

可計算性的第二個定義（邱奇, 1936）

當且僅當正整數上的函數是遞歸的時，它是有效可計算的。

邱奇和克林後來證明，他們在第一個定義中使用的λ可定義函數和他們在第二個定義中使用的赫爾不蘭特-哥德爾遞歸函數在形式上是等價的。

圖靈的解決方案

與此同時，艾倫·圖靈來到普林斯頓，試圖解決希爾伯特的判定問題，并在此過程中提供了可計算性的完整和最終定義。1936年11月30日，圖靈在《倫敦數學學會學報》上發表的論文将可計算性定義為：

圖靈的可計算性定義

一個函數是直觀可計算的（有效可計算），當且僅當它可以被圖靈機計算，也就是圖靈定義的自動機器。

圖靈在他的論文中指出了他的定義與邱奇七個月前發表的論文的相似之處，他說：“在最近的一篇論文中，邱奇引入了一個“有效可計算性”的概念，它等價于我的“可計算性”，但定義非常不同。他還補充說：“丘奇在判定問題上得出了類似的結論。”

與邱奇和克林不同，圖靈的定義并不依賴于赫爾不蘭特-哥德爾的遞歸函數。相反，圖靈研究了人類是如何進行計算分析的，最終表明，同樣的程序也可以由機器來執行。圖靈的分析不僅僅是提供了一個論證，它證明了一個定理。圖靈機的出現是他對人類計算分析的結果，是一種編碼。

圖靈機可以非正式地定義為：

圖靈機（A -machine）是一種計算的數學模型，它定義了一種抽象機器，它根據一個規則表來操作紙帶上的符号。盡管模型很簡單，但是給定任何計算機算法，都可以構造一個能夠模拟該算法邏輯的圖靈機。

不可計算數

雖然我們知道實數的集合是不可數的，但可計算數的集合是可數的，因此我們知道大多數實數是不可計算的。證明可計算數是可數的，直覺上源于這樣一個事實，即它們都可能是由圖靈機産生的。

可計算數的可數性的證明

通過分配哥德爾數給每個圖靈機定義産生一個與可計算數相對應的自然數子集。從S到可計算數的一個滿射表明，可計算數是可數的。

例A：蔡廷常數Ω

1975年，阿根廷裔美國數學家格裡高利·蔡廷将一個不可計算的實數按比例分解，現在稱為蔡廷常數Ω。它表示随機構造的程序終止的概率：

蔡廷的思想實驗：

假設我們在一個随機二進制程序上運行一個通用圖靈機。具體地說，每當需要程序的下一個比特時，我們抛硬币并将“二進制輸出”輸入到機器。圖靈機停止的概率是多少？

蔡廷的思想實驗是一個典型的終止問題的例子。終止問題是指從一個任意計算機程序的描述和一個輸入來确定程序是結束運行還是永遠繼續運行的問題。圖靈機U的終止概率 Ωᵤ 取如下表達式：

• 在輸入σ的條件下，圖靈機U的終止概率

其中σ代表随機有限二進制程序，U(σ)↓表示U将在輸入σ時停止。

圖靈1936年的論文證明了，對于所有可能的程序輸入對，解決中斷問題的一般算法是不存在的。中斷的概率是無法計算的。這一事實的證明依賴于一種算法，給定前n位Ω，它解決了長度為n的程序的圖靈中斷問題。因為中斷問題是不可判定的，所以Ω無法計算。

例子B：忙碌的海狸問題BB（n）

蒂博爾·拉多在1962年一篇名為《論不可計算函數》的論文中提出了以下問題：

給定一定數量的規則，在圖靈機停止運行之前，它能執行的最大步驟是多少？

這個問題有一個數學函數BB(n)，其中n代表規則數，BB(n)代表這種機器可以執行的最大步數（BB(1） = 1）。對于BB（4），問題就變得非常困難。證明BB（4）是一篇博士論文。BB（5）的值沒人知道，但至少為4098。BB(6)至少為3.5 x 10¹⁸²⁶⁷ 。如果運行 BB（27） 步還沒停機，就說明哥德巴赫猜想成立！

BB（n）函數是一個不可計算函數的例子。也就是說，沒有圖靈機Mᴮᴮ來計算BB函數。這可以用反證法證明，這裡就 不展開了。

例C：彭羅斯拼圖

彭羅斯拼圖是由一組非周期的原始“瓷磚”産生的非周期瓷磚的一個例子。因為這些圖案是非周期性的，它們缺乏平移對稱性。它們也是自相似的（分形），因為它們在越來越大的尺度上呈現相同的圖案。

• 彭羅斯拼圖

一套瓷磚是否會覆蓋平面的問題是1961年王皓提出的。這個問題後來被證明是不可計算的。這個證明依賴于使用圖靈機模拟圖靈機，配置圖靈機的方式是，隻有當圖靈機從一個空白磁帶開始永遠地運行時，它們才能覆蓋整個平面。既然停止問題是不可判定的，那麼平鋪問題也一定是不可判定的，因此也不可計算。

後記

今天，在數學和計算機科學中，圖靈機是定義可計算函數的主要形式。然而，為了承認邱奇首先掌握了這些函數的本質，關于可計算函數本質的假設的現代公式現在被稱為邱奇-圖靈命題：

邱奇-圖靈命題

一個函數是可計算的，當且僅當它是可計算的圖靈機，或等價地，如果它是指定的遞歸函數

它的含義是：

沒有一種機械過程的計算方法能比圖靈機更強大。

盡管這個命題被廣泛采用，但由于沒有明确的方法來證明或反駁它的有效性，它仍然是一個猜想。

想了解更多精彩内容，快來關注老胡說科學

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部