資工系最玄的一門課

如果你問我資工系哪一門必修最為詭異，我會說 “正規語言”，有些學校課程名稱叫做 “計算理論”。這門課沒有任何一行程式，專講一些很玄的東西。

從有限狀態機開始，一路講到很像哲學的東西。例如，這個世界上是不是每個敘述都可以被證明或是舉反例；世界上有沒有一個理髮師可以幫所有不幫自己理頭髮的人理頭髮；或是有沒有一個程式可以判斷另一個程式在某個輸入值時，會不會進入無窮迴圈。

這門課困難的地方是你要模擬自己是一個假想的機器。而且某些證明總是莫名其妙神來一筆。上完課總會覺得，我是誰，我在哪裡。

這門學問在電腦還沒被發明之前，就已經被 Alan Turing 開始研究了。這人眼光真大，連東西還沒發明，就開始研究電腦的極限在哪了。

課本很小一本，而且不厚，比任何一集的哈利波特的還薄。但很詭異的，就算上了一學期的課還是上不完。

https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295/ref=sr_1_2?dchild=1&keywords=Introduction+to+the+Theory+of+Computation&qid=1622494967&s=books&sr=1-2

參考影片

本篇文章是看了以下這部影片才回想起這門課程專門研究這種 “問題可不可解” 的問題。如果你也想嘗試看看這種 ”我是誰，我在哪裡” 的感覺。可以參考以下的影片。