圖靈機_顧醛大局_免费小说阅读网 

圖靈機(2 / 2)

“噗哈哈哈哈哈哈哈……解高中數學題的話說不定將來真的會有,但一般的數學命題……真可惜啊,不可能。”吃著糖的零醛好像恢複了一些活力,於是開始向我講解奇怪的東西。

“你知道希爾伯特問題嗎?”

“不太清楚……不過聽說過他的名言,‘我們必將知道,我們終將知道’。”

“啊對,他在1900年提出過‘世紀之交待解決的23個問題’,其中一個——所謂的‘entscheidungsroble’——”她念著這個冗長的德語單詞——“就是‘是不是對所有命題都有明確程序(defiterocedure)可以在有限時間內告訴我們命題是真是假’。要是真能這樣就好啦,什麼哥德巴赫猜想黎曼猜想……隻要把這些問題放進判定機器讓他運行一下就能知道了。更早的時候萊布尼茲也有過類似的幻想,他自己製造了加法器和乘法器,並且覺得人類將來能建造出所有判斷數學命題真假的機器。”

“好了好了我知道了……所以快點來打破我的幻想吧。”

“嗯……你要聽聽用圖靈機的證明嗎?”

“圖靈機……是電腦嗎?”

“隻能說電腦算是一種通用圖靈機啦。——圖靈機是圖靈構造的一種假想的機器,它有一個讀寫頭,”零醛從口袋裡掏出一支自動鉛筆,戳了戳筆尖示意,“一根紙帶,有很多格子,寫著零和一,讀寫頭在紙帶上自由移動。”她將鉛筆沿著手指前後移動,“機器還有一些內置的狀態,它會根據當前所處的狀態和讀到的方格裡的0或1來改變自己的狀態、左右移動,或在當前的格子裡寫下和擦除記號。”她“哢噠哢噠”地按了按筆尾。

“給一根輸入紙帶,有的圖靈機可以上麵運行有限步後進入停機狀態,有的則會一直運行下去——比如我可以造一台機器,在狀態1下讀到0或1都右移一格進入狀態2,在狀態2下讀到0或1都左移一格進入狀態1,進入“左移右移左移右移”的死循環……順便說一下,通過一些編碼,這些規則可以寫成01紙帶的形式,於是它們就既可以放在機器的腦袋裡,也可以拿出來作為機器的輸入。——這很重要!”她揮了揮自動鉛筆。

我點了點頭,表示能聽懂。

“所以我們現在有一台圖靈機——叫他小明吧。有一張輸入紙帶。我們就遇到了一個問題——能否在有限時間內通過明確的步驟判定小明在處理這條紙帶時會不會停機。

“先假設答案是‘能’——於是我們就會有一台特殊的圖靈機——叫它‘檢查員’吧,他隻要左手拿著小明的紙帶,右手拿著輸入紙帶——呃也可以把它們打印到一張紙帶上,算了幾張紙帶不重要——就能判定小明對這個輸入會不會停機。如果左右手都拿著小明的紙帶,就能判定小明對自身的輸入會不會停機。想象一下,比如說——這是一座機器人工廠,由於陷入死循環很麻煩,所以大家在運行紙帶之前都要去讓檢查員判定一下能不能停機……挺好的,嗯哼?

“隻是有一天,檢查員出了點狀況——無論是喝多了酒還是吃多了巧克力還是腦袋裡飛進了一隻蟲子——總之,當小明對輸入紙帶不能停機時,生病的檢查員照常在運行完這兩條紙帶後停下,給出‘不能停機’的結論;而當小明對輸入紙帶能夠停機時,生病的檢查員自己在處理這兩條紙帶時卻進入了死循環,其他機器不得不把他強行從紙帶上扯開。場麵一度失控。

“所以生病的檢查員想給自己作個檢查。他左右手都拿著自己的紙帶,想看看自己對自己的輸入會不會停機——然後就出現了矛盾。”

“如果判定能停機,就會進入死循環;如果判定不能停機,就會停下來……所以生病的檢查員最終會怎樣……”

“所以由反證法,檢查員這樣的機器不會存在。——或者,如果你一定要問他怎樣了的話——被自己的讀寫頭與紙帶摩擦所產生的熱量焚毀殆儘了吧。”

我歎出一口氣。

“希爾伯特還提出了其他的問題,比如數學是不是完備的——是不是所有數學命題都可以用一組有限的公理證明或證否;數學是不是一致的——是不是可以證明的都是真命題。”

“——這個命題是假命題!”

“哈,挺聰明的。之後哥德爾證明了如果算術係統一致那它就不完備——誒幾點了?”

我抬頭看了下學校門口電子屏上的大鐘,九點三十,我們已經在校門口的秋風中站了將近一刻鐘。

“……我們是圖靈機嗎?”我問了最後一個問題。

“誰知道呢,不過我覺得是的。”

“但我還沒聽說過誰的大腦因為接收了什麼奇怪的輸入而陷入不可預知的死循環……”

她不置可否地咧咧嘴。

到了要分彆的路口。她向左,我向右。該奔向車站了,彆誤了末班車。

轉身之前零醛停下了腳步,“哥德爾在天堂碰見了圖靈,他說:‘看吧,果然有人要毒死我們!’”她說道,然後發出幾聲上氣不接下氣的笑。

怎麼了?我回頭擔心地望著她,她搖搖頭,抬眼凝視著我,然後又恢複了平日的微笑:

“沒什麼,it’sajoke”

一點也不好笑。



最新小说: 怯弄香閨 閻羅之下 全族亂葬崗,重生罪妃不殺瘋不成活 神話擂台,開局召喚千古一帝 蘇槐楚思雨全本免費閱讀 我法師加奶媽,用七把劍不過份吧 卷王魔女從不認輸 天津人永不掉SAN 滿級傳球,請叫我三獅軍團話事人 我的諜戰日記