|
轉(zhuǎn)自：http://blog.sina.com.cn/s/blog_64ac3ab10100ges2.html
一、有限狀態(tài)機 引子 讓我們先來看幾個簡單的概念： 狀態(tài) 狀態(tài)機 有限狀態(tài)機 有限狀態(tài)機的定義 課本中的組合電路+時序電路的模型就是一個有限狀態(tài)機，我們不妨通過它來推測有限狀態(tài)機應(yīng)有的組成： 1. 狀態(tài)有限集S={S0,S1,S2, ...... }。 2. 集合S的特殊元素S0，即為起始狀態(tài)。 3. 輸入字母有限集I={i1,i2, ...... }。 4. 輸出字母有限集O={o1,o2, ...... }。 5. S×I映至S的函數(shù)f，即轉(zhuǎn)換函數(shù)。 6. S映至O的函數(shù)g，即為輸出函數(shù)。 前四個內(nèi)容很容易理解，而f與g這兩個函數(shù)由電路的設(shè)計決定，一般是時序電路（存儲電路）部分決定f，組合電路部分決定g。 具體模型可以用下面圖示表示
有限狀態(tài)機的模型
常用表示方法 而對于計算理論或數(shù)學(xué)中的定義有限狀態(tài)機M，有如下的五元組定義：有窮狀態(tài)轉(zhuǎn)換系統(tǒng)M = 其中S是M的有窮狀態(tài)集，初始狀態(tài)S0∈S，結(jié)束狀態(tài)F?S；M總處在某個狀態(tài)，開始時在S0；A是有窮符號集，h : S×A → S×(A ? { _ }) 是轉(zhuǎn)換函數(shù)（部分函數(shù)），_表示無輸出，若M在狀態(tài)S接到輸入a∈A,假設(shè)h(S, a) = 對比我們總結(jié)的模型，發(fā)現(xiàn)出現(xiàn)了終止狀態(tài)（由于我們所學(xué)電路功能主要是實現(xiàn)計數(shù)、分頻、輸出序列波等持續(xù)性功能，所以沒有接觸到終止狀態(tài)），這說明我們的模型基本反映了有限狀態(tài)機的組成，但只是第二個定義無終止狀態(tài)（即F為空集）的特例，下面我們的討論就采用后面的經(jīng)典定義。 有限狀態(tài)機示例 有限狀態(tài)機在現(xiàn)實生活中其實隨處可見，伸縮式圓珠筆其實就是一個有限狀態(tài)機（兩種狀態(tài)互相轉(zhuǎn)換），下面我們用實現(xiàn)一個簡單的有限狀態(tài)機-自動門。 要求如下：有一自動門，它可以被鎖上，也可以開鎖。當門鎖上時，某人可以在它的槽中塞進一枚硬幣。這樣，門就會自動開鎖，轉(zhuǎn)變到開鎖的狀態(tài)；人通過后，門就會自動鎖上。 對狀態(tài)進行分析可得下圖 仿真代碼： LIBRARY IEEE; USE IEEE.std_logic_1164.ALL; ENTITY door_contr IS PORT ( ); END door_contr; ARCHITECTURE behavior OF door_contr IS PROCESS (clk) END behavior; QuartusⅡ下的仿真結(jié)果 當然，上面講述的還是一個沒有停止狀態(tài)的有限狀態(tài)機，而且是由電子電路實現(xiàn)的，接下來的例子是在軟件方面具有有限狀態(tài)的有限狀態(tài)機。 這是一個地址識別的算法。日常我們描述地址（指中文）的語句中地址級別是依次降低的，國家、省（直轄市）、市、區(qū)縣、街道、門牌號（或者從區(qū)縣之后是鄉(xiāng)、村）。而這些就是我們要構(gòu)造的有限狀態(tài)機的全部狀態(tài)。這些狀態(tài)構(gòu)成的狀態(tài)圖是單向圖，比如，當前的狀態(tài)是“省”，如果遇到一個詞組（即輸入）和市名有關(guān)，我們就進入狀態(tài)相應(yīng)“市”（即狀態(tài)轉(zhuǎn)換）；走到最低級的地址單位（即終止狀態(tài)），那么這條地址是有效的，否則無效。比如說，“北京市海淀區(qū)清華大學(xué)紫荊公寓2#”對于上面的有限狀態(tài)機來講有效，而“上海市遼寧省石家莊市”則無效（因為無法從市走回到省，即便可以也會由于石家莊市不屬于遼寧省而進入錯誤狀態(tài)）。 使用有限狀態(tài)機識別地址，關(guān)鍵要解決兩個問題，即通過一些有效的地址建立狀態(tài)機，以及給定一個有限狀態(tài)機后，地址字串的匹配算法，而這兩個問題都有現(xiàn)成的算法。有了關(guān)于地址的有限狀態(tài)機后，我們就可又用它分析網(wǎng)頁，找出網(wǎng)頁中的地址部分，建立本地搜索的數(shù)據(jù)庫。同樣，我們也可以在搜索引擎中對用戶輸入的查詢進行分析，挑出其中描述地址的部分，當然，剩下的關(guān)鍵詞就是用戶要找的內(nèi)容。 以上就是有限狀態(tài)機的實際應(yīng)用，這讓我們感到它的功能的確很強大。其實想想看，無論對連續(xù)系統(tǒng)還是離散系統(tǒng)，狀態(tài)概念無所不在，有限狀態(tài)機提供了一種描述和控制應(yīng)用邏輯的非常強大的方法，具有規(guī)則簡單、可讀性和可驗證性強等特點。 有限狀態(tài)機的弱點 1、 每一種有限狀態(tài)機均功能唯一，即設(shè)計好之后無法完成其他原理不同的工作； 2、 因為其狀態(tài)有限，當所要描述的系統(tǒng)的狀態(tài)太多時，可能確定的有限狀態(tài)機無能為力； 3、 有一些任務(wù)是有限狀態(tài)機無法完成的，比如它可以判斷輸入的0、1數(shù)列中0或1的個數(shù)是否為奇數(shù)或偶數(shù)，但是無法判斷0是否比1多或者相反。 前兩個問題表示有限狀態(tài)機的可擴展性差（或者對比計算機而言是無可編程性），而后者是因為有限狀態(tài)機狀態(tài)有限而且不能記下自己需要記錄的東西（或者對比圖靈機理論是不能寫）。 于是我們發(fā)現(xiàn)有限狀態(tài)機不但狀態(tài)有限，功能也有限（根據(jù)計算理論，這是因為它只能接受正則語言，而正則語言是最低級的語言，所以能夠解決的問題是有限的）。 事實上，最初的計算“機”（其實更應(yīng)該說是計算器）都是功能單一的，雖然人們不斷地試圖在一臺機器上集成更多的功能，但是相對于下面要講到通用計算理論，這些行為還是“盲目”的。 二、圖靈機 圖靈機理論的提出及相關(guān)理論： 下面我們的主人公將是圖靈，也許你現(xiàn)在對他一無所知，但閱讀這一節(jié)后，你需要深刻的記住他，因為在我看來，是他啟發(fā)與影響了他之后的整個計算機發(fā)展史。為了讓大家更好地理解與接受他的理論，我會多穿插一些背景，畢竟天才也不是生活在真空中的。 圖靈早年在劍橋大學(xué)求學(xué)，在那個年代，劍橋大學(xué)的大數(shù)學(xué)家羅素和懷特海已經(jīng)創(chuàng)立了“數(shù)理邏輯學(xué)”?！皵?shù)理邏輯”這個學(xué)科的創(chuàng)建，起源于一個邏輯上的“悖論”。為了非專業(yè)人士都能明白邏輯悖論的含義，哲學(xué)家或者數(shù)學(xué)家喜歡用講故事的辦法來解釋它。一個經(jīng)典的故事是：村子里有位理發(fā)師，他為而且只為村子里所有那些不給自己理發(fā)的人理發(fā)。數(shù)學(xué)的邏輯推理上會出現(xiàn)類似的悖論。數(shù)學(xué)家們十分擔(dān)心“數(shù)學(xué)大廈”會因悖論的存在而坍塌，于是他們都想方設(shè)法去修補數(shù)學(xué)基礎(chǔ)。例如，康托發(fā)表專著《集合論》，羅素與懷特海聯(lián)合撰寫三卷《數(shù)學(xué)原理》。 不過圖靈在提出圖靈機構(gòu)想之后，又發(fā)現(xiàn)了新問題，有些問題圖靈機是無法計算的。比如定義模糊的問題，如“人生有何意義”，或者缺乏數(shù)據(jù)的問題，“明天3D中獎號是多少”，其答案當然是無法計算出來的。但也有一些定義完美的計算問題，它們亦是不可解的，這類問題稱為不可計算問題。 不可計算的問題在實踐中幾乎碰不到，事實上，很難找到這樣的例子，既不可計算但又有人向計算的明確定義的問題。一個罕見的問題是所謂的停機問題。設(shè)想要編寫一個用于檢查并判定另一個程序是否會運行結(jié)束的程序，而事實上，不存在一個程序能夠判斷另一個程序是否與無限循環(huán)有染。我們可以來這樣設(shè)想：假定我們有一個Test程序，此程序把別的測試程序當成輸入，我們把它插入另一個程序Paradox（悖論）中，并在Test中使用Paradox函數(shù)作為參數(shù)（即Paradox（） { … ；Test（Paradox）；…}）。這個Paradox函數(shù)的編寫思路是這樣的，如果Test程序判斷Paradox會運行結(jié)束，那么Paradox就進入無限循環(huán)，如果Test判斷Paradox不會結(jié)束，則Paradox函數(shù)立刻終止。于是Test函數(shù)對Paradox函數(shù)無效，所以判斷函數(shù)是否會終止的程序不存在。 計算機不能解一些問題并不是計算機的弱點，因為停機問題本質(zhì)上是不可解的，不可能建造出一個解停機問題的機器。通用計算機無法完成的計算，無論什么東西同樣無法勝任。 圖靈機的定義與舉例： 接下來我們給出圖靈機模型的一個嚴格的形式定義： 一個圖靈機是一個七元組（Q，∑，σ，δ，q0，qaccept，qreject），其中Q，∑，σ都是有窮集合。 Q是狀態(tài)集； ∑是輸入字母表，不包括特殊空白符號； σ是帶字母表，其中包括∑與空白符號； δ：Q×σ→Q×σ×（L，R）是轉(zhuǎn)移函數(shù)； q0∈Q是起始狀態(tài)； qaccept∈Q是接收狀態(tài)； qreject∈Q是拒絕狀態(tài)； 下面是圖靈機的圖示： 從上述形式定義可以看出模型的關(guān)鍵在于有窮控制器中的狀態(tài)轉(zhuǎn)換函數(shù)，根據(jù)圖靈的通用計算理論，這個轉(zhuǎn)換函數(shù)是靈活可變的（對應(yīng)于通用圖靈機），當然也可以使單一的（對應(yīng)于專用圖靈機，即便如此，它的能力也強于有限狀態(tài)機，因為圖靈機是可以接受0級語言的），不過這并非圖靈提出圖靈機的意義所在。 下面我們來比較有限狀態(tài)機與通用圖靈機的區(qū)別所在： 1、 圖靈機既能讀又能寫； 2、 帶子是無限長的（可以無限存儲，結(jié)合讀寫頭既能左移又能右移的特點，當然就可以解決判斷輸入的0與1個數(shù)誰多的問題），而且?guī)ё由喜坏梢詫懭霐?shù)據(jù)，還可以寫入實現(xiàn)某一具體功能的； 3、 進入拒絕和接收狀態(tài)立即停機； 同有限狀態(tài)機一樣，我們構(gòu)造一個圖靈機來實現(xiàn)一個簡單的功能。 目標：利用二進制來設(shè)計一個專門計算“x+1”的圖靈機，要求計算完成時，讀寫頭要回歸原位。 狀態(tài)集合K： {start，add，carry，noncarry，overflow，return，halt}； 字母表∑：{0，1，*}； 初始狀態(tài)s：start； 停機狀態(tài)集合H：{halt}； 規(guī)則集合δ： 實現(xiàn)步驟： ---------------------------------------------------------------- ---------------------------------------------------------------- ---------------------------------------------------------------- 從這個過程中我們發(fā)現(xiàn)，雖然圖靈機可以實現(xiàn)x+1的功能，但是他的工作流程理解起來并不是人們?nèi)粘５挠嬎氵^程，甚至與現(xiàn)代計算機的計算原理也并無太大相關(guān)。這是因為與現(xiàn)代計算機相比，它的計算方式也還是有局限性，由于圖靈機每次只能讀入一個數(shù)據(jù)，改寫所讀入的數(shù)據(jù)，而不像現(xiàn)代計算機可以同時讀入多個數(shù)據(jù)、改寫其他數(shù)據(jù)，所以相應(yīng)的算法難理解性也就增加。 圖靈機的意義與思想內(nèi)涵： 圖靈提出圖靈機的模型并不是為了同時給出計算機的設(shè)計，它的意義我認為有如下幾點： 1、 2、 3、 對圖靈機給出如此高的評價并不是高估，因為從它的設(shè)計與運行中，我們可以看到其中蘊涵的很深邃的思想。 通用圖靈機等于向我們展示這樣一個過程：程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結(jié)果，結(jié)果也保存在存儲帶上。 另外，我們可以隱約看到現(xiàn)代計算機主要構(gòu)成（其實就是馮諾依曼理論的主要構(gòu)成），存儲器（相當于存儲帶），中央處理器（控制器及其狀態(tài)，并且其字母表可以僅有0和1兩個符號），IO系統(tǒng)（相當于存儲帶的預(yù)先輸入）； 偉大的圖靈: 正是在圖靈搭建的理論基礎(chǔ)之上，計算機才有了后來的蓬勃發(fā)展。美國的阿坦納索夫在1939年果然研究制造了世界上的第一臺電子計算機ABC，其中采用了二進位制，電路的開與合分別代表數(shù)字0與1，運用電子管和電路執(zhí)行邏輯運算等。ABC是“圖靈機”的第一個硬件實現(xiàn)。馮·諾依曼不僅在上個世紀40年代研制成功了功能更好、用途更為廣泛的電子計算機，并且為計算機設(shè)計了編碼程序，還實現(xiàn)了運用紙帶存儲與輸入。至此，天才圖靈在1936年發(fā)表的科學(xué)預(yù)見和構(gòu)思得以完全實現(xiàn)。 明白了圖靈那無與倫比的貢獻，人們就不難理解，何以馮·諾依曼對于“計算機之父”的桂冠堅辭不受。曾經(jīng)擔(dān)任過馮·諾依曼研究助手的美國物理學(xué)家弗蘭克爾教授這樣寫道：“許多人都推舉馮·諾依曼為“計算機之父”，然而我確信他本人從來不會促成這個錯誤?；蛟S，他可以被恰當?shù)胤Q為‘計算機的助產(chǎn)士’。依我之見，正是馮·諾依曼使世界認識了由圖靈引入的計算機的基本概念?！备ヌm克爾教授此言不虛，在1949年，馮·諾依曼發(fā)表了一篇題為《自動計算機的一般邏輯理論》的論文，客觀而公正地闡述了圖靈在計算機理論上的重大貢獻。他寫道:“大約12年前，英國邏輯學(xué)家圖靈就開始研究‘可計算問題’，他準確地給出了‘自動計算機’的一般性定義?！瘪T·諾依曼寧愿把“計算機之父”的桂冠轉(zhuǎn)戴在圖靈頭上。當然，這已經(jīng)是在圖靈離開普林斯頓十來年以后的事了，他當年在普林斯頓并沒有像后來那樣受人景仰。圖靈曲高和寡，當年就能看明白他那篇文章劃時代意義的，僅僅是少數(shù)杰出的數(shù)學(xué)家，如馮·諾依曼者。 三、構(gòu)建現(xiàn)代計算機 整理我們的理論基礎(chǔ)： 從人類科技發(fā)展的歷史來看，當理論成熟或即將成熟之日，也就是人們開始著手實現(xiàn)之時（雖然在理論創(chuàng)立之前也會有人嘗試，但還是那句評價，“盲目”）理論指導(dǎo)實踐就是這個道理。下面我們就沿著有限狀態(tài)機、圖靈機的這條思路，將自己置身于二十世紀中葉，聯(lián)系當時的技術(shù)能力，來構(gòu)建出一臺我們自己的計算機。 隨后我們遇到的問題是如何將我們想要表達的問題轉(zhuǎn)化為0、1代碼，當然，不同的問題經(jīng)過不同人的處理會有不同的邏輯表示，關(guān)鍵是要保證計算機明白你要表達的真實意思，而這只要你在表示的同時給出一個編碼原則。這里最本質(zhì)的概念是信息，哲學(xué)家格雷戈里·貝特森將信息定義為“生異之異（the difference that makes a difference）”，換句話說，信息是一種差異性、可能性，同時它又有影響其它信息的能力，這樣看來信息是完全可以用二進制位來表出的。例如，當你和別人談話時，說的每個字都是字典中所有字中的一個。如果給字典中所有的字從1開始編號，我們就可能精確地使用數(shù)字進行交談，而不使用單詞(當然，對話的兩個人都需要一本已經(jīng)給每個字編過號的字典以及足夠的耐心) ，人與計算機的交談也是這個道理。 初步實現(xiàn)計算機： 那么接下來我們就要考慮如何通過現(xiàn)有（二十世紀中葉）的技術(shù)來實現(xiàn)一個二進制系統(tǒng)，是的我們想要實現(xiàn)的運算在里面流動（進行），并最終流出。先不要著急，我們先來看一下前人的研究成果， 早在17世紀，歐洲一批數(shù)學(xué)家就已開始設(shè)計和制造以數(shù)字形式進行基本運算的數(shù)字計算機。1642年，法國數(shù)學(xué)家帕斯卡采用與鐘表類似的齒輪傳動裝置，制成了最早的十進制加法器。1678年，德國數(shù)學(xué)家萊布尼茲制成的計算機，進一步解決了十進制數(shù)的乘、除運算。1834年，英國數(shù)學(xué)家巴貝奇在研制差分機的工作中，看到了制造一種新的、在性能上大大超過差分機的計算機的可能性。他把這個未來的機器稱為分析機。巴貝奇的分析機由三部分構(gòu)成。第一部分是保存數(shù)據(jù)的齒輪式寄存器，巴貝奇把它稱為“堆?！保c差分機中的相類似，但運算不在寄存器內(nèi)進行，而是由新的機構(gòu)來實現(xiàn)。第二部分是對數(shù)據(jù)進行各種運算的裝置，巴貝奇把它命名為“工場”。第三部分是對操作順序進行控制，并對所要處理的數(shù)據(jù)及輸出結(jié)果加以選擇的裝置。為了加快運算的速度，巴貝奇設(shè)計了先進的進位機構(gòu)。他估計使用分析機完成一次50位數(shù)的加減只要1秒鐘，相乘則要1分鐘。計算時間約為第一臺電子計算機的100倍。同時，在多年的研究制造實踐中，巴貝奇寫出了世界上第一部關(guān)于計算機程序的專著。 這臺分析機雖然已經(jīng)描繪出有關(guān)程序控制方式計算機的雛型，但限于當時的技術(shù)條件而未能實現(xiàn)。 我們不難總結(jié)出這幾點： 1、 2、 3、 此外，在那時，有人制造過模擬機器，即不是用我們已經(jīng)認同的離散數(shù)字信號做處理。我們在介紹采用0、1編碼時，并沒有明確排除模擬信號計算的可能性，事實上，這確實是可能的，不過現(xiàn)在我們來解釋一下我們之所以不那樣做的原因。 在物理世界中，完全意義上的連續(xù)流是無法做到的，模擬計算機的問題是其信號只能達到有限的精度。一種模擬信號-無論是電氣信號、機械信號或化學(xué)信號-都會包含一定程度的噪音，即到某一級分辨率上，信號基本上是隨機的。任何模擬信號，必然受到大量無關(guān)的、未明噪音源的影響。如果信號中有百萬分之一的噪音，那么，杜宇信號來說，只有一百萬中有意義的差異。既然如此，那信號中的信息大可用一個20個二進制位組成的十進制信號來表示（220=1048578）。在一個模擬計算機中，是有意義的差異的個數(shù)再翻一番，需要使其中每樣?xùn)|西的精度提高一倍，而在數(shù)字計算機中，只需增加一個二進制位便可，其實最好的模擬計算機的精度不到30個二進制位。 那好，現(xiàn)在我們可以充滿信心的使用離散數(shù)字信號，也應(yīng)當把目光從機械機上移開，機械及由于其在速度、規(guī)模、穩(wěn)定性、精確度上的缺陷，無法成為我們所要設(shè)計的機器的有效載體。再強調(diào)一遍，我們處在20世紀中葉，這時候電工學(xué)、電子學(xué)不斷取得重大進展，在元件、器件方面接連發(fā)明了真空二極管和真空三極管；在系統(tǒng)技術(shù)方面，相繼發(fā)明了無線電報、電視和雷達。所有這些成就為現(xiàn)代計算機的發(fā)展準備了技術(shù)和物質(zhì)條件。相對于機械機而言，電路可以有更高的工作頻率（意味著計算速度更快）、更小的規(guī)模、更穩(wěn)定、更加精確（高低電平表示不同狀態(tài)），而且在存儲方面它相對于機械機有更大的優(yōu)勢（而這也是我們的主要需求），所以我們把目標放在電子電路實現(xiàn)上。 我們已經(jīng)知道了用0、1表示信息，也想好了用電路的高低電平表示0、1，那么下一步就是如何進行信息存儲與簡單運算（寫到這里可以發(fā)現(xiàn)，跟數(shù)字電子技術(shù)課程的流程是一樣的）。 來看兩個比較重要的事件：1904年，John A.Fleming 取得真空二極管的專利權(quán)；1947年,英國完成了第一個存儲真空管?？磥砦覀兛梢允褂盟鼈兊模诉@些東西之外，我們還有一些器件是可以使用的，比如存儲器件中，可以的選擇有水銀延遲線存儲器、陰極射線示波管靜電存儲器、磁鼓和磁心存儲器等，好了，有了這些硬件之后，我們就可以專心于電路邏輯上的設(shè)計了。 最初的時候肯定是沒有組合電路邏輯電路之分的，更沒有《數(shù)字電子技術(shù)》這本書，可是我們還是根據(jù)邏輯式的推導(dǎo)與構(gòu)想，掌握一些基本電路的設(shè)計方法的（注意，不是電路設(shè)計的基本方法），我覺得一項新技術(shù)或新產(chǎn)品的往往是這樣：人們大概有一個方向，抽象出一定的模塊與功能，然后一點一點的加以實現(xiàn)，起初人們掌握的是最基礎(chǔ)的知識，在實現(xiàn)的過程中，他們要通過摸索去搭配與做修改，與此同時，他們慢慢積累總結(jié)出一般方法，最終形成成熟的工藝流程。比如，設(shè)計電路的過程中，我們會發(fā)現(xiàn)一些區(qū)別，有的電路只與當前輸入有關(guān)，而另一些電路還與過去的輸入有關(guān)，當然我們可以總結(jié)出組合電路與時序電路概念與設(shè)計上的區(qū)別來。就是這樣一點一點，我們可以設(shè)計出符合簡單運算要求的邏輯電路來，當然這里還是涉及一些理論的東西的，那就是要設(shè)計出多少什么功能的基本運算單元才能保證把任何問題分解成的子運算都屬于我們的基本運算單元集。這個問題現(xiàn)在（二十一世紀）的爭議是要構(gòu)建簡單指令集還是復(fù)雜指令集，而且不同種CPU它們的指令集是不同的，這的確是一個復(fù)雜的問題，但是我們在二十世紀中葉的時候主要目的還是科學(xué)計算與軍事應(yīng)用，需要的指令應(yīng)該也還不多吧，所以這個問題我們就跳過了。 最后就是真正的對照設(shè)計方案連接我們的計算機了，電子管組成的運算電路、各種器件組成的存儲器通過導(dǎo)線的連接（當然，運算電路、存儲電路、IO輸入的架構(gòu)還是一個很不容易產(chǎn)生但很偉大的想法的，雖然它在圖靈機中已經(jīng)有所體現(xiàn)。我們在這里把它忽略掉，下面將有介紹），終于可以使用了！ 我們的設(shè)計歷程到此成功結(jié)束，但是我們還是忽略了細節(jié)，而且我們還是以自己現(xiàn)在的思維，做出了一些自認為顯然的判斷與設(shè)計，我們還是有必要翻開歷史，回顧一下計算機真實的發(fā)展歷程，雖然有時候看起來笨拙而可笑，但應(yīng)當說它們都是自身所處時代的最優(yōu)解，現(xiàn)在的計算機絕不是一蹴而就的，況且，我們現(xiàn)在的計算機也許就是未來人眼中的ENIAC。 計算機真實的發(fā)展歷史： 1946年2月14日，標志現(xiàn)代計算機誕生的ENIAC(Electronic Numerical Integrator and Computer)在費城公諸于世。ENIAC代表了計算機發(fā)展史上的里程碑，它通過不同部分之間的重新接線編程，還擁有并行計算能力。ENIAC由美國政府和賓夕法尼亞大學(xué)合作開發(fā)，使用了18，000個電子管，70，000個電阻器，有5百萬個焊接點，耗電160千瓦，其運算速度比Mark I快1000倍，ENIAC是第一臺普通用途計算機。 重大突破是由數(shù)學(xué)家馮·諾伊曼領(lǐng)導(dǎo)的設(shè)計小組完成的。1945年3月他們發(fā)表了一個全新的存儲程序式通用電子計算機方案—電子離散變量自動計算機(EDVAC)，主要設(shè)計原則是： 第一代計算機的特點是操作指令是為特定任務(wù)而編制的，每種機器有各自不同的機器語言，功能受到限制，速度也慢。 第二代晶體管計算機(1956-1963) 1948年，晶體管的發(fā)明大大促進了計算機的發(fā)展，晶體管代替了體積龐大電子管，電子設(shè)備的體積不斷減小。1956年，晶體管在計算機中使用，晶體管和磁芯存儲器導(dǎo)致了第二代計算機的產(chǎn)生。第二代計算機體積小、速度快、功耗低、性能更穩(wěn)定。首先使用晶體管技術(shù)的是早期的超級計算機，主要用于原子科學(xué)的大量數(shù)據(jù)處理，這些機器價格昂貴，生產(chǎn)數(shù)量極少。 1960年，出現(xiàn)了一些成功地用在商業(yè)領(lǐng)域、大學(xué)和政府部門的第二代計算機。第二代計算機用晶體管代替電子管，還有現(xiàn)代計算機的一些部件:打印機、磁帶、磁盤、內(nèi)存、操作系統(tǒng)等。計算機中存儲的程序使得計算機有很好的適應(yīng)性，可以更有效地用于商業(yè)用途。在這一時期出現(xiàn)了更高級的 COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等語言，以單詞、語句和數(shù)學(xué)公式代替了含混晦澀的二進制機器碼，使計算機編程更容易。新的職業(yè)(程序員、分析員和計算機系統(tǒng)專家) 和整個軟件產(chǎn)業(yè)由此誕生。 第三代集成電路計算機(1964-1971) 雖然晶體管比起電子管是一個明顯的進步，但晶體管還是產(chǎn)生大量的熱量，這會損害計算機內(nèi)部的敏感部分。1958年德州儀器的工程師Jack Kilby發(fā)明了集成電路(IC)，將三種電子元件結(jié)合到一片小小的硅片上?？茖W(xué)家使更多的元件集成到單一的半導(dǎo)體芯片上。于是，計算機變得更小，功耗更低，速度更快。這一時期的發(fā)展還包括使用了操作系統(tǒng)，使得計算機在中心程序的控制協(xié)調(diào)下可以同時運行許多不同的程序。 第四代大規(guī)模集成電路計算機(1971-現(xiàn)在) 出現(xiàn)集成電路后，唯一的發(fā)展方向是擴大規(guī)模。大規(guī)模集成電路(LSI)可以在一個芯片上容納幾百個元件。到了80年代，超大規(guī)模集成電路 (VLSI)在芯片上容納了幾十萬個元件，后來的(ULSI)將數(shù)字擴充到百萬級。可以在硬幣大小的芯片上容納如此數(shù)量的元件使得計算機的體積和價格不斷下降，而功能和可靠性不斷增強。 70年代中期，計算機制造商開始將計算機帶給普通消費者，這時的小型機帶有友好界面的軟件包，供非專業(yè)人員使用的程序和最受歡迎的字處理和電子表格程序。這一領(lǐng)域的先鋒有Commodore， Radio Shack和Apple Computers等。 1981年，IBM推出個人計算機(PC)用于家庭、辦公室和學(xué)校。80年代個人計算機的競爭使得價格不斷下跌，微機的擁有量不斷增加，計算機繼續(xù)縮小體積，從桌上到膝上到掌上。與IBM PC競爭的Apple Macintosh系列于1984年推出，Macintosh提供了友好的圖形界面，用戶可以用鼠標方便地操作。 下面的圖片展示的是這整個發(fā)展歷程的一小部分。 “現(xiàn)代計算機創(chuàng)始人”查爾斯·巴貝奇的分析儀復(fù)制品，該分析儀是用于公式演算的多功能計算機，不過這臺計算機在他有生之年始終未能問世。 美國人哈雷里斯利用卡片穿孔，開發(fā)了卡片制表系統(tǒng)，這一系統(tǒng)被認為是現(xiàn)代計算機的雛形。1911年，哈雷里斯將這項專利賣給了另外一家公司，13年后這家公司更名為國際商業(yè)機器公司，也就是現(xiàn)在的IBM。 ENIAC-世界上第一臺現(xiàn)代電子計算機（局部圖） 磁鼓數(shù)字微分分析器 IBM 1956年發(fā)行的光盤，圖中的最大的光盤是上世紀70年代早期制造的 Intel 4004 新一代計算機： 歷經(jīng)這所有的發(fā)展，才有了計算機現(xiàn)在的高性能與廣泛應(yīng)用。不過，雖然計算機芯片的集成度越來越高，元件越做越小，然而由于量子效應(yīng)的存在，集成電路技術(shù)現(xiàn)在正逼近其極限（0.2nm的工藝），科學(xué)家們看到傳統(tǒng)的計算機結(jié)構(gòu)必將有終結(jié)的一天，而且盡管計算機的運行速度與日俱增，但是有一些難題是計算機根本無法解決的，例如大數(shù)的因式分解，理論上只要一個數(shù)足夠大，這個難題夠目前最快的計算機忙幾億年的。事實上，計算機從真空管、晶體管、集成電路、超大規(guī)模集成電路一路走來，從計算方式的本質(zhì)來看是沒有發(fā)生任何改變的，我們一直沿著“電子”計算機的道路行走，而沒有在其它采用不同方式進行計算的計算機上有太多考慮，不過這種狀況已經(jīng)開始有所轉(zhuǎn)變，因為量子計算機、光子計算機、生物計算機已經(jīng)開始為我們所熟知。下面，我們就介紹一下這些“非電子”計算機，從中我們可以發(fā)現(xiàn)，計算機科學(xué)確實是現(xiàn)代先進科學(xué)技術(shù)理論的交匯點。 量子計算機 進入20世紀90年代，實驗技術(shù)和理論模型的進步為量子計算機的實現(xiàn)提供了可能。尤其值得一提的是1994年美國貝爾實驗室的Peter W. Shor證明運用量子計算機竟然能有效地進行大數(shù)的因式分解。這意味著以大數(shù)因式分解算法為依據(jù)的電子銀行、網(wǎng)絡(luò)等領(lǐng)域的RSA公開密鑰密碼體系在量子計算機面前不堪一擊。于是各國政府紛紛投入大量的資金和科研力量進行量子計算機的研究，如今這一領(lǐng)域已經(jīng)形成一門新型學(xué)科-量子信息學(xué)。 量子計算機具有特大威力的根本原因在于構(gòu)成量子計算機的基本單元-量子比特（q-bit），它具有奇妙的性質(zhì)，而這種性質(zhì)必須用量子力學(xué)來解釋，因此稱為量子特性。我們現(xiàn)在所使用的計算機采用二進制來進行數(shù)據(jù)的存儲和運算，在任何時刻一個存儲器位代表0或1。而量子比特是由量子態(tài)相干疊加而成，一個具有兩種狀態(tài)的系統(tǒng)可以看作是一個“二進制”的量子比特。在量子世界里物質(zhì)的狀態(tài)是捉摸不定的，如電子的位置可以在這里同時也可以在那里，原子的能級在某一時刻可以處于激發(fā)態(tài)，同時也可以處于基態(tài)。我們就采用有兩個能級的原子來做量子計算機的q-bit。規(guī)定原子在基態(tài)時記為 |0〉，在激發(fā)態(tài)時原子的狀態(tài)記為 |1〉，而原子具體處于哪個態(tài)我們可以通過辨別原子光譜得以了解。微觀世界的奇妙之處在于，原子除了保持上述兩種狀態(tài)之外，還可以處于兩種態(tài)的線性疊加，記為 |φ〉=a |1〉+ b |0〉 ，其中a，b分別代表原子處于兩種態(tài)的幾率幅。如此一來，這樣的一個q-bit不僅可以表示單獨的“0”和“1”（a=0時只有“0”態(tài)，b=0時只有“1”態(tài)），而且可以同時既表示“0”，又表示“1”（a，b都不為0時）。舉一個簡單的例子，假如有一個由三個比特構(gòu)成的存儲器，如果是由經(jīng)典比特構(gòu)成則能表示000，001，010，011，100，101，110，111這8 個二進制數(shù)，即0~7這8個十進制數(shù)，但同一時刻只能表示其中的一個數(shù)。若此存儲器是由量子比特構(gòu)成，如果三個比特都只處于 |0〉或 |1〉則能表示與經(jīng)典比特一樣的存儲器，但是量子比特還可以處于 |0〉與 |1〉的疊加態(tài)，假設(shè)三個q-bit每一個都是處于( |0〉+ |1〉) / (√2) 態(tài)，那么它們組成的量子存儲器將表示一個新的狀態(tài)，用量子力學(xué)的符號，可記做： |0〉|0〉|0〉+ |0〉|0〉|1〉+ |0〉|1〉|0〉+ |0〉|1〉|1〉+ |1〉|0〉|0〉+ |1〉|0〉|1〉+ |1〉|1〉|0〉+ |1〉|1〉|1〉 不難看出，上面這個公式表示8種狀態(tài)的疊加，既在某一時刻一個量子存儲器可以表示8個數(shù)。 接下來看看量子計算機如何對這些態(tài)進行運算。假設(shè)現(xiàn)在我們想求一個函數(shù)f(n)，(n＝0~7)的值，采用經(jīng)典計算的辦法至少需要下面的步驟： 存儲器清零→賦值運算→保存結(jié)果→再賦值運算→再保存結(jié)果…… 對每一個n都必須經(jīng)過存儲器的賦值和函數(shù)f(n)的運算等步驟，而且至少需要8個存儲器來保存結(jié)果。如果是用量子計算機來做這個題目則在原理上要簡潔的多，只需用一個量子存儲器，把各q-bit制備到( |0〉+ |1〉) / (√2)態(tài)上就一次性完成了對8個數(shù)的賦值，此時存儲器成為態(tài) |φ〉，然后對其進行相應(yīng)的幺正變換以完成函數(shù)f(n)的功能，變換后的存儲器內(nèi)就保存了所需的8個結(jié)果。這種能同時對多個態(tài)進行操縱，所謂“量子并行計算”的性質(zhì)正是量子計算機巨大威力的奧秘所在。 我們怎么把所需要的數(shù)據(jù)從8個或更多個結(jié)果中挑選出來呢？對具體的問題這就要要采用相應(yīng)的量子算法，例如Shor提出的大數(shù)因式分解算法。按照Shor算法，對一個1000位的數(shù)進行因式分解只需幾分之一秒，同樣的事情由目前最快的計算機來做，則需1025年！而Grover的搜索算法則被形象地稱為“從稻草堆中找出一根針”！盡管量子算法已經(jīng)很多了，但是到目前為止真正的量子計算機才只做到5個q-bit，只能做很簡單的驗證性實驗，但是我們有理由期待它的光明前景。 光子計算機 1990年初，美國貝爾實驗室制成世界上第一臺光子計算機。 現(xiàn)有的計算機是由電子來傳遞和處理信息。電場在導(dǎo)線中傳播的速度雖然比我們看到的任何運載工具運動的速度都快，但是，從發(fā)展高速率計算機來說，采用電子做輸運信息載體還不能滿足快的要求，提高計算機運算速度也明顯表現(xiàn)出能力有限了。而光子計算機以光子作為傳遞信息的載體，光互連代替導(dǎo)線互連，以光硬件代替電子硬件，以光 運算代替電運算，利用激光來傳送信號，并由光導(dǎo)纖維與各種光學(xué)元件等構(gòu)成集成光路，從而進行數(shù)據(jù)運算、傳輸和存儲。在光子計算機中，不同波長、頻率、偏振態(tài)及相位的光代表不同的數(shù)據(jù)，這遠勝于電子計算機中通過電子“0”、“1”狀態(tài)變化進行的二進制運算，可以對復(fù)雜度高、計算量大的任務(wù)實現(xiàn)快速的并行處理。光子計算機將使運算速度在目前基礎(chǔ)上呈指數(shù)上升。 由于光子比電子速度快，光子計算機的運行速度可高達一萬億次。它的存貯量是現(xiàn)代計算機的幾萬倍，還可以對語言、圖形和手勢進行識別與合成。 光子計算機與電子計算機相比，主要具有以下優(yōu)點： (1) 超高速的運算速度。光子計算機并行處理能力強，因而具有更高的運算速度。電子的傳播速度是593km/s，而光子的傳播速度卻達3×10 5km/s，對于電子計算機來說，電子是信息的載體，它只能通過一些相互絕緣的導(dǎo)線來傳導(dǎo)，即使在最佳的情況下，電子在固體中的運行速度也遠遠不如光速，盡管目前的電子計算機運算速度不斷提高，但它的能力極限還是有限的；此外，隨著裝配密度的不斷提高，會使導(dǎo)體之間的電磁作用不斷增強，散發(fā)的熱量也在逐漸增加，從而制約了電子計算機的運行速度；而光子計算機的運行速度要比電子計算機快得多，對使用環(huán)境條件的要求也比電子計算機低得多。 (2) 超大規(guī)模的信息存儲容量。與電子計算機相比，光子計算機具有超大規(guī)模的信息存儲容 量。光子計算機具有極為理想的光輻射源——激光器，光子的傳導(dǎo)是可以不需要導(dǎo)線的，而且即使在相交的情況下，它們之間也不會產(chǎn)生絲毫的相互影響。光子計算機無導(dǎo)線傳遞信息 的平行通道，其密度實際上是無限的，一枚五分硬幣大小的枚鏡，它的信息通過能力竟是全世界現(xiàn)有電話電纜通道的許多倍。 (3) 能量消耗小，散發(fā)熱量低，是一種節(jié)能型產(chǎn)品。光子計算機的驅(qū)動，只需要同類規(guī)格的電子計算機驅(qū)動能量的一小部分，這不僅降低了電能消耗，大大減少了機器散發(fā)的熱量，而且為光子計算機的微型化和便攜化研制，提供了便利的條件。科學(xué)家們正試驗將傳統(tǒng)的電子轉(zhuǎn)換器和光子結(jié)合起來，制造一種“雜交”的計算機，這種計算機既能更快地處理信息，又能克服巨型電子計算機運行時內(nèi)部過熱的難題。 目前，光子計算機的許多關(guān)鍵技術(shù)，如光存儲技術(shù)、光互連技術(shù)、光電子集成電路等都已經(jīng)獲得突破，最大幅度地提高光子計算機的運算能力是當前科研工作面臨的攻關(guān)課題。光子計算機的問世和進一步研制、完善，將為人類跨向更加美好的明天，提供無窮的力量。 生物計算機 生物計算機，即脫氧核糖核酸（DNA）分子計算機，主要由生物工程技術(shù)產(chǎn)生的蛋白質(zhì)分子組成的生物芯片構(gòu)成，通過控制DNA分子間的生化反應(yīng)來完成運算。運算過程就是蛋白質(zhì)分子與周圍物理化學(xué)介質(zhì)相互作用的過程。其轉(zhuǎn)換開關(guān)由酶來充當，而程序則在酶合成系統(tǒng)本身和蛋白質(zhì)的結(jié)構(gòu)中明顯表示出來。上世紀70年代，人們發(fā)現(xiàn)DNA處于不同狀態(tài)時可以代表信息的有或無。DNA分子中的遺傳密碼相當于存儲的數(shù)據(jù)，DNA分子間通過生化反應(yīng)，從一種基因代瑪轉(zhuǎn)變?yōu)榱硪?種基因代碼。反應(yīng)前的基因代碼相當于輸入數(shù)據(jù)，反應(yīng)后的基因代碼相當于輸出數(shù)據(jù)。只要能控制這一反應(yīng)過程，就可以制成DNA計算機。 生物計算機以蛋白質(zhì)分子構(gòu)成的生物芯片作為集成電路。蛋白質(zhì)分子比電子元件小很多，可以小到幾十億分之一米，而且生物芯片本身具有天然獨特的立體化結(jié)構(gòu)，其密度要比平面型的硅集成電路高五個數(shù)量級。生物計算機芯片本身還具有并行處理的功能，其運算速度要比當今最新一代的計算機快10萬倍，能量消耗僅相當于普通計算機的十億分之一。生物芯片一旦出現(xiàn)故障，可以進行自我修復(fù)，具有自愈能力。生物計算機具有生物活性，能夠和人體的組織有機地結(jié)合起來，尤其是能夠與大 腦和神經(jīng)系統(tǒng)相連。這樣，植入人體的生物計算機就可直接接受大腦的綜合指揮，成為人腦的輔助裝置或擴充部分，并能由人體細胞吸收營養(yǎng)補充能量，成為幫助人 類學(xué)習(xí)、思考、創(chuàng)造和發(fā)明的最理想的伙伴。 首先，它體積小，功效高。在一平方毫米的面積上，可容納幾億個電路，比目前的集成電路小得多，用它制成的計算機，已經(jīng)不像現(xiàn)在計算機的形狀了，可以隱藏在桌角、墻壁或地板等地方。 其次，當它的內(nèi)部芯片出現(xiàn)故障時，不需要人工修理，能自我修復(fù)，所以，生物計算機具有永久性和很高的可靠性。 再者，生物計算機的元件是由有機分子組成的生物化學(xué)元件，它們是利用化學(xué)反應(yīng)工作的，所以，只需要很少的能量就可以工作了，因此，不會像電子計算機那樣，工作一段時間后，機體會發(fā)熱，而它的電路間也沒有信號干擾。 長舒一口氣，講到這里我們的探索歷程也就接近尾聲了。從有限狀態(tài)機到圖靈機，從理論構(gòu)想到具體實現(xiàn)，我們一步一步實現(xiàn)了制造計算機的過程；通過回顧歷史，我們了解了整個計算機產(chǎn)業(yè)的發(fā)展過程。 理論需要思想上的創(chuàng)新，從而指引實踐的方向，實踐需要技術(shù)上的巨大支持，從而能夠切實完成理論構(gòu)想，也許這就是貫穿計算機科學(xué)發(fā)展史中的兩大主題吧。計算機科學(xué)的發(fā)展是永無止境的，計算機科學(xué)的應(yīng)用同樣如此，怎樣能夠讓計算機更好地造福人類，這當中的責(zé)任扛在我們每個人信息學(xué)科人的肩頭。的確，我們?nèi)沃囟肋h，但我也相信，這會是一條光明的道路。 |
|
|
