計算是我們大多數人憑直覺就能理解的一個熟悉概念。我們以函數 f (x) = x + 3 為例，當 x 為 3 時，f (3) = 3 + 3。答案是 6，非常簡單。很明顯，這個函數是可計算的。但是有些函數并非那么簡單，而且要確定它們是否可以計算也非易事，這意味著它們可能永遠都無法得出一個最終答案。

1928 年，德國數學家大衛?希爾伯特（David Hilbert）和威廉?阿克曼（ Wilhelm Ackermann）提出了一個名為 Entscheidungsproblem（即「判定性問題」）的問題。隨著時間推移，他們提出的這個問題將引出可計算性的正式定義，這個定義使數學家能夠回答大量新問題并為理論計算機科學奠定基礎。

一位 23 歲名叫艾倫圖靈的研究生提出了這個定義，他在 1936 年寫了一篇開創性論文，不僅將計算的概念形式化表達了出來，還證明了數學的一個基本問題，為發明電子計算機創造了知識基礎。圖靈的偉大遠見在于以抽象機器的形式為計算問題提供了具體的答案，后來他的博導阿朗佐丘奇將其命名為圖靈機。

圖靈機是抽象的，因為它沒有（也不能）作為有形設備物理存在。相反，它是一個計算的概念模型：如果這個機器可以計算一個函數，那么這個函數就是可計算的。

當艾倫圖靈在 1936 年發明圖靈機時，也創造了現代計算。

艾倫?圖靈及他的圖靈機

它的工作原理是這樣的：圖靈機可以按照規則表的規定讀取和更改無限長磁帶上的符號。磁帶是由一個個「單元格」組成，每個單元格只能存儲一個符號。圖靈機用磁帶頭讀取和重寫單元格的內容。規則表中的每條規則都會決定圖靈機應該根據它當前的狀態和正在讀取的符號來做什么。圖靈機可以基于它停止的位置來進入最終狀態（「接受狀態」或「拒絕狀態」），決定接受或拒絕輸入。或者圖靈機陷入無限循環并永不停歇地讀取磁帶。

理解圖靈機的最好方法是來思考這樣一個簡單的例子。讓我們想象一下，圖靈機被設計用于告訴我們給定的輸入是否為數字零。我們將輸入帶有空白符號 (#) 的數字 0001，也就是說「#0001#」是我們磁帶的相關部分。

圖靈機從初始狀態開始，我們稱之為 q0，它讀取磁帶最左邊的單元格并找到一個空白區域。按照規則，當處于狀態 q0 時，如果符號是 #，則保持原樣不變，然后向右移動一個單元格，并將機器狀態更改為 q1。在這一步之后，機器處于狀態 q1，它的磁頭將正在讀取第二個符號 0。

現在我們尋找適用于這些條件的規則。我們發現這樣一個規則，「保持狀態 q1 并將磁頭向右移動一個單元格。」這使我們處于相同的位置（在狀態 q1 中，讀數仍為 0），因此我們繼續向右移動，直到磁頭最終讀取到一個不同的數字 1。

當我們再次查閱規則表時，我們發現了一條新規則：「如果遇到 1，則轉換到 q2，即拒絕狀態。」圖靈機停止運行，并對最初的問題「0001 是零嗎？」回答「否」。

相反，如果輸入是「#0000#」，圖靈機將在所有這些零之后遇到 #。當我們查閱規則表時，我們發現一條規則說這意味著機器進入狀態 q3，即一種「接受」狀態。現在機器對「‘0000’是零嗎？」這一問題的回答則為「是」。

艾倫圖靈幫助定義了計算、算法和圖靈機。

用抽象機器回答判斷性問題

圖靈使用他的抽象機器建立了一個計算模型，來回答 Entscheidungs 問題，它正式提出：給定一組數學公理，是否存在一個機械過程（即一組指令，今天我們稱之為算法）總是可以確定給定的陳述是否為真？

假設我們想找到一種算法來告訴我們某個棋局中棋子位置是否可行。在這其中，公理是管理國際象棋合理移動的規則。我們能否按照有限的 step-by-step 流程序列到達該位置？盡管某些棋局可能需要比我們一生更長的時間來分析，一種算法可能會生成所有可能的局面并將其逐個與輸入進行比較，此類算法存在于國際象棋游戲之中。因此，我們說國際象棋是「可判定的」。

然而，在 1936 年，美國數學家丘奇和圖靈使用不同的方法分別證明了「沒有通用方法可以解決 Entscheidungs 問題的每個例子。」 例如，約翰康威的生命游戲等一些游戲是不可判定的：沒有算法可以確定某一模式是否會從初始模式出現。

圖靈表明了，如果存在可以執行所需任務的算法，則函數是可計算的。同時，他還表明算法是一個可以用圖靈機定義的過程。因此，可計算函數是一種可通過圖靈機來計算的函數。這似乎是一種定義可計算性的迂回方式，但卻是我們所擁有的最好方式。

麻省理工學院理論計算機科學家邁克爾?西普瑟表示：「這并不是說你可以選擇用其他方式來定義它。我覺得人們普遍認為，邱奇 - 圖靈論題提出的是，算法的非正式概念就是任何合理計算模型可以做到的事情。」其他數學家提出了不同的計算模型，雖然這些模型表面上看起來很不一樣，但實際上是相同的：它們可以進行圖靈機可以進行的任何計算，反之亦然。

就在哲學家、邏輯學家和數學家庫爾特?哥德爾證明數學是不完備的幾年后，丘奇和圖靈也通過這項工作表表明了數學中的某些問題是不可判定的。無論算法多么復雜，都無法告訴我們答案是肯定還是否定。這兩件事對希爾伯特來說都是毀滅性的打擊，他曾希望數學能給出簡潔、理想化的答案。但這倒也不錯：如果存在解決 Entscheidungsproblem 問題的一般解決方案，這將意味著數學中的所有問題都可以被簡化為簡單的機械計算。

通用和概率圖靈機

除了回答這些基本問題之外，圖靈機還通過一種稱為通用圖靈機的變體直接影響了現代計算機的發展。它是一種特殊的圖靈機，可以模擬任何其他圖靈機的任何輸入。它可以讀取其它圖靈機的描述（以及規則和輸入磁帶）并在自己的輸入磁帶上模擬它們的行為，與模擬機器輸出相同的輸出結果，就像今天的計算機可以讀取任何程序并執行它一樣。

1945 年，美籍匈牙利數學家、計算機科學家、物理學家約翰?馮?諾依曼提出了一種計算機架構 —— 即馮?諾依曼架構，它使得通用圖靈機概念變為現實生活中的機器成為可能。

當普林斯頓大學理論計算機科學家 Sanjeev Arora 教授這個概念時，他強調了更廣泛的哲學描繪。他表示，「通用（universal）有兩種概念，一個是它可以運行任何其他圖靈機。，但另一個更大的概念是它可以運行你在宇宙中想出的任何計算。」在經典物理學世界中，任何物理過程都可以使用算法進行建模或模擬，而算法又可以由圖靈機進行模擬。

另一個值得關注且越來越有用的變體是概率圖靈機。與對每個輸入都有定義明確回應的常規圖靈機不同，概率圖靈機可以根據概率做出多種回應。這意味著它可以在不同的時間點對相同的輸入產出不同的結果。另外出人意料的是，對于某些問題，這種概率策略比純粹的確定性方法更有效。概率圖靈機的概念已被證明在優化和機器學習等領域非常有用。

這些抽象機器也許是最好的證據，證明提出基本問題可能是科學家能夠做的最有用的事情之一。