張貼日期：May 24, 2015 9:41:9 AM

作者：彭俊文（一個小小留學生）

有沒有一種理論可以用來解釋宇宙的全部現象？物理學家會說，我們有大一統理論 (Grand Unification Theory)，那數學家該怎麼回答？

1970 年英國數學家 John Hardon Conway 提出了一個有趣的數學益智遊戲，生命遊戲 Game of Life。在這個遊戲中，玩家決定了初始值後，剩下的事情就是交由這個遊戲自定的規則來得到結果。(讀者如果有興趣深入了解這個遊戲，可以到維基百科)

這個遊戲的背後，隱藏著我們今天故事的主角 —— 自動機。

在介紹我們今天的主角之前，我還想要跟各位玩一個遊戲，這個遊戲是 UniMath 上一篇文章的主題，統計量。如下的一組數列

1, 1, 0, 1, 0, 0, 1, 1, ＿

各位能不能告訴我下一個數字應該是 0 或是 1。(天啊！又是一個只有 0.01% 的人能夠正確回答的問題，不過不要擔心，你現在有 1/2 的機會可以當那 0.01%。)

不管各位讀者是想要找出統一這個世界的理論，或者是單純的想要證明自己就是那 0.01% 的人類，我想各位都已經有足夠的動機 (OS:希望啦) 來進入我們今天的主題，自動機。

自動機，一種最簡單的電腦，是一種被理論電腦科學家在抽象化脈絡下創造出來的電腦。下面這樣的一個示意圖代表著一個自動機。

我們對這個機器輸入一個 a 與 b 組成的 字串 (string)，它會回答一個數字，0 或 1。那它是怎麼決定輸出是 0 還是 1 呢？我想各位聰明的讀者應該已經猜到這台機器是如何運作的。假設今天輸入的字串是 bbaab，這台機器在輸入 bbaab 後會這樣運作，首先他先由圖中藍色箭頭處做為運算的起始點，你可以想像你現在站在圖中 0 的位置 左顧右盼準備往下個目標邁進。你手裡拿著 bbaab，從最右邊讀這個字串，第一個字母（word）是 b，所以你選擇了 b 這條路往下走走到圖上 1 的位置；然後下一個字母是 a，所以你這時候選擇原地繞一圈繼續站在 1 的位置；就這樣不斷地用字串判斷下一步的動向，當你用完最後一個字母時，你應該是站在 1 的位置，所以這台機器就輸出 1。

讓我們再嘗試另一組字串，這次輸入 babaabb，如果各位讀者沒有誤解我的意思的話，我們應該會得到 0。

自動機當然有更為嚴格的定義，但是我們姑且假設只要我們能畫出類似上面這樣的一張圖，我們都稱他為自動機（數學家其實相當懶惰，常常不知道辦不辦得到時，我們就會假設我們辦得到）。

我們想要討論一種特別的自動機，q-automaton，為了形容這一個特別的自動機，我們還是不免俗的要做一些枯燥的定義。

上圖中，我稱那些綠色的數字為 狀態，英文叫做 state，我們定義 Q 為所有狀態的集合。以上圖為例，Q = { 0, 1 }。

另外，紅色的英文字母，我們稱它為 word，我們定義 Σ 為所有 words 的集合。所以上面的例子，Σ= { a, b }。

q-automata 是一種自動機，這種自動機需要滿足 Q = Σ= { 0, 1, 2..., q-1 }。

所以如果將上圖的 Σ= { a, b } 換成 { 0, 1 }（a 換成 0、b 換成 1），那他就是一個2-automaton。

把所有的 words 都用數字表示有什麼好處？

除了美觀、簡潔、大方跟自己爽以外，我們將字母換成數字的最主要原因是所有的整數都可以用 q 進位制來表示，我們最常用的進位制為 10 進位，而電腦世界最常用的當然就是二進位。

所以我們可以將一個整數寫成二進位，然後丟入這個自動機裡面讓它運算，它的結果是：

這樣我們就給出了一組數列 1, 1, 0, 1, 0, 0, 1, 1 ，而這組數列的下一個數字當然是 0，我們叫這樣的一組數列為 automatic sequence。這個統計量代表著當我們將一個整數寫成二進位時，若二進位中 1 的個數為奇數，那電腦就回傳 1，如果其個數為偶數，就回傳 0。

所有自然現象的發動機

回到故事的最一開始，是否有一種理論可以解釋所有的現象，一些科學家相信，所有的自然現象其背後都有一台自動機在運作，

而第一個提出這個想法的為 Konrad Zuse ( Zuse 這個名子後來被用在科幻電影 創．光速戰紀 中，一般相信是為了紀念 Konrad Zuse)。來說說 Zuse 這個人吧，他是一個德國土木工程師、發明家，重要的是，他也是現代電腦的先驅。他最偉大的工作是他在 1941 年發明了人類第一台可以用來寫程式的電腦，也因為他的貢獻，人們將他視為現代電腦的發明者。

Zuse 是一個很容易感覺到無聊的人，他一開始進入大學的時候是讀工程跟建築，後來他覺得兩個東西都很無聊，所以最後是以土木工程畢業的（這有差嗎？）。他畢業後有一段時期是在福特汽車公司工作，做的是廣告（學用不一肯定不是 21 世紀才發明的）。後來他轉行到亨舍爾企業（虎式坦克的設計公司）下的一個飛機製造廠，搖身一變變成設計工程師(我敢定他一定是覺得廣告設計很無聊才轉行的)。

他在設計工程師的生涯裡面需要做大量重複的計算，這又開始讓他感到無聊了，他就開始夢想是不是能設計出一台機器讓他免除掉不斷重複做一個相同的計算。有了這樣的想法，他開始設計他第一台電腦 Z1，並於 1938 年完成，他第一台電腦基於機械原因大部分時間都不太能動。在 1944 年 1 月 30 號的晚上，他的第一台電腦連同設計藍圖在英軍的轟炸下付之一炬。

整個 1936 年到 1945 年期間，他跟當時的科學家與數學家是完全沒有交流的，所以他是完全在自己一個人獨立工作下完成他的 Z系列電腦。1939 年，他受到德國納粹政府的徵招，納粹政府給他資源讓他開發出第二台電腦 Z2 與後來的 Z3 和 Z4，其中 1941 年開發出來的 Z3 就是人類第一台可以藉由卡片打洞來寫程式的電腦。很可惜的，這幾個Z系列電腦都在盟軍之後的一系列空襲中被摧毀。

科技始終來自於人性，Zuse 的生活經驗告訴他大部分的事情都很無聊，或許他覺得他每天的日常生活就像是程式一樣的不斷循環撥放，每件事情都是有一定的規則在背後不斷的循環。生活經驗影響一個人的看待這個世界的方式，而 Zuse 的生活經驗讓他相信，這個世界的每樣事情背後都有一個自動機再循環撥放。

你問我相不相信這樣的看法，我只能說身為一個天橋底下說書的，我實在是沒有佐助的血輪眼能看透所有現象的背後（好吧，我就承認我並不是天才）。

下一集，我們將展現 自動機 在 純粹數學 裡面的力量，敬請期待。