淺談「圖靈機」

cc photo by flickr user Graham C99

早前見到有文章講以前 A level 嘅純數科嘅課程內容好有「藝術」成份,話而家中學 DSE 課程太淺,無緣學到數學嘅真正優美[1]。數學係優美嘅,不過講到滄海遺珠,我覺得仲未論到佢。起碼中小學生由細到大都接觸到數學,就算無緣認識比較深嘅 theorem ,起碼都識到啲簡單嘅,例如畢氏定理嘅幾十萬個 proof [2],你數學老師唔係冇教過你呀? :0) 就算中學無緣,大學讀個 Bachelor of Science 總有機會遇到嘅。

我認為真正嘅「滄海遺珠」,係電腦科學 [3]。因為好多時高中課程連呢科都唔存在,雖然現代生活(包括各種科研)都非常依賴電腦。好多人以為電腦科學係寫程式,又有好多人以為電腦科學只係「一門數學」嚟。我唔同意。電腦科學嘅基礎理論,係探討一啲比「數學」更根本嘅問題;至於電腦科學嘅應用層面,係有超級廣闊嘅光譜,講唔晒嘅,但絕對唔係數理邏輯範疇可以完全涵括。

今日心血來潮,寫下「圖靈機」嘅基本嘢。呢啲係電腦科學最基礎嘅理論,不過我包保冇數學[4]、冇程式,只有純文字。

題外話:阿倫.圖靈 (Alan Turing) 被譽為「電腦科學之父」,近年喺大眾媒體上出過幾次風頭。其一就係英國政府為佢受生前到反同惡法迫害而死道歉,之後更特赦咗佢同性戀嘅「罪」;其二就係有套電影叫《The Imitation Game》,講佢二戰事跡,票房都唔錯。

我今日就講下佢發明嘅「圖靈機」同埋相關嘅概念。未講圖靈機之前,講下個 Church-Turing Hypothesis 先。因為唔講呢樣嘢,可能圖靈機個概念會好似無咩用。

去片~
ーーーーーーーーーーーーーーー
 
邱奇-圖靈猜想 (Church-Turing Hypothesis):

我哋「計數」嘅時候,其實不外乎用紙筆同埋自己個腦,對住啲符號係咁計計計。我哋個腦只不過係一堆「狀態」(state),跟住呢啲狀態去決定下一步做乜,所以我哋大膽假設,任何人類計到嘅嘢,都可以用以下嘅「圖靈機」去描述。
 

圖靈機 (Turing Machine):

「圖靈機」唔係一部實在嘅機器,而係一種概念。係咁嘅:只要有紙有筆,制定一堆可以讀同寫嘅符號,有記憶去記住現下嘅運算狀態,同埋一堆根據現下狀態決定下一步做啲乜嘅規矩(例如讀、寫、狀態轉換),就可以做運算。張紙原本寫咗嘅嘢可以當成輸入,輸出就係用筆寫出嚟嘅嘢。

其實「圖靈機」係將人類一直以來用紙筆去做運算呢種行為,用最概括(generalized)嘅方法描述。「圖靈機」冇講明啲運算符號係點樣,冇講明做運算嗰嚿主體係點樣,冇講明一定要係人腦,你鍾意點都得。可以係火星文,可以係用機器計算,甚至可以冇紙⋯⋯只要你有啲可以讀同寫嘅嘢就 OK。而比較簡單嘅圖靈機,係絕對可以整部真嘅機器出嚟嘅[5]。

 
通用圖靈機 (Universal Turing Machine):

「通用圖靈機」係一種特別嘅圖靈機,特點係普通嘅輸入之前,紙上面會先寫咗一個圖靈機嘅描述。然後呢部通用圖靈機,就可以按照描述去模擬圖靈機。簡單講,通用圖靈機係可以模擬任何圖靈機。(呢樣嘢就等於平時打機講嘅「模擬器」。即係一種電腦「扮」另一種電腦。)

唔好以為「通用圖靈機」要模擬任何其他圖靈機,就需要好勁嘅「硬件」。有人證明到,成為「通用圖靈機」嘅條件簡單到爆。原來只要圖靈機可以數到一到五,記得住五個狀態同埋呢五個狀態之下要做啲乜,然後再設計一種用五個符號嚟表達嘅「語言」去描述想模擬嘅圖靈機、輸入同輸出,就足以模擬任何圖靈機(包括所有更加複雜嘅通用圖靈機)。

至於點樣用咁簡陋嘅圖靈機去整個通用圖靈機出嚟,我係從來冇認真睇過人哋啲 proof 嘅[6]。不過唔緊要,只要證明到通用圖靈機係理論上可以整得到出嚟就夠。事實上,任何現代電腦,包括 70 年代嗰啲電腦,只要你提供好多好多好多好多紙俾佢讀同寫,都可以做到通用圖靈機。(所以你部手機/電腦先可以行到咁多種模礙器之嘛。)

 
小結:

既然任何圖靈機都可以被通用圖靈機模擬,所以只要接受《邱奇-圖靈猜想》[7],通用圖靈機可以模擬人類任何嘅計算。只要人類計到出嚟嘅嘢,圖靈機都計到,而且呢個圖靈機嘅設計可以非常簡陋(只用幾個符號嘅語言,非常少量記憶)。

如果做標題黨,我可以話「只要你有部機器可以記到 ① 至 ⑤,同埋識得 ABCDE ,就可以計算到任何人類識得計嘅嘢喇!」[8]

ーーーーーーーーーーーーーーー
以上係非哲學討論
以下係哲學討論(好似係)
ーーーーーーーーーーーーーーー

講咗咁多嘢,其實啲結論有咩「用」呢? 第一,喺 20 世紀,冇咩人相信機器嘅智慧可以同人類相比。 圖靈發明呢樣嘢係 1936 年,仲未有電腦架[9]。你知人類好自大架嘛,覺得自己係最叻,唔會輕易相信機器可以做啲好勁嘅計算。
「吓?你話一堆廢鐵可以叻過我?唔係呀嘛!」所以圖靈就用「圖靈機」嘅概念去證明:只要你用紙筆計到嘅嘢,機器都做到,而且計算不限形式,不限文字符號。只要係「通用圖靈機」,所有運算形式其實都相等 (equivalent) 嘅。呢啲互相相等嘅運算系統,我哋稱為 Turing-Complete。

Turing-Complete 嘅概念顛覆咗好多人嘅想像。你諗下,我哋而家都時常見到有人大大聲話咩「英文係理性語言」[10],相信 1930 年代都好多人誤以為計數係要特定形式嘅符號或工具,甚至認為需要用人腦先計到複雜嘅數。人類嘅想像力好差架,如果你喺 1930 年話機器可以計到 pi 第 1000 個位,啲人直覺反應就係話你痴線嘅。 就等於早幾年啲人都唔信電腦可以捉圍棋贏到一流高手。

其實圖靈嘅年代都有好幾個邏輯學家做緊相同嘅研究。佢嘅「師父」 Alonzo Church 就係其中一位,Kurk Gödel 都係其中一位。嗰幾位邏輯學家最後都證明咗差唔多嘅結論,但最後大家比較鍾意圖靈提出嘅「圖靈機」概念,因為「圖靈機」將「運算」嘅行為概括(generalize)咗,完全不限制形式。圖靈證明咗任何符號、任何邏輯系統,只要符合好基本嘅條件,就有相等嘅「運算能力」,跳出咗傳統邏輯學用某種數學符號論證嘅框框。

點解我平時咁囂張睇唔起啲玩邏輯符號嘅人?無他,因為我知道佢哋講到好勁勁嘅邏輯系統,其實同隨便一部電腦嘅系統所做到嘅嘢無根本嘅分別。呢個世界有起碼幾百種程式語言,呢啲語言有實際嘅應用,當然都可以用嚟模擬邏輯論證嘅系統。今時今日有啲人仲以為識得幾個邏輯符號就好威威,以為靠幾個死板符號就理解人類「思考」嘅關鍵,豈不可笑?[11]

篇幅有限,有幾樣關於「圖靈機」嘅有趣結論都冇機會詳細講。例如「停機問題」呢啲,有機會再講下啦。

—-
[1] http://drstanford.blogspot.hk/2017/04/dsea-level.html?m=1
[2] 我一個都唔記得
[3] 「電腦科學」其實係一個好奇怪嘅名,一般「科學」係講究「觀察 => 假想 => 驗證」呢類科學方法,但「電腦科學」幾乎從來都冇做任何「觀察」。「電腦科學」嘅基本理論其實係由純粹邏輯同數學構築出嚟,而應用層面就基本上係「工程」嘅嘢。我都唔知科條毛,不過事但啦,啲人咁叫咪算囉⋯
[4] 係,好多人鍾意用數學符號去描述圖靈機。但我用粵文去描述都得掛?你明白圖靈機背後嘅設計概念 (點解佢定義到係任何符號系統都得?),就明白啲符號只係符號嚟,總之你清楚明白紙上面描述緊啲乜就得。
[5]

[6] 望住啲數學/邏輯符號就想死⋯
[7] 至於是否接受 Church-Turing Thesis ,就係一個哲學問題喇。有人覺得人腦有啲「三界六度」以外嘅「靈感」,可以做到 hyper-computation 架。不過呢啲人通常未瞓醒。我就認為, hyper-computation 未必證明到唔存在,但就算你做到,都解釋/證明唔到點解你計出嚟個答案係正確。
[8] 仲要有好多好多好多紙,同埋要有好多好多好多時間…
[9] Charles Babbage 嗰堆嘢連中學雞計數機都不如,只可以計特定嘅嘢,起碼唔係 Universal Turing Machine 嚟。據聞佢之後設計個Analytical Engine 係堅揪嘅,不過從來都冇整到出嚟。
[10] 各有各好啦⋯ 不過好肯定嘅係,只要任何語言能夠準確描述到圖靈機,咁佢哋喺「用嚟計數」嘅層面就相等嘅,只要其中一隻語言計到一個結果,其他相等嘅語言都可以,冇話邊隻比較優秀~
[11] 係呀,好多學嘢唔到家嘅哲學愛好者都唔識 computational theory 架。
—-
利申:我法律系畢業嘅 :0) 如果寫錯嘢請留言指正,唔好打臉。

散彈一號

全職文字工作者、應用哲學家。對「邏輯一致性」、「系統複雜度」之類的偏門學問獨有心得。在美利堅合眾帝國邪惡資本主義集團的領導下,嘗試改變世界。

More Posts

高人指點

comments