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