可計(jì)算性理論

1、1引言可計(jì)算理論建立于二十世紀(jì)三十年代?？捎?jì)算理論的研究對(duì)象有三個(gè)：(1)判定問題； (2 )可計(jì)算函數(shù)；(3 )計(jì)算復(fù)雜性。判定問題主要是判定方程是否有解；可計(jì)算函數(shù) 主要討論一個(gè)函數(shù)是否可計(jì)算，建立了原始遞歸函數(shù)、圖靈機(jī)等許多數(shù)學(xué)模型判定一個(gè) 函數(shù)是否屬于可計(jì)算函數(shù)；計(jì)算復(fù)雜性主要討論的問題是P =?NP?？捎?jì)算理論的計(jì)算模 型主要包括：(1) Turing機(jī)；(2 )遞歸函數(shù)；(3 )入演算；(4) POST系統(tǒng)； (5)正則算法。可計(jì)算理論是理論計(jì)算機(jī)科學(xué)，屬于計(jì)算機(jī)科學(xué)的基礎(chǔ)研究領(lǐng)域，可 計(jì)算理論是計(jì)算機(jī)軟件工程、系統(tǒng)結(jié)構(gòu)、并行運(yùn)算、圖像處理、人工智能、網(wǎng)絡(luò)的數(shù)學(xué) 理論基礎(chǔ)和工具.可

2、計(jì)算性理論是從三十年代初期開始哥德爾、丘吉、圖林和 波斯特等 人為了解決數(shù)學(xué)基礎(chǔ)方面的問題，(具體說.來是為了通過藪學(xué)方法來研究公理系統(tǒng)的 性質(zhì))，而發(fā)展起來的。(其中波斯特的工作則是在二十年代前期已經(jīng)作出的，但到了 四十年代才公開發(fā)表。)電子計(jì)算機(jī)產(chǎn)生后，可計(jì)算性理論的有些成果被應(yīng)用于計(jì)算 技術(shù)。(近十年來發(fā)展起來的可行計(jì)算理論則是與計(jì)算技術(shù)直接有關(guān)并作為這一技術(shù)的 數(shù)學(xué)理論而發(fā)展的。)2歷史變遷可計(jì)算理論是關(guān)于計(jì)算機(jī)械本身的數(shù)學(xué)理論.二十世紀(jì)前，計(jì)算機(jī)械總是“算計(jì)”別的 對(duì)象，很少“算計(jì)”自己。二十世紀(jì)30年代，為了要解決一個(gè)基礎(chǔ)問題，即是否存在 不可判定問題，數(shù)理邏輯學(xué)家提出了幾種不同的

3、(后來證明是彼此等價(jià)的)關(guān)于算法的 定義，從而建立了可計(jì)算性理論。德國數(shù)學(xué)家希爾伯特(Hilbert 1862-1943)認(rèn)為科學(xué)在每個(gè)時(shí)代都有它自己的問題，而 這些問題的解決對(duì)于科學(xué)發(fā)展具有深遠(yuǎn)意義。他指出：“只要一門科學(xué)分支能提出大量的 問題，它就充滿著生命力，而問題缺乏則預(yù)示著獨(dú)立發(fā)展的衰亡和終結(jié)?！痹?900年 國際數(shù)學(xué)家代表大會(huì)上，希爾伯特發(fā)表了題為數(shù)學(xué)問題的著名講演，他根據(jù)十九世 紀(jì)數(shù)學(xué)研究的成果和發(fā)展趨勢，提出了 23個(gè)最重要的數(shù)學(xué)問題。在這些問題中，有四個(gè) 問題是某類問題是否可計(jì)算。它們分別是：(1)只根據(jù)合同公理證明等底等高的兩個(gè)四 面體有相等之體積是不可能的，即存在兩個(gè)等高

4、等底的四面體，它們不可能分解為有限 個(gè)小四面體，使這兩組四面體彼此全等。(2)能否通過有限步驟來判定不定方程是否存 在有理整數(shù)解？求出一個(gè)整數(shù)系數(shù)方程的整數(shù)根，稱為丟番圖(約210-290,古希臘數(shù) 學(xué)家)方程可解。1950年前后，美國數(shù)學(xué)家戴維斯(Davis)、普特南(Putnan)、羅 賓遜(Robinson)等取得關(guān)鍵性突破。1970年，巴克爾(Baker)、費(fèi)羅斯(Philos) 對(duì)含兩個(gè)未知數(shù)的方程取得肯定結(jié)論。1970年。蘇聯(lián)數(shù)學(xué)家馬蒂塞維奇最終證明:在一 般情況答案是否定的。(3) 般七次代數(shù)方程以二變量連續(xù)函數(shù)之組合求解的不可能 性。七次方程x7+ax3+bx2+cx+1=0的

5、根依賴于3個(gè)參數(shù)a、b、c;x=x (a, b, c)。這一 函數(shù)能否用兩變量函數(shù)表示出來?此問題已接近解決。1957年，蘇聯(lián)數(shù)學(xué)家阿諾爾德 (Arnold)證明了任一在0, 1上連續(xù)的實(shí)函數(shù)f (x1, x2, x3)可寫成形式Ehi (Ei (x1, x2) , x3) (i=19),這里hi和Ei為連續(xù)實(shí)函數(shù)。柯爾莫哥洛夫證明f (x1, x2, x3)可寫成形式Ehi (Ei1 (x1) +Ei2 (x2) +Ei3 (x3) ) (i=1 7)這里 hi 和 Ei為連續(xù)實(shí)函數(shù)，Eij的選取可與f完全無關(guān)。1964年，維土斯金(Vituskin)推廣 到連續(xù)可微情形，對(duì)解析函數(shù)情形則未

6、解決。(4)實(shí)系數(shù)有理函數(shù)f (x1,，xn)對(duì) 任意數(shù)組(x1,，xn)都恒大于或等于0,確定f是否都能寫成有理函數(shù)的平方和?特 別是第二個(gè)問題，盡管得出了否定的結(jié)果，卻產(chǎn)生了一系列有價(jià)值的副產(chǎn)品，其中不少 和計(jì)算機(jī)科學(xué)有密切聯(lián)系。通過對(duì)這些問題的思考和證明，道致二十年對(duì)計(jì)算模型的研 究?？捎?jì)算性可以認(rèn)為對(duì)于某個(gè)特定的問題，如果存在一個(gè)程序，對(duì)于給定的輸入，這個(gè)程 序都能在有限步內(nèi)給出輸出，這個(gè)問題就是可計(jì)算的。從二十世紀(jì)30年代起，數(shù)理邏輯 學(xué)家就提出了幾種計(jì)算模型，試圖建立可計(jì)算性的數(shù)學(xué)模型。最早是由哥德爾 （Kurt.Godel 1906-1978）提出的是“遞歸函數(shù)”，就是現(xiàn)在的“原

7、始遞歸函數(shù)”，雖然 其定義簡單，但當(dāng)時(shí)人們所能想象得到的可計(jì)算函數(shù)都是原始遞歸函數(shù)，所以，人們猜 測原始遞歸函數(shù)就是可計(jì)算函數(shù)。不久就發(fā)現(xiàn)了一個(gè)用多重遞歸定義的函數(shù)不是原始遞 歸函數(shù)。于是，數(shù)理邏輯學(xué)家又在原始遞歸函數(shù)的定義中加了一個(gè)“極小”算子，由此 得到一個(gè)廣義遞歸函數(shù)。30年代中期，A.M.圖靈和E.L.波斯特彼此獨(dú)立地提出了理想計(jì) 算機(jī)的概念，將問題的算法可解性描述為在具有嚴(yán)格定義的理想計(jì)算機(jī)上的可解性。與 此同時(shí)，其他幾種計(jì)算模型也被提出。在圖靈之前，美國邏輯學(xué)家丘奇（A.Church）提 出了 “入演算”的概念，隨后邏輯學(xué)家波斯特（E.L.Post）提出的“POST演算”和馬爾 可

8、夫（A.Mapkob）提出的“正則算法”，都是關(guān)于算法的不同表達(dá)。30年代發(fā)展起來的 算法理論，對(duì)在40年代后期出現(xiàn)的存儲(chǔ)程序型計(jì)算機(jī)的設(shè)計(jì)思想是有影響的。圖靈提出 的理想計(jì)算機(jī)（稱為圖靈機(jī)）中的一種通用機(jī)就是存儲(chǔ)程序型的。圖靈工作的重要意義 在于他指出了一個(gè)原理：圖靈機(jī)是一種非常強(qiáng)有力的計(jì)算工具，一切可能的機(jī)械式計(jì)算 過程都可以由圖靈機(jī)實(shí)現(xiàn)。計(jì)算復(fù)雜性的研究始于50年代末60年代初，當(dāng)時(shí)在美國有兩個(gè)研究中心，一個(gè)是通用 電氣公司設(shè)立在紐約州克內(nèi)克塔迪的研究實(shí)驗(yàn)室，研究人員J. Hartmanis 和 R.Stearns 于1964年在普林斯頓舉行的第五屆開關(guān)電路理論和邏輯設(shè)計(jì)學(xué)術(shù)年會(huì)上發(fā)表了

9、文“Computational complexity of recursivese quences （遞歸序列的計(jì)算復(fù)雜性）， 論文中首次使用了計(jì)算復(fù)雜性這一術(shù)語，從此開辟了計(jì)算機(jī)科學(xué)的一個(gè)新領(lǐng)域。另一個(gè) 中心是麻省理工學(xué)院MIT,布盧姆研究了遞歸函數(shù)復(fù)雜性的機(jī)器獨(dú)立證明。關(guān)于算法的 復(fù)雜性的研究，這一領(lǐng)域的名稱曾有爭論，一般認(rèn)為，各類具體算法的復(fù)雜性的研究稱 作算法分析，而一般算法復(fù)雜性的研究稱作計(jì)算復(fù)雜性理論。計(jì)算復(fù)雜性理論原是可計(jì) 算理論的一支，是以各種可計(jì)算函數(shù)（即遞歸函數(shù)）的計(jì)算復(fù)雜性（在早期稱作“計(jì)算 難度”）為其研究對(duì)象的。可計(jì)算性分為理論可計(jì)算性和實(shí)際可計(jì)算性兩種。作為可計(jì) 算

10、性理論一支的計(jì)算復(fù)雜性理論，是以前者的復(fù)雜程度為其研究對(duì)象的;而作為計(jì)算機(jī)科 學(xué)一個(gè)領(lǐng)域的復(fù)雜性理論，則是以后者的復(fù)雜程度為其研究對(duì)象的。3內(nèi)容可計(jì)算理論的研究對(duì)象有三個(gè)：（1）判定問題；（2）可計(jì)算函數(shù)；（3）計(jì)算復(fù)雜性。判 定問題主要是判定方程是否有解;可計(jì)算函數(shù)主要討論一個(gè)函數(shù)是否可計(jì)算，建立了原始 遞歸函數(shù)、圖靈機(jī)等許多數(shù)學(xué)模型判定一個(gè)函數(shù)是否屬于可計(jì)算函數(shù);計(jì)算復(fù)雜性主要討 論的問題是P=?NP。討論的對(duì)象是難解問題是否存在時(shí)間和空間復(fù)雜度是多項(xiàng)式的有效 算法存在。對(duì)于一個(gè)判定問題，如果能夠編出一個(gè)程序，以域中任意元素作為輸入，當(dāng) 相應(yīng)的個(gè)別問題的解答是肯定的時(shí)候，執(zhí)行將終止并輸出“

11、是”；否則執(zhí)行不終止，就 稱該判定問題為半可判定的。可判定的問題總是半可判定的。集合是遞歸可枚舉集的充 分必要條件為對(duì)應(yīng)的判定問題是半可判定的。圖靈在1936年證明，圖靈機(jī)的停機(jī)問題 是不可判定的，即不存在一個(gè)圖靈機(jī)能夠判定任意圖靈機(jī)對(duì)于任意輸入是否停機(jī)。圖靈 機(jī)的停機(jī)問題是很重要的，由它可以推出計(jì)算機(jī)科學(xué)、數(shù)學(xué)、邏輯學(xué)中的許多問題是不 可判定的。計(jì)算復(fù)雜性理論這一分支的基本問題是要弄清楚實(shí)際可計(jì)算函數(shù)類的結(jié)構(gòu)和 一些性質(zhì)。實(shí)際可計(jì)算性是一個(gè)直觀的概念。如何對(duì)這一概念進(jìn)行精確的描述，是一個(gè) 并不容易的問題。60年代中期以來，有關(guān)的研究工作者一般是以計(jì)算時(shí)間多項(xiàng)式有界 的函數(shù)作為實(shí)際可計(jì)算的函數(shù)

12、。這實(shí)際上是一個(gè)論題，而不是一個(gè)可以在數(shù)學(xué)中加以證 明或否證的命題。有人指出，在有關(guān)的多項(xiàng)式次數(shù)較高時(shí)，很難說是實(shí)際可計(jì)算的。 可計(jì)算理論的計(jì)算模型主要包括：（1） Turing機(jī)；（2）遞歸函數(shù)；（3）入演算；（4） POST系統(tǒng)；（5）正則算法。第一個(gè)模型是程序設(shè)計(jì)語言S,該程序語言定義了 1）變 量；2）標(biāo)號(hào);3）語句;4）指令;5）程序;6）狀態(tài);7）快相;8）后繼;9）計(jì)算。設(shè) f （x, x,，x）是一個(gè)部分函數(shù)，如果存在程序S計(jì)算f,則稱f是部分可計(jì)算 函數(shù)。1從就一個(gè)函數(shù)是否是可計(jì)算的，只需要判斷是否可以構(gòu)造對(duì)應(yīng)的程序S即可。 原始遞歸函數(shù)一章詳細(xì)討論了可計(jì)算函數(shù)，可計(jì)算函數(shù)經(jīng)

13、過原始遞歸運(yùn)算還是可計(jì)算函 數(shù)。給出了通用程序的概念，任意程序和輸入x, x,（y=# （）,存在通用程序 以x, x,，x和y作為輸入，計(jì)算結(jié)果恰好等于程序的計(jì)算結(jié)果。“參數(shù)定 理”，“遞歸定理”提供了判斷一個(gè)函數(shù)是否可計(jì)算的方法，從基本的可計(jì)算函數(shù)推道 出其他函數(shù)是否可計(jì)算，而不需要構(gòu)造程序證明其可計(jì)算。另一個(gè)計(jì)算模型是語言hn, 該模型為字符串運(yùn)算設(shè)計(jì)的。設(shè)字母表A中有n個(gè)符號(hào)，如果A*上的m元部分函數(shù)能用 程序計(jì)算，則這個(gè)函數(shù)是可計(jì)算的。Post-Turing語言也是面向字符串運(yùn)算的程序設(shè)計(jì) 語言，要處理的字符串存在一條帶上。Post-Turing程序Z計(jì)算的A*上m元部分函數(shù) 定義為

14、對(duì)任意給定的輸入x, x,，x eA*,從初始帶格局開始，如果計(jì)算最終停 止，則部分函數(shù)等于計(jì)算停止時(shí)從帶的內(nèi)容中刪除不屬于A*的符號(hào)后得到的字符串;如 果計(jì)算不停止，則部分函數(shù)無定義。圖靈機(jī)u由六部分組成：（1）有窮狀態(tài)集，（2）字 母表，（3）動(dòng)作函數(shù)，（4）輸入字母表，（5）空白符B, （6）初始態(tài)q1。上述計(jì)算模型 等價(jià)性的證明，主要采用將一種模型用另一種模型表示的方法證明?？捎?jì)算理論中，計(jì) 算模型很多，如有窮自動(dòng)機(jī)，正則算法在本質(zhì)上都與圖靈機(jī)相似。Church-Turing論題 指出:通常說的能行可計(jì)算函數(shù)等同于部分遞歸函數(shù)，也等同于Turing機(jī)計(jì)算的部分函 數(shù);也就是說，Turi

15、ng機(jī)可計(jì)算性與遞歸性是等價(jià)的。因此，把遞歸函數(shù)、Turing機(jī) （部分）可計(jì)算函數(shù)及其等價(jià)的概念作為可計(jì)算函數(shù)的嚴(yán)格定義?？捎?jì)算理論的研究方法是通過建立數(shù)學(xué)模型，將復(fù)雜的計(jì)算抽象化，從而試圖解決各種 數(shù)學(xué)基本問題，目前已經(jīng)建立了一些數(shù)學(xué)模型，也建立新的數(shù)據(jù)模型，與現(xiàn)有的數(shù)據(jù)模 型進(jìn)行對(duì)比，證明數(shù)學(xué)的基本問題。具體的方法是:首先建立一個(gè)計(jì)算模型，然后在該模 型的基礎(chǔ)上證明一個(gè)函數(shù)是否可計(jì)算。如程序設(shè)計(jì)語言入，定義了一些規(guī)則與操作，在 證明一個(gè)函數(shù)可計(jì)算時(shí)，將這個(gè)函數(shù)用這種模型定義的操作和規(guī)則描述。使用遞歸函數(shù) 證明一個(gè)函數(shù)是否可計(jì)算，可由已知的可計(jì)算函數(shù)入手，按照一些定理和規(guī)則推道證明 該函數(shù)

16、是可計(jì)算的。由此可知，可計(jì)算理論的研究方法是通過建立一個(gè)數(shù)學(xué)模型，給出 可計(jì)算的嚴(yán)格定義，然后區(qū)分一個(gè)函數(shù)是否是可計(jì)算的，它排除了一個(gè)函數(shù)實(shí)際可計(jì)算, 而在一個(gè)數(shù)學(xué)模型下是不可計(jì)算的可能性。因?yàn)镃hurch-Turing論題指出了現(xiàn)有的各種 計(jì)算模型是等價(jià)的，一個(gè)函數(shù)在一個(gè)模型下是可計(jì)算的，則在另一個(gè)模型下也是可計(jì)算 的?？梢哉f可計(jì)算性理論研究是建立在Church-Turing論題的基礎(chǔ)上，尋找合適的數(shù)學(xué) 模型證明一個(gè)函數(shù)的可計(jì)算性。形式語言自動(dòng)機(jī)是研究形式語言和自動(dòng)機(jī)的基本理論及其關(guān)系。主要內(nèi)容包括語言與計(jì) 算、有限自動(dòng)機(jī)、正則表達(dá)式、前后文無關(guān)文法、下推自動(dòng)機(jī)和圖靈機(jī)等。自動(dòng)機(jī)理論 和形式

17、語言理論是50年代發(fā)展起來的。前者的歷史還可以上溯到30年代，因?yàn)閳D靈機(jī) 就是一類自動(dòng)機(jī)（無限自動(dòng)機(jī)）。50年代以來一些學(xué)者開始考慮與現(xiàn)實(shí)的計(jì)算機(jī)更相似 的理想計(jì)算機(jī)，J.諾伊曼在50年代初提出了有自繁殖功能的計(jì)算機(jī)的概念。王浩在50 年代中期提出了一種圖靈機(jī)的變種，這是一種比原來的圖靈機(jī)更接近現(xiàn)實(shí)機(jī)器的機(jī)器。 他還提出一種存儲(chǔ)帶上的內(nèi)容不能清除的機(jī)器，并證明這種機(jī)器是與圖靈機(jī)等價(jià)的。60年代前期，又有人提出具有隨機(jī)存取存儲(chǔ)器的計(jì)算機(jī)（簡稱RAM）以及多帶圖靈機(jī) 等。形式語言理論道源于數(shù)理語言學(xué)中的喬姆斯基理論。在這種理論中，形式語言分 為四種:0型語言;1型語言;2型語言;3型語言。相應(yīng)地存

18、在著0型、1型、2 型、3型四種形式文法。1型語言又名上下文有關(guān)語言，2型語言又名上下文無關(guān)語言， 3型語言又名正則語言。其中2型語言最受人注意。60年代中期，還發(fā)現(xiàn)了這四類語言 與四類自動(dòng)機(jī)之間的對(duì)應(yīng)關(guān)系。另一個(gè)帶根本性的問題是:確定性機(jī)器與非確定性機(jī)器的解題能力的比較問題。人們早已 知道，確定性圖靈機(jī)與非確定性圖靈機(jī)的解題能力是相等的。因?yàn)榉谴_定性機(jī)器雖比確 定性機(jī)器效率高，而如果計(jì)算時(shí)間沒有限制，則確定性機(jī)器總可以用窮舉的方法來模擬 非確定性機(jī)器。因此，二者的解題能力是一樣的。但在計(jì)算時(shí)間多項(xiàng)式有界時(shí)，二者的 解題能力是否相等，這就是有名的P=？ NP問題。4應(yīng)用（1）程序理論（程序邏輯、程序正確性驗(yàn)證、形式開發(fā)方法等）（2）計(jì)算理論（算法設(shè)計(jì)與分析、復(fù)雜性理論、可計(jì)算性理論等）（3）語言理論（形式語言理論、自動(dòng)機(jī)理論、形式語義學(xué)、計(jì)算語言學(xué)等）（4）人工智能（知識(shí)工程、機(jī)器學(xué)習(xí)、模式識(shí)別、機(jī)器人等）5總結(jié)可計(jì)算性理論的基本思想、概念和方法，被廣泛應(yīng)用于計(jì)算科學(xué)的各個(gè)領(lǐng)域。建立數(shù)學(xué) 模型的方法在計(jì)算科學(xué)中被廣泛采用。遞歸的思想被用于程序設(shè)計(jì)，產(chǎn)生了遞歸過程的 數(shù)據(jù)結(jié)構(gòu)，也影響了計(jì)算機(jī)體系結(jié)構(gòu)。入演算被用于研究程序設(shè)計(jì)語言的語義，例如， 表處理語言就以入演算為理論基礎(chǔ)。遞歸函數(shù)論的建立對(duì)于數(shù)學(xué)基礎(chǔ)的研究具有十分重要的作用。