在很多大學中，電腦系不是附屬於工程學院，便是附屬於科學院。我以前讀的大學很奇怪，電腦系是附屬於數學院，當年我不明白原因，電腦可以用來計數，但電腦和數學有什麼關係呢？我是讀電腦工程系出身的硬件人，當年與電腦科學的同學談起，聽他們說電腦理論很難明高呼救命，天真的我以為讀電腦科學不就是學寫程式嘛，有多難？直至很多年以後，某次去印度工幹買了這本《電腦理論入門》，丟在書架上又過了幾年，然後某天心血來潮打開來看看，前後繼繼續續花了兩年多才看完，終於我明白原來電腦理論不等於電腦，而是數學上如何械械式解答問題的定律。

這本Daniel I.A. Cohen的《Introduction to Computer Theory》，是電腦理論的經典課本。某種意義上，這本書非常沉悶，全本書就好似中學讀數學不停學proof。從最簡單的regular expression開始proof，一路到finite automata，到context-free grammer和pushdown automata，最後就是頂頂大名的萬能電腦原形Turing Machine。證明什麼類形的電腦可以接受什麼類形的language，某notation又可以如何與某graph等同互換。最精彩的章節是詳細解釋Turing Machine，以前上堂聽過這個term，記得教授說過TM是萬能電腦，看完這本書後，終於明白為什麼TM可以計到任何可以計得到的數，即可以解答任何能找出答案的問題。再一次佩服Alan Turing的天材，TM的構造極其簡單，可是沒有任何機械能超越TM的解題能力。

最初開始讀這本書時，我不明白language同電腦有什麼關係，不就是一串串不同的string，起個state machine去判斷一個input是否屬於language之內，程序上是有點麻煩不過也不是很複雜，要用咪call library囉。去到context-free grammer開始看到有點關係，至少寫compiler的第一步就是要parse個syntax tree。一直以無比的耐心閱讀著，逐步逐步follow書中的proof，然後有一天開竅了，忽然間看到language和solve problem之間的關係，任何能夠解答的問題都是一個數學題，電腦就只是從機械化地處理input，然後給一個output的系統，output可以是答案，但更多時間只是一個yes/no answer，又或者更基本的halting problem。找出一個問題的答案，只是最表面那層，找出一問題有沒有可能有答案，如果有答案的話，有限時間內能否找到，那些bounding的meta問題，才是電腦理論的核心。至於如何寫個行得快些慳位些的algorithm去解題，已經是應用層面上技術性的次要問題。

若果不打算理會那些proof，這張圖表大慨是全書內容的總結。老實說那些proof讀完大部份都忘記了，能夠記得大慨就只有這圖表的內容。不過讀proof的最大得著，是讀proof會潛移默化你腦袋的思路，看完知道的東西和未看差不多，但再遇同類問題時會有一份直覺。

初版pdf下載，我看的是第二版實體書。