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