「這些抽象機(jī)器也許是最好的證據(jù)，證明提出基本問題可能是科學(xué)家能夠做的最有用的事情之一?！?br />

計算是我們大多數(shù)人憑直覺就能理解的一個熟悉概念。我們以函數(shù) f (x) = x + 3 為例，當(dāng) x 為 3 時，f (3) = 3 + 3。答案是 6，非常簡單。很明顯，這個函數(shù)是可計算的。但是有些函數(shù)并非那么簡單，而且要確定它們是否可以計算也非易事，這意味著它們可能永遠(yuǎn)都無法得出一個最終答案。
1928 年，德國數(shù)學(xué)家大衛(wèi)?希爾伯特（David Hilbert）和威廉?阿克曼（ Wilhelm Ackermann）提出了一個名為 Entscheidungsproblem（即「判定性問題」）的問題。隨著時間推移，他們提出的這個問題將引出可計算性的正式定義，這個定義使數(shù)學(xué)家能夠回答大量新問題并為理論計算機(jī)科學(xué)奠定基礎(chǔ)。
一位 23 歲名叫艾倫圖靈的研究生提出了這個定義，他在 1936 年寫了一篇開創(chuàng)性論文，不僅將計算的概念形式化表達(dá)了出來，還證明了數(shù)學(xué)的一個基本問題，為發(fā)明電子計算機(jī)創(chuàng)造了知識基礎(chǔ)。圖靈的偉大遠(yuǎn)見在于以抽象機(jī)器的形式為計算問題提供了具體的答案，后來他的博導(dǎo)阿朗佐丘奇將其命名為圖靈機(jī)。
圖靈機(jī)是抽象的，因為它沒有（也不能）作為有形設(shè)備物理存在。相反，它是一個計算的概念模型：如果這個機(jī)器可以計算一個函數(shù)，那么這個函數(shù)就是可計算的。
當(dāng)艾倫圖靈在 1936 年發(fā)明圖靈機(jī)時，也創(chuàng)造了現(xiàn)代計算。
艾倫?圖靈及他的圖靈機(jī)
它的工作原理是這樣的：圖靈機(jī)可以按照規(guī)則表的規(guī)定讀取和更改無限長磁帶上的符號。磁帶是由一個個「單元格」組成，每個單元格只能存儲一個符號。圖靈機(jī)用磁帶頭讀取和重寫單元格的內(nèi)容。規(guī)則表中的每條規(guī)則都會決定圖靈機(jī)應(yīng)該根據(jù)它當(dāng)前的狀態(tài)和正在讀取的符號來做什么。圖靈機(jī)可以基于它停止的位置來進(jìn)入最終狀態(tài)（「接受狀態(tài)」或「拒絕狀態(tài)」），決定接受或拒絕輸入?；蛘邎D靈機(jī)陷入無限循環(huán)并永不停歇地讀取磁帶。
理解圖靈機(jī)的最好方法是來思考這樣一個簡單的例子。讓我們想象一下，圖靈機(jī)被設(shè)計用于告訴我們給定的輸入是否為數(shù)字零。我們將輸入帶有空白符號 (#) 的數(shù)字 0001，也就是說「#0001#」是我們磁帶的相關(guān)部分。
圖靈機(jī)從初始狀態(tài)開始，我們稱之為 q0，它讀取磁帶最左邊的單元格并找到一個空白區(qū)域。按照規(guī)則，當(dāng)處于狀態(tài) q0 時，如果符號是 #，則保持原樣不變，然后向右移動一個單元格，并將機(jī)器狀態(tài)更改為 q1。在這一步之后，機(jī)器處于狀態(tài) q1，它的磁頭將正在讀取第二個符號 0。
現(xiàn)在我們尋找適用于這些條件的規(guī)則。我們發(fā)現(xiàn)這樣一個規(guī)則，「保持狀態(tài) q1 并將磁頭向右移動一個單元格?！惯@使我們處于相同的位置（在狀態(tài) q1 中，讀數(shù)仍為 0），因此我們繼續(xù)向右移動，直到磁頭最終讀取到一個不同的數(shù)字 1。
當(dāng)我們再次查閱規(guī)則表時，我們發(fā)現(xiàn)了一條新規(guī)則：「如果遇到 1，則轉(zhuǎn)換到 q2，即拒絕狀態(tài)?！箞D靈機(jī)停止運行，并對最初的問題「0001 是零嗎？」回答「否」。
相反，如果輸入是「#0000#」，圖靈機(jī)將在所有這些零之后遇到 #。當(dāng)我們查閱規(guī)則表時，我們發(fā)現(xiàn)一條規(guī)則說這意味著機(jī)器進(jìn)入狀態(tài) q3，即一種「接受」?fàn)顟B(tài)?，F(xiàn)在機(jī)器對「‘0000’是零嗎？」這一問題的回答則為「是」。
艾倫圖靈幫助定義了計算、算法和圖靈機(jī)。
用抽象機(jī)器回答判斷性問題
圖靈使用他的抽象機(jī)器建立了一個計算模型，來回答 Entscheidungs 問題，它正式提出：給定一組數(shù)學(xué)公理，是否存在一個機(jī)械過程（即一組指令，今天我們稱之為算法）總是可以確定給定的陳述是否為真？
假設(shè)我們想找到一種算法來告訴我們某個棋局中棋子位置是否可行。在這其中，公理是管理國際象棋合理移動的規(guī)則。我們能否按照有限的 step-by-step 流程序列到達(dá)該位置？盡管某些棋局可能需要比我們一生更長的時間來分析，一種算法可能會生成所有可能的局面并將其逐個與輸入進(jìn)行比較，此類算法存在于國際象棋游戲之中。因此，我們說國際象棋是「可判定的」。
然而，在 1936 年，美國數(shù)學(xué)家丘奇和圖靈使用不同的方法分別證明了「沒有通用方法可以解決 Entscheidungs 問題的每個例子?！?例如，約翰康威的生命游戲等一些游戲是不可判定的：沒有算法可以確定某一模式是否會從初始模式出現(xiàn)。
圖靈表明了，如果存在可以執(zhí)行所需任務(wù)的算法，則函數(shù)是可計算的。同時，他還表明算法是一個可以用圖靈機(jī)定義的過程。因此，可計算函數(shù)是一種可通過圖靈機(jī)來計算的函數(shù)。這似乎是一種定義可計算性的迂回方式，但卻是我們所擁有的最好方式。
麻省理工學(xué)院理論計算機(jī)科學(xué)家邁克爾?西普瑟表示：「這并不是說你可以選擇用其他方式來定義它。我覺得人們普遍認(rèn)為，邱奇 - 圖靈論題提出的是，算法的非正式概念就是任何合理計算模型可以做到的事情?！蛊渌麛?shù)學(xué)家提出了不同的計算模型，雖然這些模型表面上看起來很不一樣，但實際上是相同的：它們可以進(jìn)行圖靈機(jī)可以進(jìn)行的任何計算，反之亦然。
就在哲學(xué)家、邏輯學(xué)家和數(shù)學(xué)家?guī)鞝柼?哥德爾證明數(shù)學(xué)是不完備的幾年后，丘奇和圖靈也通過這項工作表表明了數(shù)學(xué)中的某些問題是不可判定的。無論算法多么復(fù)雜，都無法告訴我們答案是肯定還是否定。這兩件事對希爾伯特來說都是毀滅性的打擊，他曾希望數(shù)學(xué)能給出簡潔、理想化的答案。但這倒也不錯：如果存在解決 Entscheidungsproblem 問題的一般解決方案，這將意味著數(shù)學(xué)中的所有問題都可以被簡化為簡單的機(jī)械計算。
通用和概率圖靈機(jī)
除了回答這些基本問題之外，圖靈機(jī)還通過一種稱為通用圖靈機(jī)的變體直接影響了現(xiàn)代計算機(jī)的發(fā)展。它是一種特殊的圖靈機(jī)，可以模擬任何其他圖靈機(jī)的任何輸入。它可以讀取其它圖靈機(jī)的描述（以及規(guī)則和輸入磁帶）并在自己的輸入磁帶上模擬它們的行為，與模擬機(jī)器輸出相同的輸出結(jié)果，就像今天的計算機(jī)可以讀取任何程序并執(zhí)行它一樣。
1945 年，美籍匈牙利數(shù)學(xué)家、計算機(jī)科學(xué)家、物理學(xué)家約翰?馮?諾依曼提出了一種計算機(jī)架構(gòu) —— 即馮?諾依曼架構(gòu)，它使得通用圖靈機(jī)概念變?yōu)楝F(xiàn)實生活中的機(jī)器成為可能。
當(dāng)普林斯頓大學(xué)理論計算機(jī)科學(xué)家 Sanjeev Arora 教授這個概念時，他強(qiáng)調(diào)了更廣泛的哲學(xué)描繪。他表示，「通用（universal）有兩種概念，一個是它可以運行任何其他圖靈機(jī)。，但另一個更大的概念是它可以運行你在宇宙中想出的任何計算?！乖诮?jīng)典物理學(xué)世界中，任何物理過程都可以使用算法進(jìn)行建?；蚰M，而算法又可以由圖靈機(jī)進(jìn)行模擬。
另一個值得關(guān)注且越來越有用的變體是概率圖靈機(jī)。與對每個輸入都有定義明確回應(yīng)的常規(guī)圖靈機(jī)不同，概率圖靈機(jī)可以根據(jù)概率做出多種回應(yīng)。這意味著它可以在不同的時間點對相同的輸入產(chǎn)出不同的結(jié)果。另外出人意料的是，對于某些問題，這種概率策略比純粹的確定性方法更有效。概率圖靈機(jī)的概念已被證明在密碼學(xué)、優(yōu)化和機(jī)器學(xué)習(xí)等領(lǐng)域非常有用。
這些抽象機(jī)器也許是最好的證據(jù)，證明提出基本問題可能是科學(xué)家能夠做的最有用的事情之一。
原文鏈接：https://www.quantamagazine.org/alan-turings-most-important-machine-was-never-built-20230503/