在60年代的中國,如果一個大學(xué)生不懂工農(nóng)業(yè)常識,例如混淆了韭菜麥子,可能會受到譏笑。

本來,聞道有先后,樹業(yè)有專工。要求一個領(lǐng)域的人理解另一個領(lǐng)域的知識是有些過分。在今天,如果一個計算機科學(xué)的碩士或博士不知道什么是不可判定問題,什么是停機問題,為什么停機問題不可解,什么是NP= P問題,也有可能會受到譏笑。因為這些問題對于計算機科學(xué)而言,太基本、太重要了,它們都屬于一門稱為可計算理論的學(xué)科。是計算機科學(xué)研究人員應(yīng)具備的修養(yǎng)型知識?？捎嬎憷碚撌顷P(guān)于計算機械本身的數(shù)學(xué)理論。20世紀(jì)前,計算機械總是”算計”別的對象,很少”算計”自己。20世紀(jì) 30年代,為了要解決一個基礎(chǔ)問題,即是否有存在不可判定問題,數(shù)理邏輯 學(xué)家提出了幾種不同的(后來證明是彼此等價的)關(guān)于算法的定義,從而建立了可計算性理論。科學(xué)家令計算機械 自己”算計”自己,奇跡出現(xiàn)了。圖靈用對角線方法,把圖靈機自己編碼,攪進(jìn)其自己的計算對象中,證明了停機問題不可解。在一定程度上說明了計算機(程序)的能力有限性。 30年 代前期,K.哥德爾和S.C.克林尼等人創(chuàng)立了遞歸函數(shù)論, 將數(shù)論函數(shù)的算法可計算性描述為遞歸性。30年代中期, A.M.圖靈和E.L.波斯特彼此獨立地提出了理想計算機的 概念,將問題的算法可解性描述為在具有嚴(yán)格定義的理想計算機上的可解性。30年代發(fā)展起來的算法理論,對 在40年代后期出現(xiàn)的存儲程序型計算機的設(shè)計思想是有影響的。圖靈提出的理想計算機(稱為圖靈機)中的一 種通用機就是存儲程序型的。 可計算理論主要內(nèi)容有:自動機論與形式語言理論;程序理論(包括程序正確性證明、程 序驗證等);形式語義學(xué);算法分析和計算復(fù)雜性理 論。自動機理論和形式語言理論是50年 代發(fā)展起來的。前者的歷史還可以上溯到30年代,因為圖靈機就是一類自動機(無限自動機)。50年代以來一些 學(xué)者開始考慮與現(xiàn)實的計算機更相似的理想計算機,J. 諾伊曼在50年代初提出了有自繁殖功能的計算機的概念。 王浩在50年代中期提出了一種圖靈機的變種,這是一種 比原來的圖靈機更接近現(xiàn)實機器的機器。他還提出一種 存儲帶上的內(nèi)容不能清除的機器,并證明這種機器是與圖靈機等價的。 60年代前期,又有人提出具有隨機存取 存儲器的計算機(簡稱RAM)以及多帶圖靈機等。 形式語言理論 導(dǎo)源于數(shù)理語言學(xué)中的喬姆斯基理 論。在這種理論中,形式語言分為四種：

①0型語言;②1 型語言;③2型語言;④3型語言。相應(yīng)地存在著0型、1型、 2 型、3型四種形式文法。1型語言又名上下文有關(guān)語言, 2型語言又名上下文無關(guān)語言,3型語言又名正則語言。其中2型語言最受人注意。60年代中期,還發(fā)現(xiàn)了這四類 語言與四類自動機之間的對應(yīng)關(guān)系(見表形式語言與自 動機的關(guān)系) 在上表中,左邊所列的語言恰好是右邊與之對應(yīng)的自動機所能識別的語言(見形式語言理論)。 程序設(shè)計理論 包括程序正確性證明和程序驗證, 它的一些基本概念和方法是40年代后期諾伊曼和圖靈等 人提出的。諾伊曼等在一篇論文中提出借助于證明來驗證程序正確性的方法。 J.T.施瓦茲和 M.戴維斯70年代后期提出了一種他們稱之為”正確程序 技術(shù)”的軟件技術(shù)。這種方法是先選定成千種基本程序模塊,并借助已知的各種驗證方法(包括程序正確性證 明)來保證這些基本程序的正確性。然后再提出一組能 保持正確性的程序組合規(guī)則。這樣,就可以通過不斷的 組合,生成各種各樣的程序。 有人指出,程序正確性證明技術(shù)所發(fā)展出來的”循 環(huán)不變式”,即一個程序中的某一循環(huán)的入口或出口點 上所附的謂詞,有些文獻(xiàn)中稱作”歸納斷言”,可以用來供程序研究用。也就是說,不像過去那樣,對一個給 定的程序找出其若干個循環(huán)不變式,然后借助這些不變 式來證明這個程序的正確性;而是在編制這個程序之前, 根據(jù)對這一程序的要求,找出若干個循環(huán)不變式,然后根據(jù)這些不變式來生成這個程序。 自動程序設(shè)計的概念也是從40年代提出的。 1969年又有人獨立地提出了這一想法。 程序語言的形式語法的研究,從50年代中期起有了較大的發(fā)展。而形式語義的研究自60年代以來雖有不少 研究工作者從事這方面的工作,提出幾種不同的語義理 論,主要是操作語義學(xué)、指稱語義學(xué)或稱數(shù)學(xué)語義學(xué)、 公理語義學(xué)和代數(shù)語義學(xué),但仍沒有一種公認(rèn)在軟件技術(shù)中夠用的形式語義學(xué),因而需要提出一種更適于用到 實際計算中的新的語義學(xué)。 在程序正確性證明和形式語義學(xué)中應(yīng)用的程序邏輯, 是60年代末發(fā)展起來的。 這是謂詞邏輯的一種擴充。原來的謂詞邏輯中是沒有時間概念的,所考慮的推理關(guān)系 是在同一時間里的關(guān)系。程序是一種過程,一個程序的 輸入謂詞與輸出謂詞之間的邏輯關(guān)系就不是同一時間里 的關(guān)系。因此,在有關(guān)程序性質(zhì)的推理中,原來的謂詞邏輯不夠用,需要有一種新的邏輯。 60年代末,E.恩格勒等人創(chuàng)立了算法邏輯。C.A.R. 霍爾也創(chuàng)立了一種程序邏輯。這種邏輯是在原來的邏輯上增加一個程序算子而得到的。 算法分析和計算復(fù)雜性理論 關(guān)于算法的復(fù)雜性的 研究。關(guān)于這一領(lǐng)域的名稱曾有爭論。一般認(rèn)為,各類具體算法的復(fù)雜性的研究稱作算法分析,而一般算法復(fù) 雜性的研究稱作計算復(fù)雜性理論。計算復(fù)雜性理論原是 可計算理論的一支,是以各種可計算函數(shù)(即遞歸函數(shù)) 的計算復(fù)雜性(在早期稱作”計算難度”)為其研究對象的?？捎嬎阈苑譃槔碚摽捎嬎阈院蛯嶋H可計算性兩種。 作為可計算性理論一支的計算復(fù)雜性理論,是以前者的 復(fù)雜程度為其研究對象的;而作為計算機科學(xué)一個領(lǐng)域 的復(fù)雜性理論,則是以后者的復(fù)雜程度為其研究對象的。 這一分支的基本問題是要弄清楚實際可計算函數(shù)類的結(jié)構(gòu)和一些性質(zhì)。實際可計算性是一個直觀的概念。 如何對這一概念進(jìn)行精確的描述,是一個并不容易的問 題。60年代中期以來,有關(guān)的研究工作者一般是以計算時間多項式有界的函數(shù)作為實際可計算的函數(shù)。這實際 上是一個論題,而不是一個可以在數(shù)學(xué)中加以證明或否 證的命題。有人指出,在有關(guān)的多項式次數(shù)較高時,很難說是實際可計算的。 另一個帶根本性的問題是:確定性機器與非確定性機器的解題能力的比較問題。人們早已知道,確定性圖 靈機與非確定性圖靈機的解題能力是相等的。因為非確 定性機器雖比確定性機器效率高,而如果計算時間沒有 限制,則確定性機器總可以用窮舉的方法來模擬非確定性機器。因此,二者的解題能力是一樣的。但在計算時 間多項式有界時,二者的解題能力是否相等,這就是有 名的P=NP問題。 關(guān)于計算和算法(包括程序)的研究,對串行計算的性質(zhì)研究較多,而對并行計算性質(zhì)的研究則還很不夠 (特別是對異步的并行計算更是如此)。因此,關(guān)于并 行計算的研究很可能將成為計算機理論的研究重點。對于一個判定問題,如果能夠編出一個程序,以域 中任意元素作為輸入,當(dāng)相應(yīng)的個別問題的解答是肯定 的時候, 的執(zhí)行將終止并輸出”是”,否則 的執(zhí)行不 終止,就稱該判定問題為半可判定的。可判定的問題總是半可判定的。集合是遞歸可枚舉集的充分必要條件為 對應(yīng)的判定問題是半可判定的。 圖靈在1936年證明,圖靈機的停機問題是不可判定 的,即不存在一個圖靈機能夠判定任意圖靈機對于任意輸入是否停機。圖靈機的停機問題是半可判定的。圖靈 機的停機問題是很重要的,由它可以推出計算機科學(xué)、 數(shù)學(xué)、邏輯學(xué)中的許多問題是不可判定的。