Computer Science - 杜林機
on 2013-08-27
杜林機
計算理論的中心觀念在於通用電腦(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位元來表示數字,因此它所能產生的有效訊號個數超過類比電腦.
Computer Science - 流體電腦
on 2013-08-27
流體電腦
管路以水壓來表示兩種不同的訊號.在液壓活門中,控制端的水流可以操作輸出端水流,但輸出端的水流並不會影響控制端的水流,這限制了訊息的傳遞方向,就某方面來說,也決定了時間順序.同樣的它也提供了了一個增強(amplification)的附加功能,使每一段訊號強度都能回到最大值.即使當輸入的水流因流過細長的管路或因漏損造成壓力減低,輸出的水壓仍然會因活門的開關動作而達到最大壓力.這就是數位(digital)和類比(analog)最大的不同.數位活門不是開就是關,類比就像是水龍頭一樣,可以任意控制水量大小.在流體電腦中,所有輸入訊號只要強到足以移動活塞就可以了,因此這裡所謂[造成顯著改變的差異]就是推動活塞的水壓大小.
既然由於輸入一個微弱訊號仍可以得到最強的輸出訊號,我們就可以連接上千層的邏輯函數,用其中一層的輸出訊號控制下一層邏輯,而不用擔心會有壓力減弱的情形發生,因為每個閘門的輸出訊號都是最強.
這設計型態稱為復原邏輯(restoring logic),而這個流體裝置的例子也特別有趣,因為它與現今電子計算機所用的邏輯幾乎相同.水管的水壓=電路的電壓,液壓活門=用金屬氧化物作成的電晶體,活門上的控制端 輸入端 輸出端=電晶體中的三個接點 閘極(gate) 源極(source) 汲極(drain)