我們都知道，圓周率是無限不迴圈小數（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年王皓提出的。這個問題後來被證明是不可計算的。這個證明依賴於使用圖靈機模擬圖靈機，配置圖靈機的方式是，只有當圖靈機從一個空白磁帶開始永遠地執行時，它們才能覆蓋整個平面。既然停止問題是不可判定的，那麼平鋪問題也一定是不可判定的，因此也不可計算。

後記

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

邱奇-圖靈命題

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

它的含義是：

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

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