# 杜林機 計算理論的中心觀念在於通用電腦(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位元來表示數字,因此它所能產生的有效訊號個數超過類比電腦. ...

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

# 演算法 ## 演算法與啟發式解法 不論是不是用來處理數字,演算法(algorithm)是一種萬全的程序,保證能達成特定的目的.[演算法]一詞源自阿拉伯數學家花拉子密(al-Khwarizmi),它在9世紀時發明許多演算法.在英文中代數(algebra)這個字其實源自於調換(al jabr)之意.花拉子密的許多演算法至今仍被廣泛使用. 電腦演算法通常以程式描述,由於演算法一詞主要描述的是操作順序,因此相同的演算法可以用不同的電腦語言描述,甚至連接適當的暫存器及邏輯閘於硬體上,以建立另一種演算法. 通常,很多演算法都可以得到相同的結果,只是不同的演算法完成同一件工作的時間不同.某些演算法可能有其他的優點,也許它所需的記憶體較少,或是使用的的訊息模式特別簡單,因此很容易將線路連接於硬體中.好的演算法和壞的演算法對時間與記憶體的需求往往相差超過數千倍,甚至數百萬倍.有時發現新的演算法可以讓你解決一個困擾多時的問題. 由於演算法能以各種方式執行,而且能應用在不同難易度的問題上,因此無法只用解決某個問題所花的時間來評斷演算法的速度,因為解題時間是依執行方式及問題大小而異.通常我們會以解題時間與問題大小之間的關係來描述演算法的速度.撰寫電腦程式最大的樂趣再於找到一種更新更快更有效率的方式來處理問題. ## 最佳演算法 最佳演算法往往不是那麼顯而易見.現在我們想辦法將一疊依序編號的卡片,按遞增順序排列.有一種排列方式是先找出最小的卡片,將它取出後放到一邊.然後在剩下的卡片中再取出編號最小的卡片,將它放在剛才取出的第一張卡片上面.重複這過程直到所有的卡片抽完,會得到一疊依遞增順序排的卡片.以這種方式抽出每一張卡片時,都要先檢視剩下未排序的卡片,若剩下 n 張卡片,則每一次都要比較 n 張卡片上的數字,因此這個演算法執行時間的級數為n**2(n 張卡片 X 比較 n 次). 若我們知道卡片上的編號為 1~n,則可以用另一種方式排序.這方式是利用遞迴定義.要以遞迴檢視一疊卡片時,首先檢視全部的卡片,將所有小於平均值的卡片湊一堆,而大於平均值的卡片置於另一堆,再以同樣的方式處理這2堆卡片,則會得到4堆卡片,以此類推,每遞迴一次,每疊卡片的數量便會減半,最後當每疊卡都只剩一張時,排序工作就完成了.由於這個演算法會反覆將卡片對分,直到剩下一張卡為止,因此他所需要的時間與n張卡片可以對分的次數成正比,也就是以2為底,取 n 的對數(log n),所以這演算法的時間級數為 nlog n.除此之外還有一個更優雅的遞迴演算法,卡片的排列方式不必依序編號,它是將名片依英文字母順序排列時所用的演算法.這種演算法蠻有用的,稱為合併排序(merge sort).雖然不太容易理解.若有兩疊已排序的卡片,則我們只要不斷選取兩疊卡片中,頂端那張字母順序較前的卡片,便可以輕易得到一疊排序過的卡片,合併排序就是利用這個特性.這個合併過程只是合併排序的副程式,而整個演算法運作方式如下-若每疊只有一張卡片,則卡片已完成排序,否則將卡片分成兩半,再以遞迴的方式對這兩半作排序合併的動作,合併排序演算法式展現遞迴及簡潔的絕佳示範. ## 旅行推銷員問題 有一個典型的難題叫旅行推銷員問題(traveling salesman problem).想象有個到處旅行的旅行員要拜訪n個城市,假使已知任兩個城市的距離,那旅行員應以什麼樣的順序走訪這n個城市,才能使總距離最短?沒人知道這問題應以多少級數的演算法才能解決,是 n2 還是 n 的任何次方?若已知的最佳演算法級數為 2n,這表示解題時間隨時間大小呈指數次方成長, Ex.若我們將推銷員拜訪的城市個數增加10個,則問題的難度就增加了1000倍(210=1024),若增加30個,則難度將變成10億倍(230約為10**9).指數演算法在問題變大時就沒什麼用處,但對旅行推銷旅行員問題而言,這是目前所知最佳的演算法.旅行推銷員問題看起來也許不重要,但它卻和許多問題是相當的,也就是所謂的N-P完全問題(N-P complete problem,N-P表示[nondeteministic polynomial],非決定性多項式),而這樣的演算法對這些問題都很有用.若能迅速解答旅行推銷員問題,也就能立刻得到這些問題的解答,果真如此的話,要破解機密資料的密碼就變得輕而易舉了.電腦科技在解決旅行推銷員問題仍然沒什麼突破,即使是運算速對非常快的電腦,也會因多加了幾個城市而變的遲緩. 像旅行推銷員這樣的難題,對電腦來說並不是最最困難的,有些問題的解題時間甚至超過指數級數.也有些無法用演算法解不可計算問題,即使某些問題有演算法可解,但也未必是最好的解法,但依定義來看,演算法是保證能夠完成所要執行的工作,但這樣的保證往往需要付出相當高的代價,在許多型況下,使用[幾乎]能夠得到正確答案的程序更切何實際.一般來說,[幾乎]就已經夠不錯了,若一個法則傾向於得到正解,卻不能保證得到正解,則我們稱之為啟發式解法(heuristic).使用啟發式解法往往比演算法來得實際. 啟發式解法在使用上,最間單的例子就是西洋棋遊戲程式.一個聰明的程式設計師,即使他只有普通的棋藝,卻可以寫出打敗自己的西洋棋程式.這種程式並非演算法,因為它不保證穩贏.啟發式解法是利用經驗及知識做各種猜測,而好的啟發式解法往往能做出正確的判斷.電腦的某些最令人印象深刻的行為都是啟發式解法,而非演算法.要寫出良好的下棋程式,則可以下列啟發式解法作為依據: 1 計算棋盤上所剩的棋子,以評估每位玩家相對的局勢. 2 將棋子下在往後幾步內所能預料的最佳位置. 3 假設對手採取與你相似的策略. 這些法則只是大概的策略,我們也可以想像它們失誤的情況.玩家的相對局勢除了要看所剩的棋子外,棋子所在的位置也很重要.好的位置往往比多一個子來得有利. 利用這些啟發式法則,可以寫出一個下棋程式,模擬往後幾步內所有看起來可行的棋路.最好能同時考慮所有看起來可行與不可行的棋路,並盡可能延長到遊戲結束. 對井字遊戲而言是很容易,但對西洋棋來說,這麼做是不切實際的,即使是用最快的電腦也是如此.在西洋棋遊戲中,玩家有36種移動方式,而每一種移動方式又導致對方有36種回應的可能,平均來說,玩西洋棋時至少都會持續80步以上,因此電腦必須在36**80種可能的狀態中搜尋,這種搜尋即使是最快的電腦也要花上百年的時間才能完成.假設(2)是正確的,並同意最佳路線即為未來幾步內使玩家處於最有利地位的棋路,再指定下棋程式檢視往後的六個步驟.根據(1),下棋程式會檢視六個步驟後雙方的局勢.有了這些假設,再接下來的六個步驟中,電腦不能只選它最想走的路,因為其中還參雜著對手所下的棋子.因此我們必須假設對手會選擇對他自己有利的棋路,這就是(3).因此電腦會沿著六個步驟的所有可能棋路,輪流扮演黑白雙方的棋子.程式在電腦記憶體中的虛擬棋盤上遊走,就像西洋棋大師在腦海中摹想它的棋路一樣.評估黑白棋形式的程式會遞迴的呼叫副程式. 大部分的下棋程式會加入一些額外的啟發式法則,已停止搜尋工作,並對可能的棋路做更深度的搜尋,包括犧牲自己的棋子兌換對方的棋子.這些啟發式法則只是一些附加的揣測,在某些情況下可以改善搜尋品質,但同時可能會造成其他方面的失誤.精雕細琢之後,這個基本搜尋程式幾乎就是所有下棋程式的核心.由於電腦的速度足以考慮數百萬條可能的路線因此它非常有效率,而在這幾百萬條棋路中,總有一條出乎程式設計師意料之外的,甚至連西洋棋高手也無法預測,這就是為什麼在與電腦下棋時,程式設計師往往被電腦打敗. 在電腦程式中,利用啟發式法則在可能狀態中搜尋是相當普遍的,而且也有比玩遊戲更重要的應用,它通常也是電腦尋找[創造性]答案的一種方式,這類問題的解答通常落在一組非常龐大卻有限的可能狀態所成的集合中,我們稱這個集合為搜尋空間(search space).西洋棋的搜尋空間是由一組所有能的棋路所成的集合,而旅行推銷員問題的搜尋空間是連接每個城市的所有可能路徑.由於這些空間非常龐大,無法條列式一一搜索,因此必須靠啟發式法則縮小搜尋範圍,像井字遊戲這種搜尋空間很小的問題,條列式搜尋則是最佳的方式,因為它能保證得到正確答案. 搜尋空間之所以龐大,乃因那些可能狀態是產生於簡單元素的組合,這些元素導致了可能狀態的[組合爆炸],它隨著組合元素的增加呈指數倍爆炸性成長.由於可能狀態是由元素組合所產生的,因此在這個空間中會有距離的觀念,公有元素組合出來的距離比稀有元素組合出來更為接近. 可以想像這些可能狀態是落在一處二維風景中,有時也稱為適切度風景(fitness landscape).每個可能解答的適切度或分數以風景中某一點的高度來表示.若相似的可能解有相近的分數,則相鄰的點有相似的高度,因此可以明確的定義出山丘及溪谷,找尋最佳解就等於尋找最高峰. 要搜尋這樣的空間,最簡單的方式就是隨機挑選一些點加以比較,並紀錄其中最好的點.這種方式所能搜尋的點數只受限於時間,而且它可以應用在任一空間上,這就好像叫一群傘兵跳到這風景的不同位置上,然後叫他們回報所在位置的高度.這種搜尋方式並不是很有效率. 在旅行推銷員問題這樣的搜尋空間裡,鄰近的點可能有著相近的分數,通常較適合的搜尋方式是在相鄰的點跟點之間遊走,就如在丘陵地上只有往上攀爬才能找到頂峰一樣,所對應的啟發式法則就是在搜尋空間裡選擇相鄰的兩解中最佳者. 這方法稱為登山法則(hill climbing),弱點在於你即使登上了某座山的山頂也不保證是最高的山頂.登山法則是一種啟發式法則,並非演算法.還有其他類似登山法則的啟發式法則,而且比較部會困於某座山的頂端.Ex.可由一些隨機抽出的位置開始反覆以登山法則向上攀豋,或往下走,避免困於山頂.登山法則這類的啟發式方法在處理旅行者問題時非常有效,它可以再短時間內得到一組不錯的解,即使有數千個城市,由合理的猜測為出發點,並逐次改善,找出最佳解.利用啟發式法則,我們幾乎能得到幾乎是最佳途徑.要想出針對旅行推銷員問題的迅速啟發式解法並不難,困難的是如何找到最快的演算法. 在許多問題上,並不需要每次都得到最佳解,只要一個能被接受的次佳解即可,因為即使有最完美的解答,我們也未必做得到.對這類的問題電腦會根據知識經驗猜出一個深思熟慮的答案,由於電腦能考慮的組合及可能性極多,因此它所做的猜測常常讓程式設計師驚訝.當電腦使用啟發式法則時,它可能讓我們驚喜,但不免犯錯,因此使它變得有點像人類而不像機器. ...

# 與硬體對話 就像布林邏輯和有限狀態機是電腦硬體的建構區組一樣,程式語言等於是組成電腦軟體的建構區組.和人類的語言一樣,程式語言也有字彙和文法,但不同的是,程式語言的每個字句都有其確切的意義.大部分程式語言就如同布林邏輯是通用的,它們可以描述任何電腦所做的事情. 告訴電腦你要做的事情並不如想像中的容易,必須精確描述任何要求電腦進行的細節與步驟. 程式語言種類繁多,照成多樣性的主要因素包括歷史、習慣及喜好等等,但這些不同的程式語言之所以能繼續存在,主要是因為他們在描述不同事物上各有所長.每種語言都有自己的語法,你必須學會它才能撰寫程式,但與法並非語意的基礎,也不是表達語言的動力,而是像一般語言中的拼字和標點符號一樣.就表達語言的動力而言,最重要在於字彙,亦稱為語言的原詞(primitive),以及如何用原詞組合新概念的方法. 電腦語言有很多種,如 LISP Ada FORTRAN C ALGOL 之類,有些語言對於定義遞迴運算,或在處理非數值資料上有其限制,有些則可以讓程式設計師直接操作位元資料.最近新一代的電腦語言漸漸出頭,就是所謂的物件導向(object-oriented)語言,如 Small-Talk C++ Java 等.這些語言將所要處理的資料結構(如螢幕上的圖形)視為擁有屬性的[物件],這些屬性好比圖畫的位置、顏色等等,而物件可以接受其他物件的命令. 物件導向程式語言最大的優點在於它可以個別定義不同的物件,如電腦遊戲中的各種物件,然後再將物件組合在一起變成新的程式.寫一個新的物件導向程式有點像是把一群動物關在一個籠子裡,然後靜觀其變.在這些虛擬物件互相作用的過程中,程式的行為便浮現出來. 有限狀態機如何執行 logo 這類語言所下的指令?要回答這個問題,我們必須再回到布林邏輯這個層面詳加討論.有限狀態機和 logo 語言之間有三個主要步驟加以連結.首先,我們要了解有限狀態機在加上記憶體(memory)這樣的儲存裝置後,是如何延伸、擴充的,而記憶體可以讓電腦儲存它被要求執行的動作.其次,我們將看到擴充後的有限狀態機是如何依機械語言(machine language)的指令運作,這種語言是一種很簡單的語言,可以明確地指示機器所要執行的運算.最後,我們則會看到機械語言是如何指揮機器解讀logo這類程式語言. 電腦其實只是一種連接了記憶體的有限狀態機.電腦的記憶體,實際上相當於許多用來儲存資料的小隔間組成的陣列,由暫存器建構成,和儲存有限狀態機的狀態所用的暫存器相同. 每個暫存器都可以容納一組位元,稱之為字組(word),這些字組可以被有限狀態機讀取或寫入.每部電腦的字組所含的位元數可能都不太一樣,但現今的微處理器通常是8位元 16位元或32位元(隨科技的進步,字組的位元數也越來越大,如64位元).一般記憶體可能有上百萬個甚至數十億個這樣的暫存器,而每個暫存器都可容納一個字組.在同一時間內,每次只能存取一個記憶體中的暫存器,也就是說在有限狀態機的每個循環中,只能寫入或讀取一個暫存器中的資料. 每個暫存器都有不同的位址(address),位址是一組位元的組合形態,可藉由它找到特定的暫存器,因此暫存器也稱為記憶體中的位置(locations in menory),記憶體包含了一些可以解碼的布林邏輯區組,用以選擇所要寫入或讀取的位置.如果要在某個記憶體位置寫入資料,這些邏輯區組便將新資料寫入指定的暫存器中.若要讀取資料,這些邏輯區組也會將資料由指定的暫存器中引導到記憶體的輸出端,而這個輸出端是連接在有限狀態機的輸入端. 記憶體所儲存的字組有些是要運算的資料,如數字和字母等,也可能是指令,告知電腦執行運算的程序.指令以機械語言的方式儲存.機械語言比一般程式語言來的簡單.機械語言可直接由有限狀態機解讀,在我們所介紹的電腦中,每個機械語言指令都以一個字組儲存,而指令就儲存再一塊依序編號的記憶體位置中,這一連串的機械語言指令就是電腦中最簡單的軟體. 有限狀態機會重複執行下列的程序 1.讀取(read)記憶體中的指令. 2.執行(execute)這個指令所代表的運算. 3.推算(calculate)下一個指令所在的位址. 完成這些工作所需的狀態順序就建構在有限狀態機的布林邏輯中,而指令本身則以位元表示,這些位元組可使有限狀態機對記憶體中的資料作各種運算.例如, Add 指令為一個特定的位元組合,它表示將記憶體中的兩個暫存器相加,當有限狀態機辨識出這個位元組後,會透過一連串的狀態轉換將記憶體中要加總的資料讀出,然後相加,再將總和寫回記憶體. 大部分電腦中都有兩種最基本的指令-運算指令(processing instruction) 控制指令(control instruction). 運算指令是由記憶體存取資料,然後將資料做算數或邏輯計算,而資料所在的記憶體位址或暫存器也是由運算指令所指定.通常指令只與少數暫存器有直接關聯,而以間接的方式對其他暫存器下指令,因為它的位址是存在別的暫存器. EX. Move 指令可將暫存器1中的資料搬移到暫存器2指定的位址上. 控制指令則決定下一個呼叫的指令所在的位址,這個位址儲存在一個特別的暫存器中,稱為程式計時器(program counter).在正常的狀態下,指令從連續的記憶體位置中依序叫出,所以每當叫出一個指令後,程式計數器就會自動加1.控制指令可以改變程式計數器的內容,藉此改變程式執行的順序.最簡單的就是Jump指令它可以將指定的位址儲存在程式計數器中,因此下一個指令便會從此位置中呼叫出.另外還有一種條件式的Jump指令,它只在符合條件的狀態下才會改變程式計數器的內容. 若要重複執行一串相同的指令,則可以在這串指令結束時,利用條件式 Jump 指令將程式計數器移回開始的地方,重複幾次都行,這動作稱為迴圈(loop). ...

# 計算能力 雖然通用電腦可以做任何計算裝置所能計算的事物,但還是有它無法計算的東西,像是定義含糊籠統的問題,實際上我們很少遇到不可計算的問題,因為要找一個定義周詳且大家都想解決的不可計算的問題非常困難,終止問題(halting problem)就是這樣的一個罕見例子.假設我要寫一個電腦程式,用它來檢驗另一個程式最後是否會終止,若被檢驗的程式不包含任何迴圈或遞迴結構,則它最後一定會結束,但若它包含了迴圈或遞迴結構,則程式可能會一直執行下去,因此還是找不到可以檢驗某個程式是否會落入無窮循環的演算法.終止問題是個不可計算的問題. 杜林憑空想像出來的終止問題是不可計算問題的典範,現實中所發生的大部分不可計算的問題都和他一樣或類似.但無法解決終止問題並不能說是電腦的弱點,因為終止問題本來就是不可解的,也就是說沒有一部可以解決終止問題的機器.到目前為止,就我們所了解,沒有任何東西能執行通用電腦所不能執行的計算,數位電腦所能計算的問題顯然也包括任何計算裝置能夠計算的問題.最後這段敘述也稱為邱奇論題(Church thesis),它以與杜林同時期的學者邱奇(Alonzo Church)為名.關於計算及邏輯問題研究,數學家已經討論好幾個世紀了,但科學史上最令人讚嘆的同步學術研究之ㄧ就是杜林 邱奇及波斯特(Emil Post)幾乎同時提出通用計算的觀念.他們的描述方式迴異,但都在1937年發表這些結果,也為以後的計算機革命奠定基礎. 另一個與終止問題很相近的不可計算函數,就是要決定某個已知的數學陳述是真或假的問題.就在杜林提出終止問題不久前,1931年,歌爾德以其不完全定理證明了這個問題亦沒有演算法可解.歌爾德的定理提到,在嚴謹而有效的數學系統中,存在一些無法證明真假的陳述,數學家以證明或反證陳述真假為職責,而歌爾德卻證明他們在某些情況下無法履行這個[職責]. 有些數學家及哲學家認為歌爾德的不完全定理是近乎神秘,不可思議的論調,少部分的人則認為,這個定理證明了人類的直覺終究勝過電腦,也就是說人類或許可以用[直覺]來判斷電腦無法證明的問題.這是一種感情上的爭議,對那些不喜歡和電腦相提並論的哲學家而言,反而成為他們的把柄.但這種事是荒謬的,不論人類是否一瞬間以直覺勝過電腦,從歌爾德的不完全定理來看,我們沒有理由相信世界上存在著任何數學家可以證明但電腦無法證明的數學陳述.據我們目前所知,任何人類所能證明的理論,電腦也可以證明,然而,人類無法計算那些電腦無法解決的不可計算問題. 雖然人類絞盡腦汁才提出一些不可計算問題的例子,但我們卻可以輕易的證明大部分的數學函數是不可計算的.因為任何程式都能以有限個位元表示,而描述一個函數通常都要無限多個位元,因此函數數目要比程式多得多. 函數是什麼?Ex.餘弦或自然對數.數學家可以定義出各類怪異的函數,不一定有其用處,但在數學家眼中,仍是一個合理的函數,因為它能將任一數值完全轉換成另一個數值. 我們可以用數學方式證明函數的個數無限多於程式個數,因此,對大部分的函數而言,都沒有相對應的程式可以計算,若要確實計算出它們的個數相當的困難(包括計算無限多個數,還要分辨不同程度的無限),但結論是正確的,就統計的觀點來說,絕大部分的數學函數都是不可計算的.幸運的是,幾乎所有的不可計算函數都沒什麼用處,事實上所有我們想用來計算的函數都是可計算的. ...

# 語言轉譯 目前已將技術和指令兩者串連起來,但語言是以文字撰寫的,而指令是一些位元組合,電腦本身必須自己將程式轉換成位元組合. 電腦翻譯程式語言的方法就像一個極有耐性的翻譯員一樣,靠著一本字典翻譯用某種其實自己並不熟悉的語言所寫的文件一樣.翻譯員可以在字典中查閱任何他不懂的單字,若定義裡仍出現不懂的字,一樣可以查閱字典,直到完全了解整個意思.在這裡,翻譯員的字典 = 程式,而電腦所認識的文字 = 程式語言原詞.這些原詞是以一連串簡單的機械指令定義出來的. 把一連串的字元儲存在相鄰的記憶體中,每個字元佔一個位置.電腦的記憶體中也有一本字典,它紀錄了每個指令名稱所對應的指令順序位址.電腦可以在字典中搜尋,找出特定的指令名稱及所對應的位址,不只如此,電腦要執行某個特殊指令時,就會從這些字典中找出這個指令定義儲存的地方. 這個搜尋指令的動作可以在程式執行前完成,如此可省掉許多時間,因為假使有個程式要執行很多次,實在沒有道理叫它每次都重複做同樣的搜尋.弱大部分轉換的工作都事先完成的話,則我們稱這過程為編譯(compilaction),而執行編譯動作的程式稱為編譯器.若這些轉換大部分都在程式執行時才做,稱之為直譯(interpretation),而執行這動作的程式稱為直譯器,但兩者不一定是如此壁壘分明. 電腦所執行的動作是由程式指定的,而程式是由程式語言寫成.程式語言會由直譯器或編譯器,透過一組成為作業系統的副程式,轉譯成一連串的機械語言指令.指令定義了資料所要執行的運算,而不論指令或資料,都會儲存在記憶體中.至於有限狀態機的功能,就是將這些指令叫出並加以執行.指令及運算資料都是以位元組合表示,有限狀態機和記憶體則由暫存器及布林邏輯區組所構成,而布林邏輯區組又是以 And Or Invert 這些簡單的邏輯函數所組成.邏輯函數由串聯或並聯的開關操作出來,而這些開關控制了水或電流等物質,以傳遞兩種訊號1或0. 這就是電腦賴以運作的分離階層架構. ...

# 量子計算 電腦所產生的假隨機數列看起來是雜亂的,但它仍是靠某種潛在的演算法計算出來,若知道序列產生的方式,就可以預測它,而它就不再是隨機.而唯一真正達到不可預測效果的,就是量子力學(quantum mechanics).它所產生的效應是隨機性的, Ex.我們無法預測某個鈾原子經過多久會蛻變成鉛.因此我們可以用蓋格計數器(Geiger counter)產生真正隨機的資料,這是通用電腦在原理上所無法辦到的. 量子力學在通用電腦這個議題上引發了一些尚無人能解的問題.初步看來,量子力學似乎和數位電腦非常契合,因為[量子]這個字眼所要表達的基本概念與[數位]是一致的.量子現象和數位的東西一樣,只存在於不連續的狀態中.從量子的觀點來看,物理世界中(外觀上)的連續,類比性質,只限於巨觀尺度下,肉眼所產生的幻覺,但在原子這樣的小尺度中卻不然.在原子的尺度中,幾乎所有的東西都是不連續的,所有現象都是數位的,帶電粒子可以帶數個電子,但無法帶半個電子.不幸的是,主控粒子間交互作用的法則是無法憑直覺得知. Ex.正常情況下,一樣東西無法同時存在於兩個地方,但在量子力學的世界裡卻非如此,因為在量子力學中根本沒有任何東西有其確定位置.一個次原子粒子其實是同時存在於所有地方的,只是我們比較可能會在某個地方觀測到它罷了.一搬來說,我們可以認定某個粒子就在我們所觀測的位置上,但綜合了觀測到的現象,令我們不得不承認它是同時存在於不同地方的.包括物理學家在內,幾乎所有人都覺得這概念難以理解. 目前尚未確認是否可以利用量子效應建構一部強大的電腦,但卻是可能的.原子似乎擅長計算一些特定的問題,如它們的結合方式,這在傳統電腦上很難計算, Ex.當2個氫原子和1個氧原子結合時,這些原子本身以某種方式計算出2個結合鍵之間的角度為107度,我們可以利用量子力學的觀念在數位電腦上算出近似值,但所花的時間會很長,而要得到精確的結果更是費日費時,但一杯水中的每個分子都在一瞬間完成這樣的計算. 電腦之所以要花這麼多時間計算這個量子力學的問題,是因為它必須考慮無限多種可能的水分子型態,才能得到答案.由於原子在組成分子時,可能立刻形成各種不同的組態,所以這樣的計算是必要的,這也就是為什麼數位電腦在有限的時間內只能得到近似值.若要解釋水分子何以能進行這樣的運算,我們想像它是同時嘗試所有可能的組態,就是利用平行處理(parallel processing). 也許可以利用量子中所謂的纏結(entanglement)現象來建構量子電腦.在量子力學系統中,兩個粒子交互作用之後,它們的命運會以某種方式結合在一起,與古典力學看到的截然不同,也就是當我們測量其中一者的某項特性時,也會對另一者的該項特性產生影響,即使兩個粒子實際上並未接觸.愛因斯坦稱這種在時間上沒有任何延遲的現象為超距幽靈效應(spooky action at a distance),他非常不認同世界會以這種方式運作. 量子電腦正是利用這種纏結效應-一個一位元量子暫存器不只能儲存一個0或1,而是可以儲存非常多的0和1,就好像原子可以存在許多地方一樣,一個位元也可以同時有許多狀態(0或1).不是處在0或1之間,因為每個疊置得0和1可以再量子電腦中與其他位元糾結在一起.若以兩個這種量子位元組合成一個量子邏輯區組,則它們的所有疊置狀態可以用不同的方式互動,產生更複雜的纏結組合,而一個利用量子邏輯區組完成的計算量非常龐大,甚至可能到無限多. 量子計算背後的理論已金建立了,但要真正實用仍有些困難.物理學家蕭爾(Peter Shor)最近發現一個利用這些量子效應的方法,至少,在理論上用它來計算因式分解這類重要且困難的計算,而他的成果也使量子電腦重新燃起一片生機,但眼前還有許多難題要去克服.其中一個問題在於,量子電腦中位元在運作時必須保持有秩序的糾結在一起,才能進行計算,然而即使是最細微的干擾,如宇宙射線或甚值處於真空中,都可能破壞纏結狀態.這種現象稱為脫散(decoherence),在量子電腦中,它等於阿契里斯的腳踝.蕭爾所提出的方法似乎僅限於可以利用一般化傅立葉轉換(generalized Fourier transform)這個快速運算方法求值的計算.而這類的問題可能在一般的杜林機就可以輕易的計算出來,若是這樣的話,蕭爾的量子計算只相當於傳統電腦中的某些程式. 若量子電腦可以同時在無限多個可能做搜尋,則它的本質就勝過傳統的計算設備. ...

# Tab problem ## Problem Mac 的 function 中 console.log(‘hihi’) 是按一次 Tab 有 4 個空白 but alert(‘hihi’) 這一行在按 Tab 縮排就有問題，再接續上一行按 enter 下來之後縮排剩 2 個空白，之後再按 Tab 縮排會變成只有 2 個空白 在 fun2 的 function 中都是直接按 4 個空白鍵來作縮排，都正常 ## 發生現象 在按 Tab 縮排過，打完那一行直接按 enter 到下一行，縮排就從 4 個空白變成 2個空白 ## 期望 希望用 Tab 時在 Edit 和 Preview(最終結果)的結果是一樣的 var Mac = function() { console.log('hihi'); if (!console) { alert('hihi'); } } var fun function() { console. ...

# Some different in Mac ## PageDown, PageUp, Home, End It is not useful in setting vimrc. Solution Terminal->Preference->KeyBoard Home: \033[1~ End: \033[4~ PageUp: \033[5~ PageDown: \033[6~ ...

# JavaScript Type number string boolean null undefind 減少 type 轉換以加快執行速度 # Object ## var 宣告後即擁有物件的屬性 宣告之後無法刪除 區域變數 function 內宣告 全域變數 小心使用 ## property 建立在物件中 可刪除 # Array method 1 var arr = new Array(); bug var arr = new Array(10); arr // [undefined × 10] method 2 var arr = []; ...