[分享] 模仿遊戲與艾倫圖靈(文長)

模仿遊戲是一部以二次大戰為背景的一部電影,故事中的主角艾倫圖靈是英國的數學家,為了破解德國的加密系統─奇謎(Enigma,電影中稱為英格瑪),設計了一款機器以協助解碼的故事。

在這部電影中,有幾個對於生活科技可以用上的內容,如傳播科技中的傳播原理、解碼加密的部分,科技史的內容以及圖靈測試與人工智慧的關係,都是可以進行探討的題材。其他的部分則可針對亞斯伯格以及同性戀的議題進行討論。 而這邊我們將對艾倫圖靈以及他所提出的圖靈測試、圖靈機以及電影他所設計的機器「炸彈(bomba,電影中將它命名為Christopher,這個我們會在後面進行說明)」進行簡單的介紹,讓老師們可以較容易的將這些議題使用於課程中。

艾倫圖靈(Alan Mathison Turing),出生於1912年6月23日,是位英國的數學家以及邏輯學家,同時也被譽為電腦科學之父。

Alan_Turing_Aged_16
16歲的艾倫圖靈(取自維基百科)

他在1931年即進入了劍橋大學國王學院,畢業後到美國普林斯頓大學攻讀博士學位,二戰爆發後又再度回到劍橋,並協助軍方破解德國的著名密碼系統Enigma,對盟軍取得了二戰的勝利有一定的幫助。

圖靈對於人工智慧的發展有諸多貢獻,在圖靈1950年所寫的一篇論文─《機器會思考嗎?》(Can Machines Think?)即提出了一種可判定機器是否具有智能的試驗方法,就是我們所稱的圖靈測試。而到現在,每年都有還有針對是否能通過圖靈測試的競賽進行著,透過競賽讓各國的程式專家進行挑戰。此外,圖靈提出的著名的圖靈機理論模型則為現代電腦的邏輯工作方式訂下了基礎。

以下我們將從他著名的圖靈測試開始進行介紹。

圖靈測試(Turing test)

圖靈測試是圖靈在1950年所提出的理論,透過此測試將能判斷機器是否能夠思考,或是測試某機器是否能表現出與人等價智能的一種測試方式。此測試使用「談話」進行,並限制談話媒介為電腦鍵盤與螢幕,藉此減少電腦把語句轉換為音頻的困難以及相關的問題。

在此測試的內容如下:
如果一個人(代號C)使用測試對象皆理解的語言去詢問兩個他不能看見的對象任意一串問題。
對象為:一個是正常思維的人(代號B)、一個是機器(代號A)。如果經過若干詢問以後,C不能得出實質的區別來分辨A與B的不同,則此機器A通過圖靈測試。

這樣的討論在當時還沒有電腦的時代,突然就跳到了接近人工智慧的問題,對於當時的人們來說當然是不懂。而在圖靈發表的60年以來,許多科學家以及工程師更不斷地希望去突破這個測試。如在1996年,Joseph Weizenbaum 即曾經創造出一個稱為 ELIZA 的程式,讓不少人認為他們是在跟真人進行交談(陳鍾誠,2014),而在程式人雜誌中:JavaScript (8) – 中文版 Eliza 聊天程式(作者:陳鍾誠)一文裡,作者也透過Java寫出一ELIZA的程式,可讓大家上去玩玩看。到了2011年,有個稱為Cleverbot的程式也成功的欺騙了60%的受試者,讓他們以為自己真的是在跟人談話。而近期的話則屬2014年英國皇家學會所設計的Eugene Goostman最為出名,但由於其設定電腦為13歲的小孩,而且通過的樣本只達29%,因此相關的成效還有受爭議,目前該網站為關閉中。

但圖靈測試這麼困難,是否就對於我們的生活沒什麼關係呢?其實在我們生活中就有許多圖靈測試的變種,像是「反向圖靈測試和驗證碼」,即常見的網站驗證碼以及我們較熟悉的「完全圖靈測試」,因為實際人機互動時,我們不會單純的只接觸螢幕與文字,因此人與可動的機器互動上如何變的真實則是這個部份所討論的。

google_account_captcha

25630359

 圖靈機

談到圖靈,我們更常提到的是圖靈所提出的圖靈機(Turing machine)。

圖靈機是圖靈於1936年提出的一種抽象電腦模型,其更抽象的意義為一種基於數學邏輯而產生的機器,可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。

其基本思法是用機器來模擬人們用紙筆進行數學運算的過程,圖靈將這樣的過程看作下列兩種簡單的動作:
1. 在紙上寫上或擦除某個符號
2. 把注意力從紙的一個位置移動到另一個位置
而在每個階段,人要決定下一步的動作,依賴於(a)此人當前所關注的紙上某個位置的符號和(b)此人當前思維的狀態。 為了模擬人的這種運算過程,圖靈構造出一台假想的機器,該機器由以下幾個部分組成:
1. 一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子,每個格子上包含一個來自有限字母表的符號,字母表中有一個特殊的符號\square表示空白。紙帶上的格子從左到右依次被編號為0, 1, 2, ...,紙帶的右端可以無限伸展。
2. 一個讀寫頭HEAD。該讀寫頭可以在紙帶上左右移動,它能讀出當前所指的格子上的符號,並能改變當前格子上的符號。
3. 一套控制規則TABLE。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作,並改變狀態暫存器的值,令機器進入一個新的狀態。
4. 一個狀態暫存器。它用來儲存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的,並且有一個特殊的狀態,稱為停機狀態

很像我們在計算機概論中讀寫頭的概念。 Maquina

其正式的定義則如下:

一台圖靈機是一個七元組(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}),其中Q, \Sigma, \Gamma都是有限集合,且滿足

  1. Q是狀態集合;
  2. \Sigma是輸入字母表,其中不包含特殊的空白符\square
  3. b \in \Gamma空白符
  4. \Gamma是帶字母表,其中\square \in \Gamma\Sigma \subset \Gamma
  5. \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}是轉移函式,其中L, R表示讀寫頭是向左移還是向右移;
  6. q_0 \in Q是起始狀態;
  7. q_{accept} \in Q是接受狀態。q_{reject}\in Q是拒絕狀態,且q_{reject}\neq q_{accept}

圖靈機M=(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) 將以如下方式運作: 開始的時候將輸入符號串 \omega=\omega_0\omega_1\ldots\omega_{n-1} \in \Sigma^* 從左到右依此填在紙帶的第0, 1, \ldots , n-1號格子上,其他格子保持空白(即填以空白符\square)。 M的讀寫頭指向第0號格子, M處於狀態q_0。機器開始執行後,按照轉移函式\delta所描述的規則進行計算。例如,若當前機器的狀態為q,讀寫頭所指的格子中的符號為x,設\delta(q,x) =(q', x', L),則機器進入新狀態q',將讀寫頭所指的格子中的符號改為x',然後將讀寫頭向左移動一個格子。若在某一時刻,讀寫頭所指的是第0號格子,但根據轉移函式它下一步將繼續向左移,這時它停在原地不動。換句話說,讀寫頭始終不移出紙帶的左邊界。若在某個時刻M根據轉移函式進入了狀態q_{accept},則它立刻停機並接受輸入的字串; 若在某個時刻M根據轉移函式進入了狀態q_{reject},則它立刻停機並拒絕輸入的字串。 轉移函式\delta是一個部分函式,換句話說對於某些q,x\delta(q,x)可能沒有定義,如果在執行中遇到下一個操作沒有定義的情況,機器將立刻停機。

而這套系統由於是一套很基礎的運算系統與法則,同時也開創了電腦運算的基礎架構,因此圖靈被譽為電腦科學之父。 到現在還有許多學校以這為挑戰進行設計。3941765_orig (一群來自里昂高等師範學院的資訊工程系學生用樂高建造的圖靈機複製品。轉自Maker)

電影「模仿遊戲」

模仿遊戲這個名詞是出於圖靈在1950年為提出圖靈測試所撰寫的文章《COMPUTING MACHINERY AND INTELLIGENCE》中第一段所提起的。模仿遊戲中不同圖靈測試的是以三個人作為討論,藉由一對話讓C角色判別A、B誰是男、誰是女,進而再衍伸到機器上。

而在模仿遊戲這部電影中,則是以這個機器智能測驗方式作為貫穿全文故事的引子,主要則是在敘述圖靈於二次大戰時將其圖靈機的理論進行實踐,並設計出一台可破解德軍加密系統Enigma的故事。

但在電影中有些故事則被刪略了,因此要談到這部分的故事我們需要從更早的地方開始說起。

在二次大戰時最厲害的加密系統Enigma是由德國發明家亞圖 雪畢伍斯(Arthur Scherbius)所發明的,這機器是以密碼盤做基礎,透過三個密碼盤進行編碼與紀錄,同時為了使單一文字部出現重複的狀況(如Letter有兩個t,即會增加猜出的機率),因此當一個文字加密後,密碼盤則會向後轉一個單位。

(同期間還有荷蘭的亞歷山大 寇赫(Alexander Koch)以及瑞典的亞維 當姆(Arvid Damm)與美國的發明家愛德華 赫本(Edward Hebern),但三位皆因沒有遇到賞識的金主而作罷。)

P_20150302_144105
一開始設計的奇謎,具有三個編碼器以及一個反射器 [取自 碼書]
因此在三個編碼盤進行加密之後,如果使用英文字母的話則會有26*26*26=17576種組合,然後再透過反射器反射到燈板進行顯示。而為了使加密系統的變化性更高雪畢伍斯之後還增加了幾種加密的方式,而Enigma就在這樣的改進下漸漸變成二戰時期令人聞風喪膽的加密系統了。

首先他增加了讓編碼器拆下進行替換的加密方式,因此又增加了6倍的變換方式。然後又加上了6組接線板的變換(如下圖),讓密碼的變化又增加了110039179500倍。而且德軍的加密鑰匙每天更新,因此所有的解碼皆須在一天內完成,不然就算解出來了也沒有用了。而德國即佔著此龐大的變化優勢讓他們的密碼牢不可破,讓盟軍傷透腦筋。

P_20150302_144123
加入了接線板的功能,將其變換量提升了100391791500倍 [取自 碼書]
P_20150226_205622
軍用奇謎機 [取自 碼書]
P_20150226_205608
軍用奇謎機其內部構造 [取自 碼書]
P_20150226_205811
戰時使用情況 [取自 碼書]
在奇謎發明之後,盟軍就努力地想將其破解,最開始取得奇謎的是法國的情報局,他們透過來自德國的提羅 施密德(Hans-Thilo Schmidt)取得「『奇謎』密碼機使用說明書」因而了解其架構,但由於實在太困難,最後法國則將相關的資料轉給波蘭的密碼局進行破解。

而在波蘭的密碼局中,第一個成功破解奇謎的是馬里楊 瑞傑斯基(Marian Adam Rejewski)。他分析出奇謎中加密鑰匙的重複模式,藉此破解編碼器來破解密碼,再透過文字中的規律來破解接線板的設定。此後,瑞傑斯基就靠著這樣的機器破解出德國的種種加密暗號,平均兩小時就可以破解當天的鑰匙,進而解出當天的暗號。(呵呵,這邊有三句話結束,但其實超複雜,這邊就不一一說明了)

bomba1
bomba 第一台破解奇謎的機器

但這一切在1938年的12月後發生了改變。德國加強了奇謎的密碼強度,從原先的三個密碼盤增加到五個密碼盤,因此原先的6種排列組合增加到60種排列組合,而接線板也從過去的6條增加為10條,因此加密字母從12變成20,所以鑰匙的可能總數即達到電影中所敘述的159000000000000000000種。(18個零)

在這龐大的數量下,已經超過瑞傑斯基可以處理的能力範圍,因此在1939年8月16日,波蘭將奇謎的複製品與「炸彈」的藍圖送到了倫敦。

在相關的機器與資料送到了倫敦之後,這些資料又馬上送到了白金漢郡的柏雷屈里園(Bletchley Park)裡面的政府代碼暨密碼學校。而圖靈才開始進行相關的解碼行動。

圖靈的解法是先蒐集大量的解釋訊息(即解密後的訊息),然後找出其語意中的固定結構。如在電影中所提到的「每天早上六點後的氣象預報」,在文字中的某個區域裡一定會出現Wetter的單字,因此他就針對該單字對應的加密文字進行解碼。他參考奇謎的電路設計以及瑞傑斯基分離加密程序的方式進行分析,進而找出了以下的迴路(如下圖)。 P_20150302_205830 透過這個迴路,他設計出一組電流環路以檢驗出正確的編碼器。當三組編碼器的電路都接通後燈泡就會亮(下圖表示的為當所有電路都正確),即找到正確的編碼。而這組機器只檢驗奇謎所使用的編碼器,對於接線板的部分則使用文字排列的模式進行分析與調整。 P_20150302_205801 因此在這些設計後,1940年3月14日第一台可自行運作的「炸彈」的原型機「勝利(Victory)」抵達了柏雷屈里園,但相關的運作卻不盡人意,因此再1940年8月4日,第二款的「炸彈」抵達,命名為「神之羔羊」(Agnus Dei)或是「艾格妮斯」(Agnes),終於可在當天最新的密碼發出後的一個小時解出密碼。

//所以沒有Christopher唷~~//

結語

呼~好多東西,終於打一個段落了… 其實這部影片可以做為生活科技課程一個不錯的參考教材或是引起動機,因為節奏緊湊,故事又吸引人,學生們應該會有不錯的回響。除了可搭配傳播科技中的解碼加密與訊息傳播等概念,更可透過此一故事討論電腦的發展史與演進史,老師可安排讓學生自行進行資料蒐集,並針對日漸成熟的人工智慧進行討論。 同時,針對電影中為了張力而疏漏的地方,教師也可以再將故事完整的重述一番,讓學生真實的了解整個科技史的脈絡,或許也可以讓他們設計自己的加密罐做為本課程的延伸實作也說不定。 可3D列印的Code Wheel:http://www.thingiverse.com/thing:69473

參考資料:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s