国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
計(jì)算的極限(一):所有機(jī)器的機(jī)器,與無法計(jì)算的問題

計(jì)算的極限(一):所有機(jī)器的機(jī)器,與無法計(jì)算的問題

本文作者:方弦

在圖靈誕辰100周年之際,獻(xiàn)給這位偉大的開拓者。

計(jì)算無處不在。

走進(jìn)一個(gè)機(jī)房,在服務(wù)器排成的一道道墻之間,聽著風(fēng)扇的鼓噪,似乎能嗅出0和1在CPU和內(nèi)存之間不間斷的流動(dòng)。從算籌算盤,到今天的計(jì)算機(jī),我們用作計(jì)算的工具終于開始量到質(zhì)的飛躍。計(jì)算機(jī)能做的事情越來越多,甚至超越了它們的制造者。上個(gè)世紀(jì)末,深藍(lán)憑借前所未有的搜索和判斷棋局的能力,成為第一臺(tái)戰(zhàn)勝人類國際象棋世界冠軍的計(jì)算機(jī),但它的勝利仍然仰仗于人類大師賦予的豐富國際象棋知識(shí);而僅僅十余年后,Watson卻已經(jīng)能憑借自己的算法,先“理解”問題,然后有的放矢地在海量的數(shù)據(jù)庫中尋找關(guān)聯(lián)的答案。長此以往,工具將必在更多的方面超越它的制造者。而這一切,都來源于越來越精巧的計(jì)算。

計(jì)算似乎無所不能,宛如新的上帝。但即使是這位“上帝”,也逃不脫邏輯設(shè)定的界限。

第一位發(fā)現(xiàn)這一點(diǎn)的,便是圖靈。

計(jì)算的極限(零):邏輯與圖靈機(jī)

所有機(jī)器的機(jī)器

圖靈機(jī)非常簡單,只要明白了它的運(yùn)作過程,任何一個(gè)受過足夠訓(xùn)練的計(jì)算機(jī)系本科生都可以寫出一個(gè)模擬圖靈機(jī)運(yùn)行的程序。只消輸入狀態(tài)轉(zhuǎn)移表和紙帶的輸入內(nèi)容,程序就可以一步一步模擬相應(yīng)的圖靈機(jī)在紙帶上爬來爬去的過程。對(duì)于一些熟悉圖形編程的程序員來說,做個(gè)模擬動(dòng)畫也問題不大。即使不用計(jì)算機(jī),靠人手一步步操作,也是一件小孩子也能完成的事。圖靈機(jī)就是這么簡單的一種機(jī)器。

雖然看上去簡單,但實(shí)際上圖靈機(jī)能做的事情遠(yuǎn)遠(yuǎn)超出一般的想象。只要有足夠長的紙帶和足夠好的耐心,今天的電腦能做的計(jì)算,一臺(tái)精心設(shè)計(jì)的圖靈機(jī)也能完成。訣竅在于,電腦中的電路是有限的,電路的狀態(tài)也是有限的,我們可以用圖靈機(jī)去模擬電腦中的電路狀態(tài)。只要有足夠長的紙帶,那就可以模擬出足夠大的寄存器、內(nèi)存和硬盤;而CPU中的電路,雖然所有可能的狀態(tài)極其多,但終究是有限的,可以用圖靈機(jī)模擬,雖然這臺(tái)圖靈機(jī)的狀態(tài)轉(zhuǎn)移表將會(huì)有著令人頭痛的大小,以及令人偏頭痛的復(fù)雜程度。但是,從原則上來說,用圖靈機(jī)模擬一臺(tái)電腦是完全可能的,雖然每次“讀寫內(nèi)存”時(shí),讀寫頭都需要花長得令人咋舌的時(shí)間在紙帶上來回奔波。

也就是說,從原則上來說,只要配備適當(dāng)?shù)妮斎牒洼敵鲈O(shè)備,以及極其好的耐心,我們完全可以用圖靈機(jī)上網(wǎng)、玩游戲甚至執(zhí)行自己寫的程序。特別地,存在一臺(tái)特定的編寫程序?qū)S玫膱D靈機(jī)T,我們可以在紙帶上寫程序,將它輸入到T,然后T就能執(zhí)行這個(gè)程序。那么,如果我們將方才本科生寫的那個(gè)可以模擬任意圖靈機(jī)運(yùn)行的程序(暫且把它稱為程序P),寫在紙帶上輸入到T中,讓T去執(zhí)行的話,原本的機(jī)器T就搖身一變,變成了一臺(tái)可以根據(jù)輸入的狀態(tài)轉(zhuǎn)移表來模擬任何一臺(tái)圖靈機(jī)的圖靈機(jī)。

【樂高玩具版圖靈機(jī),圖片出處:http://www.cs.cmu.edu/】

更精確地說,因?yàn)槌绦騊的長度是有限的,我們可以將它直接寫進(jìn)原來機(jī)器的狀態(tài)轉(zhuǎn)移表,得到一臺(tái)新的機(jī)器UTM。UTM會(huì)在紙帶上讀取兩樣?xùn)|西:一臺(tái)圖靈機(jī)M的狀態(tài)轉(zhuǎn)移表的二進(jìn)制編碼,以及作為M的初始輸入的紙帶數(shù)據(jù)。然后,UTM會(huì)根據(jù)M的狀態(tài)轉(zhuǎn)移表和初始輸入數(shù)據(jù),在紙帶上模擬M的運(yùn)作過程。換言之,UTM是一臺(tái)可以模擬任何圖靈機(jī)的圖靈機(jī)。它是所有機(jī)器的機(jī)器,所謂的通用圖靈機(jī)(Universal Turing Machine)。當(dāng)然,通用圖靈機(jī)并不是唯一的,只要一臺(tái)圖靈機(jī)能完成根據(jù)狀態(tài)轉(zhuǎn)移表模擬任意圖靈機(jī)的任務(wù),它就是通用圖靈機(jī)。

【一臺(tái)通用圖靈機(jī),數(shù)據(jù)具體格式請參見來源:http://rendell-attic.org/gol/utm/utmprog.htm】

通用圖靈機(jī)的想法,在如今這個(gè)計(jì)算機(jī)泛濫的時(shí)代,似乎并不新鮮。但在圖靈的1935年,電子計(jì)算機(jī)甚至仍未問世,機(jī)械計(jì)算機(jī)還只能執(zhí)行內(nèi)設(shè)的一套指令。即使是Charles Babbage和Ada Lovelace的超越時(shí)代的設(shè)想,其中執(zhí)行外部程序的概念也相當(dāng)含混不清。在這種歷史背景下,要?dú)w納出通用圖靈機(jī)這個(gè)概念,本身就需要極為豐富的想象力,而且這種圖靈機(jī)是否存在,這是個(gè)遠(yuǎn)非顯然的問題。而圖靈不僅設(shè)想到了這個(gè)概念,而且正確地判斷出它的存在性,這需要何等非凡的直覺!

但單純的直覺終究不能令人信服,數(shù)學(xué)家講究的是邏輯和證明。而要證明通用圖靈機(jī)的存在,最直接的方法莫過于直接給出一個(gè)通用圖靈機(jī)的實(shí)例。這并不簡單,如果讀者想嘗試一下的話,我建議先嘗試構(gòu)造一個(gè)能做二進(jìn)制加法的圖靈機(jī)。為了降低難度,可以假設(shè)紙帶上有第三種符號(hào),表示空白,但即使如此,要構(gòu)造一個(gè)能做加法的圖靈機(jī),遠(yuǎn)比想象中的困難??上攵?,通用圖靈機(jī)的構(gòu)造肯定更為復(fù)雜繁瑣。即使是圖靈,他在一開始給出的構(gòu)造也是有問題的,而這些問題甚至在后來的勘誤中也沒有成功修正。比構(gòu)造更麻煩的是證明給出的圖靈機(jī)的確是一臺(tái)通用圖靈機(jī),在圖靈解決希爾伯特可判定性問題的論文中,有關(guān)通用圖靈機(jī)的構(gòu)造和證明占了相當(dāng)大的篇幅。這部分非常繁復(fù)瑣碎,而且其中還有錯(cuò)誤,如果細(xì)細(xì)研讀的話,絕對(duì)有誘發(fā)劇烈偏頭痛的危險(xiǎn)。

幸運(yùn)的是,無論細(xì)節(jié)多么復(fù)雜,圖靈的想法還是被邏輯學(xué)家們接受了。一旦領(lǐng)會(huì)到圖靈機(jī)的能力,接受了通用圖靈機(jī)的構(gòu)想,再檢查幾個(gè)能完成基本任務(wù)的圖靈機(jī)之后,大部分?jǐn)?shù)學(xué)家都會(huì)認(rèn)為通用圖靈機(jī)的確存在,盡管他們并不一定會(huì)細(xì)看圖靈的詳細(xì)構(gòu)造。而現(xiàn)代電子計(jì)算機(jī)的發(fā)展,更是驗(yàn)證了通用圖靈機(jī)的存在:每一臺(tái)電腦都相當(dāng)于一臺(tái)通用圖靈機(jī)。

通用圖靈機(jī)的存在,從側(cè)面說明了圖靈機(jī)這個(gè)計(jì)算模型的強(qiáng)大之處:圖靈機(jī)作為一類機(jī)器,其中一個(gè)特例就可以模擬整個(gè)類別中的任意一臺(tái)機(jī)器,宛如能折射大千世界的一滴水珠。但在這種強(qiáng)大的背后,隱隱也暗藏著不安定的因素。哥德爾不完備性定理告訴我們,有時(shí)候越強(qiáng)大的數(shù)學(xué)理論,因?yàn)槟鼙磉_(dá)的概念太多,甚至連理論的命題和證明都能表達(dá),反而會(huì)導(dǎo)致不能被證明的真命題的存在。如果一個(gè)系統(tǒng)足以描述它自己,那魔法般的自指將是不可避免的。圖靈機(jī)如此強(qiáng)大,它的其中一臺(tái)就可以模擬所有圖靈機(jī),會(huì)不會(huì)導(dǎo)致不能用計(jì)算來回答的問題存在呢?

很不湊巧,答案是會(huì)。

無法計(jì)算的問題

在哥德爾不完備性定理的證明中,哥德爾構(gòu)造了一個(gè)描述了本身不可證明性的自指命題,通過這個(gè)命題完成了他的證明。要想照葫蘆畫瓢的話,那些關(guān)于圖靈機(jī)本身的問題,將會(huì)是很好的候補(bǔ)。

關(guān)于圖靈機(jī),最簡單的問題是什么呢?回想一下圖靈機(jī)的運(yùn)作過程,一臺(tái)圖靈機(jī)從初始狀態(tài)開始,根據(jù)紙帶上的內(nèi)容,一邊不斷變換狀態(tài),一邊更改紙帶的內(nèi)容,如此往復(fù)永無休止,除非它遇上了表示停機(jī)的那個(gè)狀態(tài),才能從這機(jī)械的計(jì)算過程中跳出,獲得靜息的安樂。一個(gè)自然的問題是:一臺(tái)圖靈機(jī)什么時(shí)候會(huì)停機(jī)呢?

更嚴(yán)格地說,會(huì)不會(huì)停機(jī)并不是圖靈機(jī)本身的屬性,它跟紙帶的初始輸入也有關(guān)系。對(duì)于同一臺(tái)圖靈機(jī),不同的紙帶輸入也可能導(dǎo)致不同的結(jié)果和行為。比如說,我可以設(shè)計(jì)一臺(tái)圖靈機(jī),它的任務(wù)只有一個(gè):一步一步向右移動(dòng),尋找輸入中的第一個(gè)1。如果輸入紙帶上全是0的話,那么,這臺(tái)圖靈機(jī)自然不會(huì)停止;但只要紙帶上有一個(gè)1,那么它就會(huì)停止。所以,真正嚴(yán)謹(jǐn)?shù)膯栴}是:給定一臺(tái)圖靈機(jī)M以及一個(gè)輸入I,如果我們將I輸入M,然后讓M開始運(yùn)行,這時(shí)M是會(huì)不停運(yùn)轉(zhuǎn)下去,還是會(huì)在一段時(shí)間后停止?我們將這個(gè)問題稱為停機(jī)問題。

初看起來,停機(jī)問題并不難。既然我們有通用圖靈機(jī)這一強(qiáng)大的武器,那么只需要用它一步步模擬M在輸入I上的計(jì)算過程就可以了。如果模擬過程在一段時(shí)間后停止了,我們當(dāng)然可以得出“M在輸入I上會(huì)停止”這個(gè)結(jié)論。問題是,在模擬過程停止之前,我們不可能知道整個(gè)計(jì)算過程到底是不會(huì)停止,它可能會(huì)在3分鐘后停止,可能要等上十年八載,更有可能永遠(yuǎn)都不會(huì)停止。換句話說,用模擬的方法,我們只能知道某個(gè)程序在某個(gè)輸入上會(huì)停止,但永遠(yuǎn)不能確定那些不停止的狀況。所以說,單純的模擬是不能解決停機(jī)問題的。

實(shí)際上,停機(jī)問題比我們想象中要復(fù)雜得多。

舉個(gè)例子,我們可以編寫一個(gè)程序GC,它遍歷所有大于等于6的偶數(shù),嘗試將這樣的偶數(shù)分成兩個(gè)素?cái)?shù)的和。如果它遇到一個(gè)不能被分解為兩個(gè)素?cái)?shù)之和的偶數(shù),它就停機(jī)并輸出這個(gè)偶數(shù);否則,它就一直運(yùn)行下去。用現(xiàn)代的工具編寫GC這樣的程序,對(duì)于計(jì)算機(jī)系的學(xué)生最多只能算一次大作業(yè);用圖靈機(jī)實(shí)現(xiàn)的話,也不是什么極端困難的事。然而,GC是否會(huì)停止可是牽涉到了哥德巴赫猜想。如果哥德巴赫猜想是正確的,每個(gè)大于等于6的偶數(shù)都能分解為兩個(gè)素?cái)?shù)之和的話,那么GC自然會(huì)一直運(yùn)行下去,不會(huì)停機(jī);如果哥德巴赫猜想是錯(cuò)誤的話,必定存在一個(gè)最小的反例,它不能分解為兩個(gè)素?cái)?shù)之和,而GC在遇到這個(gè)反例時(shí)就會(huì)停機(jī)。也就是說,GC是否永遠(yuǎn)運(yùn)行下去,等價(jià)于哥德巴赫猜想是否成立。如果我們能判定GC是否會(huì)停止,那我們就解決了哥德巴赫猜想。

數(shù)學(xué)中的很多猜想,比如說3x+1猜想、黎曼猜想等,都可以用類似的方法轉(zhuǎn)化為判斷一個(gè)程序是否會(huì)停止的問題。如果存在一個(gè)程序,能判斷所有可能的圖靈機(jī)在所有可能的輸入上是否會(huì)停止的話,那么只要利用這個(gè)程序,我們就能證明一大堆重要的數(shù)學(xué)猜想。我們可以說,停機(jī)問題比所有這些猜想更難更復(fù)雜,因?yàn)檫@些困難的數(shù)學(xué)猜想都不過是一般的停機(jī)問題的一個(gè)特例。如果停機(jī)問題可以被完全解決,我們能寫出一個(gè)程序來判斷任意圖靈機(jī)是否會(huì)停機(jī)的話,那么相當(dāng)多的數(shù)學(xué)家都要丟飯碗了。

停機(jī)問題如此復(fù)雜,機(jī)械的計(jì)算看起來沒有足夠的力量來完全解決它。停機(jī)問題似乎是不可計(jì)算的。但要想嚴(yán)格證明這個(gè)結(jié)論,似乎仍要求助于深藏在圖靈機(jī)之中,那魔法般的自指。

本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點(diǎn)擊舉報(bào)
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
超越數(shù)學(xué)的判定——通用圖靈機(jī)的誕生
人人都能懂的圖靈機(jī)原理
什么是算法?讀完這篇文章你就知道了
最不可思議的數(shù),決定了哥德巴赫猜想是否正確,遠(yuǎn)非人類可以理解
!!!!!釋放比特自由 Wolfram的“一種新科學(xué)”介紹
都聽過圖靈機(jī),它的靈感來自哪兒?
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服