「從未被製造出來的最重要機器」，艾倫·圖靈及圖靈機那些事

計算是我們大多數人憑直覺就能理解的熟悉概念。我們以函數 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）有兩種概念，一個是它可以運行任何其他圖靈機。，但另一個更大的概念是它可以運行你在宇宙中想出的任何計算。」在經典物理學世界中，任何物理過程都可以使用演算法進行建模或模擬，而演算法又可以由圖靈機進行模擬。

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

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

以上是「從未被製造出來的最重要機器」，艾倫·圖靈及圖靈機那些事的詳細內容。更多資訊請關注PHP中文網其他相關文章！