# 杜林機

計算理論的中心觀念在於通用電腦(universal computer)的概念,所謂的通用電腦是一步功能超強,能夠模擬任何計算裝置的電腦.只要軟體正確,加上足夠的記憶體和時間,每一部通用電腦都可以模擬任何其他種類的電腦,或是我們已知的任何處理資訊的設備. 這種通用原理所衍生的理論,就是任兩種電腦在功能上最大的差異,只在於它們的運算速度和記憶體的大小.不同的電腦或許有不同的輸入或輸出設備,但這些週邊設備並非電腦的基本特性,就功能而言,所有電腦(及所有通用計算裝置)基本上都是一樣的.

通用電腦的觀念是由英國數學家杜林(Alan Turing,1912-1954)於1937年所提出的,和其他許多計算領域的先驅一樣,當時的杜林也醉心於製造一部會思考的機器,他發明了一套針對普遍用途計算機的架構.杜林將這部虛構的機器稱為[通用機器],因為當時計算者(computer)所代表的意義仍為[做計算的人].

關於杜林機的描述,我們先想像一個數學家在紙卷上進行計算,這紙卷的長度無限長,因此不需要擔心紙會用完而無法運算,不論有多少計算步驟,花掉多少時間,數學家總是可以用這種方式算出任何有解答的計算問題.杜林說明一位精明的數學家所做的計算,即使讓一個愚笨但謹慎的書記員來作,也同樣做得出來,只要他依循一些簡單規則在紙上讀寫資訊.事實上,他宣稱這位書記員甚至可以用一部有限狀態機取代,這部有限狀態機一次只能讀取紙卷上的一個符號,因此我們可以把紙卷想像成一條細長的紙帶,而每一行只有一個符號.

今天,我們稱這部結合有限狀態機及無限長紙帶的機器為杜林機(Turing machine).杜林機的紙帶=現今電腦中的記憶體.

就我們所知,世上沒有任何一種設備的計算能力勝過杜林機,只要時間和記憶體足夠,任何計算裝置能執行的運算,都可以用通用電腦完成.這意味著只要有適當的程式運作,通用電腦就應該能模仿人腦的功能.

目前我們所討論的是二態電腦,以0或1表示所有事物.若電腦以三態邏輯(three-state logic)表示事物(是 否 或許),則它的功能不一定更強,因為可以利用其中一種電腦模擬另一種電腦.但並不代表三態電腦沒有優於二態電腦的地方,Ex.它所需的繞線也許較少,因此體積較小,成本較低,但也只是另一種通用電腦而已.但使用類比訊號的電腦又如何?早期的電腦就是這樣運作,以類比訊號表示量值,稱為類比電腦(analog computer),有別於數位電腦(digital computer),數位電腦的每一個訊號都是獨立的.有人認為類比電腦的功能較強,因為它可以表示連續值,而數位電腦只能表示獨立值.但在現實世界中只有單一數值,而不可能出現一個真正的連續數值.

類比電腦的問題在於其訊號只能達到某種程度的精準度,任何類比訊號都一定會有雜訊,也就是說,當鑑別率達到某種程度之後,訊號就變得雜亂無章.任何類比訊號都會受到不相干或不知名的雜訊干擾,Ex.電子訊號會受到導線內分子的隨機運動干擾,或是打開電燈開關所產生的磁場干擾.雖然可能的訊號有無限多種,但其中能區別出不同意義,表示有效資訊的訊號卻是有限的.若訊號中有個百萬分之ㄧ大小的雜訊,那要區別出不同意義的訊號大約只有百萬個,因此,這個訊號所含的訊息可以用二十位元的數位訊號表示(2**20=1048578).在類比電腦中,要將有效資訊量提升兩倍,就得將所有東西如精準度都提高兩倍,但數位電腦只要增加一個位元就好了.最好的類比電腦其精準度不超過32個位元,而數位電腦往往是以32位元或64位元來表示數字,因此它所能產生的有效訊號個數超過類比電腦.