Archives

Introduction to Computer Theory – Daniel I.A. Cohen

9788126513345_1

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

這本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下載,我看的是第二版實體書。

Leave a Reply