精選答案在60年代的中國,如果一個大學(xué)生不懂工農(nóng)業(yè)常識,例如混淆了韭菜麥子,可能會受到譏笑。本來,聞道有先后,樹業(yè)有專工。要求一個領(lǐng)域的人理解另一個領(lǐng)域的知識是有些過分。在今天,如果一個計(jì)算機(jī)科學(xué)的碩士或博士不知道什么是不可判定問題,什么是停機(jī)問題,為什么停機(jī)問題不可解,什么是NP=?P問題,也有可能會受到譏笑。因?yàn)檫@些問題對于計(jì)算機(jī)科學(xué)而言,太基本、太重要了,它們都屬于一門稱為可計(jì)算理論的學(xué)科。是計(jì)算機(jī)科學(xué)研究人員應(yīng)具備的修養(yǎng)型知識。 可計(jì)算理論是關(guān)于計(jì)算機(jī)械本身的數(shù)學(xué)理論。20世紀(jì)前,計(jì)算機(jī)械總是”算計(jì)”別的對象,很少”算計(jì)”自己。20世紀(jì) 30年代,為了要解決一個基礎(chǔ)問題,即是否有存在不可判定問題,數(shù)理邏輯 學(xué)家提出了幾種不同的(后來證明是彼此等價的)關(guān)于算法的定義,從而建立了可計(jì)算性理論。 科學(xué)家令計(jì)算機(jī)械 自己”算計(jì)”自己,奇跡出現(xiàn)了。圖靈用對角線方法,把圖靈機(jī)自己編碼,攪進(jìn)其自己的計(jì)算對象中,證明了停機(jī)問題不可解。在一定程度上說明了計(jì)算機(jī)(程序)的能力有限性。
30年 代前期,K.哥德爾和S.C.克林尼等人創(chuàng)立了遞歸函數(shù)論, 將數(shù)論函數(shù)的算法可計(jì)算性描述為遞歸性。30年代中期, A.M.圖靈和E.L.波斯特彼此獨(dú)立地提出了理想計(jì)算機(jī)的 概念,將問題的算法可解性描述為在具有嚴(yán)格定義的理想計(jì)算機(jī)上的可解性。30年代發(fā)展起來的算法理論,對 在40年代后期出現(xiàn)的存儲程序型計(jì)算機(jī)的設(shè)計(jì)思想是有影響的。圖靈提出的理想計(jì)算機(jī)(稱為圖靈機(jī))中的一 種通用機(jī)就是存儲程序型的。
可計(jì)算理論主要內(nèi)容有:自動機(jī)論與形式語言理論;程序理論(包括程序正確性證明、程 序驗(yàn)證等);形式語義學(xué);算法分析和計(jì)算復(fù)雜性理 論。自動機(jī)理論和形式語言理論是50年 代發(fā)展起來的。前者的歷史還可以上溯到30年代,因?yàn)閳D靈機(jī)就是一類自動機(jī)(無限自動機(jī))。50年代以來一些 學(xué)者開始考慮與現(xiàn)實(shí)的計(jì)算機(jī)更相似的理想計(jì)算機(jī),J. 諾伊曼在50年代初提出了有自繁殖功能的計(jì)算機(jī)的概念。
王浩在50年代中期提出了一種圖靈機(jī)的變種,這是一種 比原來的圖靈機(jī)更接近現(xiàn)實(shí)機(jī)器的機(jī)器。他還提出一種 存儲帶上的內(nèi)容不能清除的機(jī)器,并證明這種機(jī)器是與圖靈機(jī)等價的。
60年代前期,又有人提出具有隨機(jī)存取 存儲器的計(jì)算機(jī)(簡稱RAM)以及多帶圖靈機(jī)等。 形式語言理論 導(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)了這四類 語言與四類自動機(jī)之間的對應(yīng)關(guān)系(見表形式語言與自 動機(jī)的關(guān)系) 在上表中,左邊所列的語言恰好是右邊與之對應(yīng)的自動機(jī)所能識別的語言(見形式語言理論)。 程序設(shè)計(jì)理論 包括程序正確性證明和程序驗(yàn)證, 它的一些基本概念和方法是40年代后期諾伊曼和圖靈等 人提出的。諾伊曼等在一篇論文中提出借助于證明來驗(yàn)證程序正確性的方法。
J.T.施瓦茲和 M.戴維斯70年代后期提出了一種他們稱之為”正確程序 技術(shù)”的軟件技術(shù)。這種方法是先選定成千種基本程序模塊,并借助已知的各種驗(yàn)證方法(包括程序正確性證 明)來保證這些基本程序的正確性。然后再提出一組能 保持正確性的程序組合規(guī)則。這樣,就可以通過不斷的 組合,生成各種各樣的程序。
有人指出,程序正確性證明技術(shù)所發(fā)展出來的”循 環(huán)不變式”,即一個程序中的某一循環(huán)的入口或出口點(diǎn) 上所附的謂詞,有些文獻(xiàn)中稱作”歸納斷言”,可以用來供程序研究用。也就是說,不像過去那樣,對一個給 定的程序找出其若干個循環(huán)不變式,然后借助這些不變 式來證明這個程序的正確性;而是在編制這個程序之前, 根據(jù)對這一程序的要求,找出若干個循環(huán)不變式,然后根據(jù)這些不變式來生成這個程序。 自動程序設(shè)計(jì)的概念也是從40年代提出的。
1969年又有人獨(dú)立地提出了這一想法。 程序語言的形式語法的研究,從50年代中期起有了較大的發(fā)展。而形式語義的研究自60年代以來雖有不少 研究工作者從事這方面的工作,提出幾種不同的語義理 論,主要是操作語義學(xué)、指稱語義學(xué)或稱數(shù)學(xué)語義學(xué)、 公理語義學(xué)和代數(shù)語義學(xué),但仍沒有一種公認(rèn)在軟件技術(shù)中夠用的形式語義學(xué),因而需要提出一種更適于用到 實(shí)際計(jì)算中的新的語義學(xué)。 在程序正確性證明和形式語義學(xué)中應(yīng)用的程序邏輯, 是60年代末發(fā)展起來的。
這是謂詞邏輯的一種擴(kuò)充。原來的謂詞邏輯中是沒有時間概念的,所考慮的推理關(guān)系 是在同一時間里的關(guān)系。程序是一種過程,一個程序的 輸入謂詞與輸出謂詞之間的邏輯關(guān)系就不是同一時間里 的關(guān)系。因此,在有關(guān)程序性質(zhì)的推理中,原來的謂詞邏輯不夠用,需要有一種新的邏輯。 60年代末,E.恩格勒等人創(chuàng)立了算法邏輯。C.A.R. 霍爾也創(chuàng)立了一種程序邏輯。這種邏輯是在原來的邏輯上增加一個程序算子而得到的。
算法分析和計(jì)算復(fù)雜性理論 關(guān)于算法的復(fù)雜性的 研究。關(guān)于這一領(lǐng)域的名稱曾有爭論。一般認(rèn)為,各類具體算法的復(fù)雜性的研究稱作算法分析,而一般算法復(fù) 雜性的研究稱作計(jì)算復(fù)雜性理論。計(jì)算復(fù)雜性理論原是 可計(jì)算理論的一支,是以各種可計(jì)算函數(shù)(即遞歸函數(shù)) 的計(jì)算復(fù)雜性(在早期稱作”計(jì)算難度”)為其研究對象的。可計(jì)算性分為理論可計(jì)算性和實(shí)際可計(jì)算性兩種。 作為可計(jì)算性理論一支的計(jì)算復(fù)雜性理論,是以前者的 復(fù)雜程度為其研究對象的;而作為計(jì)算機(jī)科學(xué)一個領(lǐng)域 的復(fù)雜性理論,則是以后者的復(fù)雜程度為其研究對象的。
這一分支的基本問題是要弄清楚實(shí)際可計(jì)算函數(shù)類的結(jié)構(gòu)和一些性質(zhì)。實(shí)際可計(jì)算性是一個直觀的概念。 如何對這一概念進(jìn)行精確的描述,是一個并不容易的問 題。60年代中期以來,有關(guān)的研究工作者一般是以計(jì)算時間多項(xiàng)式有界的函數(shù)作為實(shí)際可計(jì)算的函數(shù)。這實(shí)際 上是一個論題,而不是一個可以在數(shù)學(xué)中加以證明或否 證的命題。有人指出,在有關(guān)的多項(xiàng)式次數(shù)較高時,很難說是實(shí)際可計(jì)算的。
另一個帶根本性的問題是:確定性機(jī)器與非確定性機(jī)器的解題能力的比較問題。人們早已知道,確定性圖 靈機(jī)與非確定性圖靈機(jī)的解題能力是相等的。因?yàn)榉谴_ 定性機(jī)器雖比確定性機(jī)器效率高,而如果計(jì)算時間沒有 限制,則確定性機(jī)器總可以用窮舉的方法來模擬非確定性機(jī)器。因此,二者的解題能力是一樣的。但在計(jì)算時 間多項(xiàng)式有界時,二者的解題能力是否相等,這就是有 名的P=? NP問題。 關(guān)于計(jì)算和算法(包括程序)的研究,對串行計(jì)算的性質(zhì)研究較多,而對并行計(jì)算性質(zhì)的研究則還很不夠 (特別是對異步的并行計(jì)算更是如此)。因此,關(guān)于并 行計(jì)算的研究很可能將成為計(jì)算機(jī)理論的研究重點(diǎn)。
對于一個判定問題,如果能夠編出一個程序,以域 中任意元素作為輸入,當(dāng)相應(yīng)的個別問題的解答是肯定 的時候, 的執(zhí)行將終止并輸出”是”,否則 的執(zhí)行不 終止,就稱該判定問題為半可判定的?？膳卸ǖ膯栴}總是半可判定的。集合是遞歸可枚舉集的充分必要條件為 對應(yīng)的判定問題是半可判定的。 圖靈在1936年證明,圖靈機(jī)的停機(jī)問題是不可判定 的,即不存在一個圖靈機(jī)能夠判定任意圖靈機(jī)對于任意輸入是否停機(jī)。圖靈機(jī)的停機(jī)問題是半可判定的。圖靈 機(jī)的停機(jī)問題是很重要的,由它可以推出計(jì)算機(jī)科學(xué)、 數(shù)學(xué)、邏輯學(xué)中的許多問題是不可判定的。