0

8
2

文字

分享

0
8
2

搞懂「通用圖靈機」的終站——它的誕生與意義 │《電腦簡史》數位時代(十三)

張瑞棋_96
・2020/12/21 ・4490字 ・閱讀時間約 9 分鐘 ・SR值 560 ・八年級

本文為系列文章,上一篇請見:搞懂「通用圖靈機」的第一站——康托爾的「無限樂園」 │《電腦簡史》數位時代(十二)

數學體系的的聖杯是否存在?——圖靈機的源頭

上一篇提到的無限這個原本大家都敬而遠之的怪物,還是被康托爾用集合論馴服了,集合論儼然成為建構數學體系的利器。然而過沒多久,英國哲學家與數學家羅素 (Bertrand Russell) 卻在 1901 年提出一個後來以他為名的「羅素悖論」(註一),指出集合論的矛盾之處,史稱「第三次數學危機」。

儘管幾位數學家著手修補,參考歐氏幾何有五大公設,也為集合論制定一些公設,將「樸素集合論」改造為沒有矛盾的「公設化集合論」,安然度過危機。但是數學體系接二連三出現裂縫,表示其中必有缺陷。大數學家希爾伯特 (David Hilbert) 因此呼籲重新審視所謂不證自明的公設或定理,從根基開始,重新打造完美無瑕的數學體系。

大數學家希爾伯特 (David Hilbert) 攝於 1912 年。圖:Wikipedia

1928 年,希爾伯特在國際數學家大會上拋出三大提問:

一、數學是否完備?所謂完備是指每則陳述(例如畢氏定理)都可以被證明為真或為假。

二、數學是否一致?也就是同一則陳述不會有既被證明為真、又被證明為假的矛盾情況。

三、數學是否可以判定?意思是任何陳述都有一套明確的程序可以用來判定其真假。(例如希爾伯特列舉的 23 個懸而未決的數學問題,是否終究會找出證明的方法?)

基於數學以往幾次克服危機的歷史經驗,希爾伯特相信這三個提問的答案都是肯定的;1930 年他發表退休演說時,就以「我們必須知道,我們將會知道!」做為結語。這並不是希爾伯特一廂情願,事實上學界也都普遍相信完備且一致的數學體系指日可待。

哥德爾不完備定理敲碎美夢

不料第二年,大家的美夢就被一篇論文狠狠敲碎。才25歲的奧地利數學家哥德爾 (Kurt Gödel) 提出「哥德爾不完備定理」,證明任何一個基於算術公設的系統如果有一致性,就不是完備的,也就是其中一定有無法證明真偽的陳述(註二)。而且「哥德爾第二不完備定理」還指出:這個系統的一致性根本無法在系統內部獲得證明。

哥德爾 (Kurt Gödel) 攝於 1925 年。圖:Wikipedia

哥德爾正式宣判完備且一致的數學體系並不存在,追求聖杯只是徒勞,大家可以散矣。整個學界感到震驚與失落,正如馮紐曼的喟嘆:「一切都結束了!」。

如今希爾伯特的前兩個問題顯然答案都是否定的,而既然存在無法證明真偽的陳述,那麼第三個問題當然也就沒意義了。但能否退而求其次,把第三個問題改為:可否透過一套明確的程序判定某個陳述能不能被證明真假?也就是說,我們至少可以把這種無法證明真假的異類挑出來吧?

正是這個判定問題,讓圖靈跨入計算機的領域。

延續摯愛未竟之業——圖靈奮發向前的動力

圖靈於 1912 年在倫敦出生,到了中學就長得高大壯碩,還是長跑健將。不過他卻不是陽光男孩,相反地,他個性內向,在學校沒有多少朋友,其中最知心的是大他一個年級的莫康 (Christopher Morcom)。莫康因為感染肺結核,身體嬴弱削瘦,但他課業名列前茅,與圖靈一樣對數學、科學有極高的興趣,兩人常一起討論而成為莫逆之交。

圖靈攝於 16 歲。圖:Wikipedia

圖靈對莫康愛慕不已,也因此才察覺自己的同性戀傾向。無奈莫康在畢業前一年不敵病魔而過世,用情至深的圖靈深受打擊,卻也因此更加專注於學業。他在寫給莫康母親的信上說:

「……我知道自己必須在學業上投注相同的心力,彷彿他仍然在世,因為他會希望我這麼做。」

圖靈如此努力的背後還有個重要動力。莫康原本已經獲得劍橋大學的獎學金,圖靈想替他實現未能完成的人生,以進入劍橋大學為目標,而最後圖靈也如願於 1931 年入學就讀。

1935年春季,圖靈在數學教授紐曼 (Max Newman) 的課堂上,聽到教授介紹希爾伯特的三大問題。紐曼提及修正後的「判定性問題」時,不知有心或無意,用的詞是「機械式程序」(mechanical process),而不是「明確的程序」。

機械式程序聽起來就是多了一層含意,暗示著一種不需人為介入的自動程序。而這層含意在圖靈心中埋下了種子,然後在初夏某一天的下午,圖靈慢跑完,躺在草地上休息時,想到了如何透過自動機器解決判定性問題。

圖靈機構造與運作原理

圖靈無意打造一台真正的機器,因為他要處理的是抽象的原則性問題,重點在於思辨過程,而不是加減乘除。因此圖靈只須設想這台自動機器如何運作,無需考慮它如何製造。事實上這台後來以他為名的「圖靈機」極為簡化,硬體組成只有一個可以左右移動的讀寫頭,以及一條無限長的紙帶。與其說它是計算機,反倒比較像是台打字機。

這條紙帶上面劃分成一個一個方格,每個方格只能打印一個符號。讀寫頭能掃描辨識符號、打印符號,或抹拭符號;它還能左右移動,但每次最多只能移動一格。讀寫頭的動作取決於它正下方那個方格內的符號,以及機器目前的狀態。這兩個參數也會決定讀寫頭每次做完動作後,機器狀態是否要改變。

這些影響讀寫頭與機器狀態的規則可以整理成一張「行為表」,例如下面這張:

按照這張行為表,像下面圖中的紙條,原本3 個 “1” 和 2 個 “1” 彼此隔開,經過圖靈機後,就會變成 5 個 “1” 連在一起。我們可以當作這是 3+2=5 的計算,那麼配備這張行為表的圖靈機就是一台簡易加法器,可以任意加總兩個數目。

圖靈機構造再簡單不過,但只要在行為表中制定適當的規則,再複雜的計算,它都可以勝任。圖靈把可以透過有限的規則,讓圖靈機進行計算並以小數的形式印出來的數,定義為「可計算數」

可計算數不一定是有限小數,像 1/3 = 0.3333……也算,反正紙帶無限長,或者你也可以決定小數點後幾位就停下來。因此像 √2、π 這種無理數也都是可計算數,因為它們可以用具有規律的無限級數表示(例如萊布尼茲所發現的 π/4 = 1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + ……),就能透過有限的規則,讓圖靈機計算。

描述數與通用圖靈機

不過圖靈機只能從紙帶上讀取資料,所以行為表得用一行符號來表達,才能印在紙帶上讓圖靈機掃描。例如上面那張行為表可能就會變成一行指令:

10RNN;11RN2;20R13;21RNN;30LN4;31RNN;40NNN;41N0N

接著我們把指令中的英文字母與符號用數字代替,例如 A ~ Z 改為 11 ~ 33,分號”;” = 99,數字也跟著改用兩位數 00 ~ 09表示。如此一來,指令就會化為一串數字,圖靈稱之為「描述數」,意指這行純數字的數列就能描述圖靈機的行為。

正常的描述數可以讓圖靈機經過有限步驟後停下來,產生可計算數。但某些描述數卻可能讓圖靈機中途動彈不得,或是不斷來回繞圈圈,無法產生有意義的答案。例如「讀到 1 就往右;讀到 0 則往左」這個指令,就會讓圖靈機遇到 “1”、”0”相鄰時左右來回,永不停止(這其實就相當於「說謊者悖論」)。

如果一台圖靈機只有一個描述數,我們當然可以輕易地發現某台圖靈機停不下來,從而知道這個描述數有問題。不過實際上不需要建造那麼多台圖靈機。想像有台特別的「通用圖靈機」(圖靈稱之為 ”Universal machine“),可以把其它圖靈機的描述數都掃描進來,那麼它便能模擬任何一台圖靈機的運作。而且描述數除了代表運作規則,也可以當成數字做為編號,按大小順序排列,方便圖靈機搜尋。

停機問題

現在問題來了,我們怎麼知道掃描進來的那麼多描述數之中,是否摻雜著造成圖靈機空轉的描述數?有沒有一套機械程序可以直接判定某個描述數能否讓圖靈機正常停機(而不用讓圖靈機實際執行,再看結果如何)?這就是所謂的「停機問題」。它的性質等同於希爾伯特的判定性問題:有沒有一套明確的程序可以判定某個陳述能不能被證明真假?

我們先假設真的有這麼一套判定停機與否的程序,那麼它可以把所有描述數的執行結果列表如下:(H代表會停機,N代表不會停機)

還記得上一篇介紹過的康托爾對角線法嗎?現在我們拿來如法炮製,可以編製一個新的描述數,輸入 1 的結果是 ”N”,與 M1 相反;輸入 2 的結果是 “N” 與 M2 相反;……以此類推。這麼一來,這個描述數絕對不在原來的表裡面,也就是出現判定程序不知其執行結果的描述數。

就算把這個新的描述數再納入表中也沒用,因為永遠都可以再用康托爾對角線法,新增一個不在表上的描述數。因此,根本不可能有套程序可以判定任一個描述數會不會停機。停機問題無解,代表數學上的判定性問題也確定無望,希爾伯特的三大提問至此可以休矣。(註三)

計算機不只會計算,還能模擬人的思考方式

1936 年 5 月,圖靈提交這篇影響深遠的論文:《論可計算數及其在判定性問題上的應用》 (On Computable Numbers, with an Application to the Entscheidungsproblem),不但在數學上占有重要地位,更展示許多計算機的創新設計。

他率先提出通用計算機的概念,將不同程式預先載入後再開始運行。而程式轉化為描述數,使得程式和資料共用同一個載體,也是首創。同時描述數做為程式的獨特編號,就相當於電腦程式在記憶體中的貯存位址;許多人相信這個概念啟發了馮紐曼用於 ENIAC 的設計。

圖靈還揭示了常人所未見的計算機角色。計算機的作用向來純粹就只為數學計算,但圖靈在這篇論文中卻是從人類如何思考的角度,討論如何讓機器模仿計算者的心智狀態。多年之後,圖靈提出「圖靈測試」,因而被稱為「人工智慧之父」,但其實這顆種子早在此時就已埋下了。

圖靈為了解決一個抽象的數學問題,而構思出通用圖靈機這台純屬想像的機器。幾年之後二次大戰爆發,這次為了千百萬人的生死存亡,圖靈將動手打造真正的計算機。

__________________________________________________________________________

註一:羅素設想有個集合 R 是由所有不包含它本身的集合所構成的集合。這定義感覺很撓口,但其實相當合理。因為在實際生活的應用上,幾乎所有集合本來就不包含本身,例如我們絕不會說昆蟲這個集合的成員包括昆蟲。問題來了,R 的成員應該包括它自己嗎?

如果說不應該,那麼 R 也是不包含自己的集合,所以 R 也應該屬於 R。但是這樣一來, R 就包含它自己,如此又不符合加入 R 的資格。結果不管 R 包不包含它自身,按照 R 的定義都會導致矛盾,這就是羅素悖論。

註二:算術公設指皮亞諾公設 (Peano axioms),是義大利數學家皮亞諾提出關於自然數的五條公設。

註三:其實美國普林斯頓大學的數學家丘奇 (Alonzo Church) 比圖靈早一個月,於 1936 年 4 月就提出論文,用正統的數學方法解決了判定性問題。圖靈獲悉後,也趕在論文發表前,在附錄處加註說明丘奇的證明。不過丘奇用的形式系統複雜多了,不如圖靈的方法簡單易懂,所以一般講到判定性問題的證明,都還是舉通用圖靈機為例。


數感宇宙探索課程,現正募資中!

文章難易度
張瑞棋_96
423 篇文章 ・ 479 位粉絲
1987年清華大學工業工程系畢業,1992年取得美國西北大學工業工程碩士。浮沉科技業近二十載後,退休賦閒在家,當了中年大叔才開始寫作,成為泛科學專欄作者。著有《科學史上的今天》一書;個人臉書粉絲頁《科學棋談》。


1

2
1

文字

分享

1
2
1

今年夏天絕不能錯過——「搞笑諾貝爾獎世界展」首度登台!

鳥苷三磷酸 (PanSci Promo)_96
・2022/05/17 ・1966字 ・閱讀時間約 4 分鐘

你一定知道諾貝爾獎,但你知道世界上竟然還有搞笑諾貝爾獎(Ig Nobel Prize)嗎?搞笑諾貝爾獎是對諾貝爾獎的有趣模仿,甚至還會邀請真正的諾貝爾獎得主來參加!

搞笑諾貝爾獎由美國的科學雜誌《不可思議研究年報》的主編馬克·亞伯拉罕斯發起,每一屆都號稱「第一屆」,每次都會頒發十座獎盃給各領域中「無法被複製」或「荒唐到不應該再來一次」的研究者,頒獎要旨是希望讓大家能夠"先大笑,再思考"。臺灣也有多位學者共襄盛舉,並曾六度獲獎,臺灣立法院更曾拿下和平獎,其中原因竟然是因為他們以打架替代戰爭!典禮現場更是充滿歡笑,讓人佩服科學家怎麼一本搞笑做研究!

搞笑諾貝爾獎頒獎現場超搞怪!

  • 量身打造獎盃,每年都以當年獲獎的研究為靈感,製作不同主題的獎盃!
  • 不值錢獎金,得獎者會獲得比壁紙還不值錢的高額辛巴威幣作為獎金。
  • 甜便便小姐,得獎者只有 60 秒的時間能發表感言,只要一超時,年幼的「甜便便小姐」就會大叫:「請停下來吧!煩死人了!」直到得獎者下台。
  • 全場亂飛的紙飛機,頒獎典禮中會安排一名背著一個紅色靶心的人,讓台下觀眾將手中紙飛機射向台上的靶心。
2009 年的得獎者們。

今年夏天搞笑諾貝爾獎世界展將首次登台!廢到笑的研究與發人省思的成果,一次集結歷屆讓人目瞪口呆的得獎研究及五大互動體驗,讓你一本正經的捧腹大笑!展區內充滿更多腦洞無極限的幽默科學得獎,一定要揪朋友一起來漲知識。

5/2-5/26 早鳥 $260 限時搶購,購票請洽:https://kham.tw/t14cjEav

ㄎㄧㄤ到爆獎項搶先看

搞笑諾貝爾獎世界展將集結眾多搞笑諾貝爾獎的獲獎研究,其中有許多讓人會心一笑的內容,像是鴿子也懂藝術?日本學者就曾做過實驗,證明鴿子可以分得出畢卡索和莫內的畫;在野外遇到熊怎麼辦?只要穿上防熊裝就不用怕;指甲刮黑板的聲音經研究證實為世界上最讓人痛苦的聲音!

曾有科學家發明出可迅速變身防毒口罩的胸罩,並成功獲得搞笑諾貝爾獎的公共衛生獎,其發明聽起來很荒謬,但背後原因是胸罩是會隨身穿戴的物品,能夠在緊急時刻變成防毒口罩保護他人,符合了搞笑諾貝爾獎頒獎要旨「先大笑,再思考」,另外還曾有一年的「獸醫學獎」頒給發現幫乳牛取名字,就能夠增加產乳量的專家學者!以及最經典的貓貓是液體嗎?也都存在於搞笑諾貝爾獎的得獎研究裡!

  1. 鴿子也懂藝術?|連鴿子都分得出畢卡索和莫內的畫!
  2. 野外遇到熊了怎麼辦?|穿上防熊裝,再也不怕!
  3. 動物也吃重口味!?|綠頭鴨也有戀屍癖!?
  4. 用「屁」交流!|看看鲱魚怎麼用放「屁」溝通!
  5. 逃跑鬧鐘|還想賴床按鬧鐘嗎?鬧鐘本人跑起來給你追!
  6. 最討厭的聲音!|指甲刮黑板太邪惡了!
  7. 如何增加乳牛的產乳量?|不妨給牠取個名字吧!
  8. 胸罩變口罩|在突發的緊急狀況時胸罩變防護口罩!?  
  9. 恐龍走路長甚麼樣子?|在雞的屁股裝上一根棒子就知道!
  10. 貓是液體嗎?|喵星人的貓體力學大解密!

五大互動體驗,只有實驗了才知道

展區現場將規劃五種關於搞笑諾貝爾獎得獎研究的實際互動體驗,讓你能夠化身為小小研究學者,一起來實際試試看、探討世界上經典的搞笑研究!

  1. 吐司永遠是塗奶油的那面先落地嗎?
  2. 挑戰「說話干擾器」!你能夠堅持把話說完嗎?
  3. 極高速烤肉!液態氧+木炭可以燃起多大的火花?
  4. 活性碳內褲過濾屁味?沒有比較沒有傷害
  5. 旋轉吧!高速助產裝置,離心力有助生產?

2022年最寓教於「笑」的展覽,更多大開眼界的搞怪研究,就在國立臺灣科學教育館等你來刷新三觀! 5/2-5/26早鳥$260限時搶購,購票請洽:https://kham.tw/t14cjEav

 圖/歷屆得獎者授獎畫面
圖/日本展出現場照

展覽資訊

  • 展覽名稱:搞笑諾貝爾獎世界展
  • 展覽日期:2022 年 6 月 25 日(六)至 2022 年 9 月 11 日(日)
  • 展覽地點:國立臺灣科學教育館 七樓南側特展區(臺北市士林區士商路 189 號)
  • 展覽時間:平日9:00-17:00/週末、國定假日、暑假 9:00-18:00
    (閉展前 30 分鐘停止售票及入場)
  • 休展日:6/27(一)、9/5(一)
  • 主辦單位:寬宏藝術經紀股份有限公司、三貝多股份有限公司
  • 企劃單位:株式会社ドリームスタジオ(Dream Studio Company)
  • 授權單位:IMPROBABLE RESEARCH, INC.

購票請洽:https://kham.tw/t14cjEav


數感宇宙探索課程,現正募資中!

所有討論 1
鳥苷三磷酸 (PanSci Promo)_96
9 篇文章 ・ 7 位粉絲
充滿能量的泛科學品牌合作帳號!相關行銷合作請洽:contact@pansci.asia