「從未被制造出的最重要機(jī)器」，艾倫·圖靈及圖靈機(jī)那些事

天承辦公室 2023-06-24 發(fā)布于北京

展開全文

選自量子雜志

機(jī)器之心編譯

編輯：王楷

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

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

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

一位 23 歲名叫艾倫圖靈的研究生提出了這個(gè)定義，他在 1936 年寫了一篇開創(chuàng)性論文，不僅將計(jì)算的概念形式化表達(dá)了出來(lái)，還證明了數(shù)學(xué)的一個(gè)基本問題，為發(fā)明電子計(jì)算機(jī)創(chuàng)造了知識(shí)基礎(chǔ)。圖靈的偉大遠(yuǎn)見在于以抽象機(jī)器的形式為計(jì)算問題提供了具體的答案，后來(lái)他的博導(dǎo)阿朗佐丘奇將其命名為圖靈機(jī)。

圖靈機(jī)是抽象的，因?yàn)樗鼪]有（也不能）作為有形設(shè)備物理存在。相反，它是一個(gè)計(jì)算的概念模型：如果這個(gè)機(jī)器可以計(jì)算一個(gè)函數(shù)，那么這個(gè)函數(shù)就是可計(jì)算的。

當(dāng)艾倫圖靈在 1936 年發(fā)明圖靈機(jī)時(shí)，也創(chuàng)造了現(xiàn)代計(jì)算。

艾倫?圖靈及他的圖靈機(jī)

它的工作原理是這樣的：圖靈機(jī)可以按照規(guī)則表的規(guī)定讀取和更改無(wú)限長(zhǎng)磁帶上的符號(hào)。磁帶是由一個(gè)個(gè)「單元格」組成，每個(gè)單元格只能存儲(chǔ)一個(gè)符號(hào)。圖靈機(jī)用磁帶頭讀取和重寫單元格的內(nèi)容。規(guī)則表中的每條規(guī)則都會(huì)決定圖靈機(jī)應(yīng)該根據(jù)它當(dāng)前的狀態(tài)和正在讀取的符號(hào)來(lái)做什么。圖靈機(jī)可以基于它停止的位置來(lái)進(jìn)入最終狀態(tài)（「接受狀態(tài)」或「拒絕狀態(tài)」），決定接受或拒絕輸入?；蛘邎D靈機(jī)陷入無(wú)限循環(huán)并永不停歇地讀取磁帶。

理解圖靈機(jī)的最好方法是來(lái)思考這樣一個(gè)簡(jiǎn)單的例子。讓我們想象一下，圖靈機(jī)被設(shè)計(jì)用于告訴我們給定的輸入是否為數(shù)字零。我們將輸入帶有空白符號(hào) (#) 的數(shù)字 0001，也就是說(shuō)「#0001#」是我們磁帶的相關(guān)部分。

圖靈機(jī)從初始狀態(tài)開始，我們稱之為 q0，它讀取磁帶最左邊的單元格并找到一個(gè)空白區(qū)域。按照規(guī)則，當(dāng)處于狀態(tài) q0 時(shí)，如果符號(hào)是 #，則保持原樣不變，然后向右移動(dòng)一個(gè)單元格，并將機(jī)器狀態(tài)更改為 q1。在這一步之后，機(jī)器處于狀態(tài) q1，它的磁頭將正在讀取第二個(gè)符號(hào) 0。

現(xiàn)在我們尋找適用于這些條件的規(guī)則。我們發(fā)現(xiàn)這樣一個(gè)規(guī)則，「保持狀態(tài) q1 并將磁頭向右移動(dòng)一個(gè)單元格。」這使我們處于相同的位置（在狀態(tài) q1 中，讀數(shù)仍為 0），因此我們繼續(xù)向右移動(dòng)，直到磁頭最終讀取到一個(gè)不同的數(shù)字 1。

當(dāng)我們?cè)俅尾殚喴?guī)則表時(shí)，我們發(fā)現(xiàn)了一條新規(guī)則：「如果遇到 1，則轉(zhuǎn)換到 q2，即拒絕狀態(tài)?！箞D靈機(jī)停止運(yùn)行，并對(duì)最初的問題「0001 是零嗎？」回答「否」。

相反，如果輸入是「#0000#」，圖靈機(jī)將在所有這些零之后遇到 #。當(dāng)我們查閱規(guī)則表時(shí)，我們發(fā)現(xiàn)一條規(guī)則說(shuō)這意味著機(jī)器進(jìn)入狀態(tài) q3，即一種「接受」?fàn)顟B(tài)。現(xiàn)在機(jī)器對(duì)「'0000’是零嗎？」這一問題的回答則為「是」。

艾倫圖靈幫助定義了計(jì)算、算法和圖靈機(jī)。

用抽象機(jī)器回答判斷性問題

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

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

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

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

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

就在哲學(xué)家、邏輯學(xué)家和數(shù)學(xué)家?guī)鞝柼?哥德爾證明數(shù)學(xué)是不完備的幾年后，丘奇和圖靈也通過這項(xiàng)工作表表明了數(shù)學(xué)中的某些問題是不可判定的。無(wú)論算法多么復(fù)雜，都無(wú)法告訴我們答案是肯定還是否定。這兩件事對(duì)希爾伯特來(lái)說(shuō)都是毀滅性的打擊，他曾希望數(shù)學(xué)能給出簡(jiǎn)潔、理想化的答案。但這倒也不錯(cuò)：如果存在解決 Entscheidungsproblem 問題的一般解決方案，這將意味著數(shù)學(xué)中的所有問題都可以被簡(jiǎn)化為簡(jiǎn)單的機(jī)械計(jì)算。

通用和概率圖靈機(jī)

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

1945 年，美籍匈牙利數(shù)學(xué)家、計(jì)算機(jī)科學(xué)家、物理學(xué)家約翰?馮?諾依曼提出了一種計(jì)算機(jī)架構(gòu) —— 即馮?諾依曼架構(gòu)，它使得通用圖靈機(jī)概念變?yōu)楝F(xiàn)實(shí)生活中的機(jī)器成為可能。

當(dāng)普林斯頓大學(xué)理論計(jì)算機(jī)科學(xué)家 Sanjeev Arora 教授這個(gè)概念時(shí)，他強(qiáng)調(diào)了更廣泛的哲學(xué)描繪。他表示，「通用（universal）有兩種概念，一個(gè)是它可以運(yùn)行任何其他圖靈機(jī)。，但另一個(gè)更大的概念是它可以運(yùn)行你在宇宙中想出的任何計(jì)算。」在經(jīng)典物理學(xué)世界中，任何物理過程都可以使用算法進(jìn)行建?；蚰M，而算法又可以由圖靈機(jī)進(jìn)行模擬。

另一個(gè)值得關(guān)注且越來(lái)越有用的變體是概率圖靈機(jī)。與對(duì)每個(gè)輸入都有定義明確回應(yīng)的常規(guī)圖靈機(jī)不同，概率圖靈機(jī)可以根據(jù)概率做出多種回應(yīng)。這意味著它可以在不同的時(shí)間點(diǎn)對(duì)相同的輸入產(chǎn)出不同的結(jié)果。另外出人意料的是，對(duì)于某些問題，這種概率策略比純粹的確定性方法更有效。概率圖靈機(jī)的概念已被證明在密碼學(xué)、優(yōu)化和機(jī)器學(xué)習(xí)等領(lǐng)域非常有用。

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

原文鏈接：https://www./alan-turings-most-important-machine-was-never-built-20230503/

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：天承辦公室 > 《022機(jī)器之心》

舉報(bào)/認(rèn)領(lǐng)