Member-only story

資工系最玄的一門課

--

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

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

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

這門學問在電腦還沒被發明之前,就已經被 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

參考影片

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

--

--

Chen Li-Chi (陳立其)
Chen Li-Chi (陳立其)

Written by Chen Li-Chi (陳立其)

希望所有困難事都可以拆成簡單的事

No responses yet