淺談「圖靈機」

早前見到有文章講以前 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)，跟住呢啲狀態去決定下一步做乜，所以我哋大膽假設，任何人類計到嘅嘢，都可以用以下嘅「圖靈機」去描述。呢個假設，叫做「邱奇-圖靈猜想」(Church-Turing Hypothesis)。

圖靈機 (Turing Machine)：

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

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

通用圖靈機 (Universal Turing Machine)：

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

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

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

小結

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

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

ーーーーーーーーーーーーーーー

以上係非哲學討論

以下係哲學討論（好似係）

ーーーーーーーーーーーーーーー

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

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

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

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

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

— —

利申：我法律系畢業嘅 :0) 如果寫錯嘢請留言指正，唔好打臉。