計(jì)算復(fù)雜性課件

可計(jì)算性與計(jì)算復(fù)雜性李占山1000個圖片的拼圖，如果沒有考慮把握技巧，那么對于每個圖片有正反面、左右和對錯3種組合8種狀態(tài)，這樣我們把所有圖片拼在一起需要考慮81000種狀態(tài)（步驟）情況拼圖，這是一個驚人的數(shù)字，用計(jì)算機(jī)求解在我們的有生之年是看不到結(jié)果的。難道這個問題就沒有結(jié)果了嗎？非也，我們?nèi)瞬皇窃谕孢@種游戲嗎？我只用了一兩天甚至更短的時間就成功了，哪有你老師說的那么復(fù)雜？那樣不是很郁悶嗎？我拼圖成功很是快樂，為什么？拼圖游戲從拼圖游戲到解現(xiàn)實(shí)生活中的實(shí)際問題的解決---同學(xué)，游戲不是這樣玩的！我們的課程可以使你從可郁悶性與郁悶復(fù)雜性到可快樂性與快樂復(fù)雜性的。怎么辦？分類分解問題唄！首先把圖片都翻到相同一面，最壞時要做1000次，如果圖片字母標(biāo)號有20種，然后把它們根據(jù)字母標(biāo)號分成20子類，每一子類再根據(jù)字母正反分為2個子子類，同樣拼圖時相鄰的圖片是交錯排列的，按照這樣的分類方法進(jìn)行拼圖看看最壞時我們需要多少個步驟？玩游戲是一門學(xué)問呦！1000+1000+20250個狀態(tài)（步驟），這些狀態(tài)步驟完全在你的有限時間掌控之中，因此能夠在一兩天甚至更短時間內(nèi)完成拼圖任務(wù)。嗷！原來是這樣的呀！看來學(xué)好這門課會使我們從可郁悶性與郁悶復(fù)雜性到可快樂性與快樂復(fù)雜性的！??！為了學(xué)好這門課程我們有必要介紹這門課程的本質(zhì)與定位以及一些重要?dú)v史人物，他們是？？？？？

計(jì)算學(xué)科（ComputingScience）即我們所熟悉的計(jì)算機(jī)科學(xué)與技術(shù)(ComputerScienceandTechnology)。計(jì)算學(xué)科是對描述和變換信息的算法過程，包括其理論、分析、設(shè)計(jì)、效率分析、實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究的一門學(xué)科。它涉及計(jì)算過程的分析如可計(jì)算性、算法，研究有關(guān)計(jì)算機(jī)的各種現(xiàn)象、揭示其規(guī)律與本質(zhì)如計(jì)算機(jī)的設(shè)計(jì)和使用、可計(jì)算性硬件和軟件的實(shí)際實(shí)現(xiàn)問題。

計(jì)算學(xué)科的基本問題是能行與效率的問題,即它的核心問題是“能行”問題(Practicability)：1)什么是（實(shí)際）可計(jì)算的？什么是（實(shí)際）不可計(jì)算的？2)如何保證計(jì)算的自動性、有效性及正確性？

1985年春，ACM（美國計(jì)算機(jī)協(xié)會）和IEEE－CS（國際電子電氣工程師學(xué)會計(jì)算機(jī)分會）組成聯(lián)合攻關(guān)小組，開始了對“計(jì)算作為一門學(xué)科”的存在性證明。1989年1月，該小組提交了《計(jì)算作為一門學(xué)科》（Computingasadiscipline）的報(bào)告。第一次給出了計(jì)算學(xué)科一個透徹的定義，回答了計(jì)算學(xué)科中長期以來一直爭論的一些問題，完成了計(jì)算學(xué)科的“存在性”證明，還提出了未來計(jì)算科學(xué)教育必須解決的二個重大問題――整個學(xué)科核心課程詳細(xì)設(shè)計(jì)及整個學(xué)科綜述性導(dǎo)引課程的構(gòu)建。1991年，在這報(bào)告的基礎(chǔ)上提交了關(guān)于計(jì)算學(xué)科教學(xué)計(jì)劃CC1991（ComputingCurricula1991）。2001年12月，提交了最終的CC2001報(bào)告。

《計(jì)算作為一門學(xué)科》報(bào)告及CC1991、CC2001一起解決了三個重要問題：第一個重大問題（計(jì)算作為一門學(xué)科的存在性證明）的解決。對學(xué)科本身的發(fā)展至關(guān)重要。如果在眾多分支領(lǐng)域都取得了重大成果并已得到廣泛應(yīng)用的“計(jì)算”，連作為一門學(xué)科的地位都不清楚，那么它的發(fā)展勢必要受到很大的限制。

第二個重大問題（整個學(xué)科核心課程詳細(xì)設(shè)計(jì)）的解決，將為高校制定計(jì)算機(jī)教學(xué)計(jì)劃奠定基礎(chǔ)。確定一個公認(rèn)的本科生應(yīng)該掌握的核心內(nèi)容，將避免教學(xué)計(jì)劃設(shè)計(jì)中的隨意性，從而為我們科學(xué)地制定教學(xué)計(jì)劃奠定基礎(chǔ)。

第三個重大問題（整個學(xué)科綜述性導(dǎo)引課程的構(gòu)建）的解決，將使人們對整個學(xué)科的認(rèn)知科學(xué)化、系統(tǒng)化和邏輯化。如果人們對計(jì)算學(xué)科的認(rèn)知能建立在公理化的基礎(chǔ)之上，則該學(xué)科可被認(rèn)為是嚴(yán)謹(jǐn)?shù)目茖W(xué)、成熟的學(xué)科，從而有助于它的發(fā)展，并將由此而得到人們的尊重。

攻關(guān)小組的結(jié)論是：計(jì)算學(xué)科所研究的根本問題是能行問題（什么能被（有效地）自動進(jìn)行）。計(jì)算學(xué)科的基本原理已納入理論、抽象和設(shè)計(jì)這3個具有科學(xué)技術(shù)方法意義的過程中。學(xué)科的各分支領(lǐng)域正是通過這3個過程來實(shí)現(xiàn)它們各自的目標(biāo)。而這3個過程要解決的都是計(jì)算過程中的“能行性”和“有效性”問題。

與數(shù)學(xué)相比，電子技術(shù)的重要性對計(jì)算科學(xué)而言不如數(shù)學(xué)，因?yàn)閿?shù)學(xué)提供了計(jì)算科學(xué)最重要的學(xué)科思想和方法論基礎(chǔ)，而電子技術(shù)只提供了電子計(jì)算機(jī)的實(shí)現(xiàn)技術(shù)，它僅僅只是對計(jì)算科學(xué)許多思想和方法的一種當(dāng)前最現(xiàn)實(shí)、最有效的實(shí)現(xiàn)技術(shù)手段而已。當(dāng)科學(xué)技術(shù)的手段提到發(fā)展時，完全有可能有某一項(xiàng)新技術(shù)歸結(jié)為有效地取代電子技術(shù)（如光技術(shù)、生物技術(shù)等等），但計(jì)算科學(xué)的數(shù)學(xué)基礎(chǔ)可能變化不大。

從事計(jì)算科學(xué)的人都知道，計(jì)算科學(xué)中不僅許多理論是用數(shù)學(xué)描述的，而且許多技術(shù)也是用數(shù)學(xué)描述的。大多數(shù)計(jì)算科學(xué)理論不僅僅是對研究對象變化規(guī)律的陳述，而且由于能行性這一本質(zhì)的核心問題和特點(diǎn)的作用，理論描述中常通過方法折射出技術(shù)的思想和步驟，而從理論通過方法跨越到技術(shù)則完全取決于理論的深刻認(rèn)識和理解。一個人如果看懂了以形式化方法描述的技術(shù)文獻(xiàn)，自然明白技術(shù)上應(yīng)該怎樣去做。

至于計(jì)算機(jī)技術(shù)專業(yè)的學(xué)生為何要學(xué)習(xí)數(shù)學(xué)這個問題的答案，了解了上面所講的計(jì)算學(xué)科與數(shù)學(xué)的關(guān)系后就不言而喻了：計(jì)算機(jī)科學(xué)植根于數(shù)學(xué)，但又不同于數(shù)學(xué)，從而可計(jì)算理論的基礎(chǔ)知識就需要掌握，因?yàn)檫@能夠提高我們本身的邏輯推理能力、抽象思維能力和形式化思維能力，從而今后在學(xué)習(xí)任何一門計(jì)算機(jī)科學(xué)的專業(yè)主干課程時，都不會遇上任何思維理解上的困難。

當(dāng)前計(jì)算機(jī)科學(xué)在發(fā)展過程中面對著如下兩個問題：

一是信息革命要求計(jì)算機(jī)科學(xué)要將計(jì)算機(jī)的應(yīng)用擴(kuò)大到包含所有的問題領(lǐng)域和深入到每個問題領(lǐng)域的深處而越來越細(xì)致越來越復(fù)雜；二是一旦讓計(jì)算機(jī)去解決問題，那么計(jì)算機(jī)應(yīng)自動地在有限和有效的時間內(nèi)得出解。前者指出計(jì)算機(jī)科學(xué)的任務(wù)就是要用計(jì)算機(jī)的硬件、外設(shè)和軟件構(gòu)成一個系統(tǒng)，使得許多不同領(lǐng)域的問題都能在這樣的計(jì)算機(jī)系統(tǒng)中得到解決。為了完成這個任務(wù)，就必須用一種符號語言構(gòu)成一個包括了不同領(lǐng)域的通用模型。

計(jì)算理論就是指出構(gòu)成一個包括了不同領(lǐng)域的通用模型的思維方法，并且告訴我們怎樣用不同的語言（符號語言、圖形語言、邏輯語言等）從最簡單的對象（集合）出發(fā)表示通用模型。后者指出計(jì)算機(jī)科學(xué)必須了解讓計(jì)算機(jī)去解決問題在通用模型中的結(jié)構(gòu)，由于要求在有限和有效時間內(nèi)計(jì)算機(jī)自動完成，那么問題求解的方法必然是構(gòu)造性的。

(2)從計(jì)算機(jī)科學(xué)學(xué)生能力角度培養(yǎng)的看計(jì)算理論的作用。計(jì)算機(jī)出現(xiàn)的五十多年間，人們追求著和出現(xiàn)了許多計(jì)算機(jī)信息革命帶來的信息產(chǎn)品，但是信息產(chǎn)品受工業(yè)產(chǎn)品的觀念上的影響，使得計(jì)算機(jī)科學(xué)的學(xué)科發(fā)展帶來了偏差，使得整個學(xué)科的發(fā)展都是“軟件跟著硬件走”。我們不能將自己的學(xué)生培養(yǎng)成計(jì)算機(jī)系統(tǒng)的奴隸，而應(yīng)該培養(yǎng)成計(jì)算機(jī)系統(tǒng)的主人，我們的學(xué)生不能給計(jì)算機(jī)系統(tǒng)所塑造，將他們變成計(jì)算機(jī)，而是教育學(xué)生怎樣地塑造計(jì)算機(jī)系統(tǒng)。

在計(jì)算機(jī)科學(xué)知識掌握的過程中應(yīng)是“硬件跟著軟件走，軟件跟著模型走，模型跟著學(xué)科實(shí)際應(yīng)用走；學(xué)科實(shí)際應(yīng)用跟著自然走”。而最主要的培養(yǎng)環(huán)節(jié)應(yīng)該是軟件跟著模型走，模型跟著學(xué)科實(shí)際應(yīng)用走。關(guān)于學(xué)生的培養(yǎng)目標(biāo)就是要培養(yǎng)自己的學(xué)生能夠根據(jù)實(shí)際應(yīng)用問題提出計(jì)算機(jī)應(yīng)用的模型，并用硬件和軟件資源去構(gòu)造計(jì)算機(jī)系統(tǒng)去完成模型中所提出來的工作。

首先，計(jì)算機(jī)系統(tǒng)要解決的問題并不是個別的問題，也并不是某個領(lǐng)域上的特殊問題，要解決某個領(lǐng)域的所有能用計(jì)算機(jī)進(jìn)行計(jì)算的問題，因此，關(guān)于計(jì)算機(jī)科學(xué)的思維方法必須是在足夠通用的層面上的思維方法。如果所掌握或所習(xí)慣的思維方法僅限制在是某些特殊的領(lǐng)域，那么，隨著計(jì)算機(jī)應(yīng)用的不斷擴(kuò)大和計(jì)算機(jī)信息革命的不斷擴(kuò)大，將會使得思維的方法帶有很大的局限性。當(dāng)然，最通用的層面是自然層面，然而，自然層面上的對象還不能為現(xiàn)代計(jì)算機(jī)(現(xiàn)代計(jì)算模型)所了解。因?yàn)?，我們選擇塑造計(jì)算機(jī)系統(tǒng)的層面既帶有最大的通用性，又能為現(xiàn)代計(jì)算機(jī)系統(tǒng)所了解的層面。在現(xiàn)代計(jì)算技術(shù)的支持下，這個層面就是符號處理層面。

其次，我們是要去塑造計(jì)算機(jī)系統(tǒng)，我們的所有思維都要立足于能“塑造”性，因此，思維的可構(gòu)造性，即在考慮構(gòu)成計(jì)算機(jī)系統(tǒng)的所有對象都必須能夠有某種方法在有限的時間內(nèi)構(gòu)造出來。因此塑造計(jì)算機(jī)系統(tǒng)的基本思維是構(gòu)造性思維。以上描述了計(jì)算理論的學(xué)科定位下面我們來看相關(guān)的歷史人物簡介計(jì)算理論的開拓者—圖靈阿蘭·圖靈，1912年6月23日出生于英國倫敦。其祖父曾獲得劍橋大學(xué)數(shù)學(xué)榮譽(yù)學(xué)位，但他父親的數(shù)學(xué)才能平平。因此，圖靈的家庭教育，對他以后在數(shù)學(xué)及計(jì)算機(jī)方面的成就并沒有多少幫助。

小時侯的圖靈生性活潑好動，很早就表現(xiàn)出對科學(xué)的探索精神。據(jù)他母親回憶，3歲時，小圖靈就進(jìn)行了他的首次實(shí)驗(yàn)，嘗試把一個玩具木頭人的小胳膊、小腿掰下來栽到花園里，等待長出更多的木頭人。到了8歲，他更開始嘗試寫一部科學(xué)著作，題目為《關(guān)于一種顯微鏡》。在這部很短的書中，天才兒童圖靈拼錯了很多單詞，句法也有些問題，但寫得還能讓人看懂，很像那么一回事兒。在書的開頭和結(jié)尾，他都用同一句話“首先你必須知道光是直的”作前后呼應(yīng)，但中間的內(nèi)容卻很短，短得破了科學(xué)著作的記錄。圖靈曾說:“我似乎總想從最普通的東西中弄出些名堂。”就連和小朋友們玩足球，他也能放棄當(dāng)前鋒進(jìn)球這樣出風(fēng)頭的事，只喜歡在場外巡邊，因?yàn)檫@樣能有機(jī)會去計(jì)算球飛出邊界的角度。他的老師認(rèn)為:“圖靈的頭腦思維可以像袋鼠一樣進(jìn)行跳躍?！眻D靈是個天才。他16歲就開始研究愛因斯坦的相對論。1931年，圖靈考入劍橋大學(xué)國王學(xué)院，開始他的數(shù)學(xué)生涯，研究量子力學(xué)、概率論和邏輯學(xué)。在校期間，圖靈還是現(xiàn)代語言哲學(xué)大師維特根斯坦班上最出色的學(xué)生。他對由劍橋大學(xué)的羅素和懷特海創(chuàng)立的數(shù)理邏輯很感興趣。數(shù)理邏輯的創(chuàng)建，主要是為了對付“悖論”。“悖論”(paradox)是人類思維中最狡猾的兩面派，最早起源于古希臘克里特島上有個叫愛皮梅尼特的“智者”，他說:“所有的克里特島人都說謊”。我們可以把它簡化為:“我說的這句話是假話”。這就出現(xiàn)一種兩面都無法自圓的怪圈:如果他沒有說謊，那他這句話是錯的，他是在說謊;如果他真的在說謊，那他說自己在說謊是對的，所以他又沒有說謊。羅素和懷特海把它從邏輯、集合論以及數(shù)論中驅(qū)逐出去，最后又想盡辦法歸入《數(shù)學(xué)原理》之中。

圖靈一上大學(xué)，就迷上了《數(shù)學(xué)原理》。在1931年，著名的“哥德爾定理”出現(xiàn)后(該定理認(rèn)為沒有一種公理系統(tǒng)可以導(dǎo)出數(shù)論中所有的真實(shí)命題，除非這種系統(tǒng)本身就有悖論)，天才的圖靈在數(shù)理邏輯大本營的劍橋大學(xué)提出一個設(shè)想:能否有這樣一臺機(jī)器，通過某種一般的機(jī)械步驟，能在原則上一個接一個地解決所有的數(shù)學(xué)問題。大學(xué)畢業(yè)后，圖靈去美國普林斯頓大學(xué)攻讀博士學(xué)位，還順手發(fā)明過一個解碼器。在那里，他遇見了馮·諾依曼，后者對他的論文擊節(jié)贊賞，并隨后由此提出了“存儲程序”概念。圖靈學(xué)成后又回到他的母校任教。在短短的時間里，圖靈就發(fā)表了幾篇很有份量的數(shù)學(xué)論文，為他贏得了很大的聲譽(yù)。

在劍橋，圖靈可稱得上是一個怪才，一舉一動常常出人意料。他是個單身漢和長跑運(yùn)動員。在他的同事和學(xué)生中間，這位衣著隨便、不打領(lǐng)帶的著名教授，不善言辭，有些木訥、害羞，常咬指甲，但他更多地以自己杰出的才智贏得了人們的敬意。圖靈每天騎自行車上班，因?yàn)榛歼^敏性鼻炎，一遇到花粉，就會鼻涕不止，大打噴嚏。于是，他就常常在上班途中戴防毒面具，招搖過市，這早已成為劍橋的一大奇觀。圖靈的自行車經(jīng)常半路掉鏈子，但他就是不肯去車鋪修理。每次騎車時，他總是嘴里念念有詞，在心里細(xì)細(xì)計(jì)算，這鏈條也怪，總是轉(zhuǎn)到一定的圈數(shù)就滑落了，而圖靈竟然能夠做到在鏈條下滑前一剎那停車，讓旁觀者佩服不已，以為圖靈在玩雜技。后來圖靈又居然在腳踏車旁裝了一個小巧的機(jī)械記數(shù)器，到圈數(shù)時就停，歇口氣換換腦子，再重新運(yùn)動起來。

1936年，圖靈向倫敦權(quán)威的數(shù)學(xué)雜志投了一篇論文，題為《論數(shù)字計(jì)算在決斷難題中的應(yīng)用》。在這篇開創(chuàng)性的論文中，圖靈給“可計(jì)算性”下了一個嚴(yán)格的數(shù)學(xué)定義，并提出著名的“圖靈機(jī)”(TuringMachine)的設(shè)想?！皥D靈機(jī)”不是一種具體的機(jī)器，而是一種思想模型，可制造一種十分簡單但運(yùn)算能力極強(qiáng)的計(jì)算機(jī)裝置，用來計(jì)算所有能想像得到的可計(jì)算函數(shù)。裝置由一個控制器和一根假設(shè)兩端無界的工作帶(起存儲器的作用)組成。工作帶被劃分為大小相同的方格，每一格上可書寫一個給定字母表上的符號。控制器可以在帶上左右移動，它帶有一個讀寫頭，可讀出控制器所訪問的格子上的符號，也能改寫或抹去這一符號，最后便會得出一個你期待的結(jié)果。外行人看了會墜入云里霧里，而內(nèi)行人則稱它是“闡明現(xiàn)代電腦原理的開山之作”，并冠以“理想計(jì)算機(jī)”的名稱。這篇論文在紙上談了一把兵，創(chuàng)造出一個“圖靈機(jī)”來。但現(xiàn)代通用電腦確實(shí)是用相應(yīng)的程序來完成任何設(shè)定好的任務(wù)。這一理論奠定了整個現(xiàn)代計(jì)算機(jī)的理論基礎(chǔ)?！皥D靈機(jī)”更在電腦史上與“馮·諾依曼機(jī)”齊名，被永遠(yuǎn)載入計(jì)算機(jī)的發(fā)展史中。1931年，年輕的法國數(shù)學(xué)家赫爾布蘭德（JacquesHerbrand，1908～1931）對遞歸函數(shù)進(jìn)行了研究，并給著名邏輯學(xué)家哥德爾（KurtG?del，1906～1978）寫信敘述了自己的研究結(jié)果。哥德爾當(dāng)時正處于自己一生中最重大的成果—哥德爾不完全性定理的研究時期，他沒有仔細(xì)看赫爾布蘭德的來信內(nèi)容，因此沒有立即對赫爾布蘭德的工作做出回應(yīng)。那一年的夏天，年僅23歲的赫爾布蘭德在攀登阿爾卑斯山時不幸遇難，他的工作因此被暫時埋沒了。

與赫爾布蘭德的研究差不多同時，1931年秋天，普林斯頓大學(xué)的美國邏輯學(xué)家丘奇（AlonzoChurch，1903～1995）也在積極從事邏輯及算法的研究，并且發(fā)展出了一種新的邏輯體系。丘奇在普林斯頓開了一門邏輯課，他讓自己的兩個學(xué)生克林（StephenKleene，1909～1994）與羅瑟（JohnRosser，1907～1989）對這一體系做細(xì)致的研究。兩個學(xué)生都是一流好手，他們的研究很快就有了結(jié)果，但這結(jié)果大大出乎丘奇的意料。他們發(fā)現(xiàn)丘奇的那套體系竟然是自相矛盾的！命運(yùn)似乎只有一個：放棄。幸運(yùn)的是，丘奇的那套體系中有一個組成部分是自洽的，因此可以保留下來，這部分叫做蘭姆達(dá)運(yùn)算（λ－calculus）。這種蘭姆達(dá)運(yùn)算可以用來定義函數(shù)，而所有用蘭姆達(dá)運(yùn)算定義的函數(shù)都是可以有效計(jì)算的。在對蘭姆達(dá)運(yùn)算做了研究之后，丘奇提出了一個大膽的猜測，他猜測所有可以有效計(jì)算的函數(shù)都可以用蘭姆達(dá)運(yùn)算來定義。于是克林開始進(jìn)行研究，結(jié)果克林和丘奇得到一類可計(jì)算的函數(shù)，他們稱之為A可定義函數(shù)。

1934年春天，哥德爾在普林斯頓大學(xué)做了一系列講演。丘奇向到普林斯頓大學(xué)訪問的哥德爾介紹了他的猜測，哥德爾卻不以為然。丘奇不服氣，請哥德爾給出一個他認(rèn)為合適的描述。一兩個月后，哥德爾就給出了一種完全不同的描述，這種描述的基礎(chǔ)正是3年前赫爾布蘭德在給他的信中敘述的結(jié)果。哥德爾對這一結(jié)果進(jìn)行了完善，這一結(jié)果被人們稱為赫爾布蘭德－哥德爾遞歸函數(shù)。與此同時，丘奇和克林在1936年分別發(fā)表論文，證明A可定義函數(shù)類正好就是一般遞歸函數(shù)類。有了這個有力的證據(jù)，丘奇于是公開發(fā)表他的"論點(diǎn)"。這樣，丘奇與哥德爾各自給出了一種體系，描述可以有效計(jì)算的函數(shù)。丘奇與克林很快證明，這兩種看上去完全不同的描述方式實(shí)際上是彼此等價的。

兩位著名邏輯學(xué)家的工作殊途同歸，大大增強(qiáng)了丘奇的信心。他相信人們已經(jīng)找到了可以有效計(jì)算的函數(shù)的普遍定義。但哥德爾及其他一些人對此卻仍然懷有疑慮。最終打消這種疑慮的是英國數(shù)學(xué)家圖靈（AlanTuring，1912～1954）。

1937年圖靈證明了用圖靈機(jī)可計(jì)算的函數(shù)類與可定義函數(shù)類是一致的，當(dāng)然，也就和一般遞歸函數(shù)類相重合。這樣一來，丘奇的論點(diǎn)與圖林的論點(diǎn)就是一回事。當(dāng)時許多人對于丘奇的論點(diǎn)表示懷疑，由于圖林的思想表述得如此清楚，從而消除了許多人的疑慮，哥德爾就是其中一位。從這時起大家對于丘奇-圖靈論點(diǎn)一般都抱支持的態(tài)度了。數(shù)理邏輯學(xué)家歌德爾

1947年美國數(shù)學(xué)家波斯特（EmilPost，1897～1954）找到了第一個邏輯領(lǐng)域以外的不可判定命題。波斯特是一位有著深刻洞察力的邏輯學(xué)家，7歲時隨父母從波蘭移民到美國，是美國邏輯學(xué)的先驅(qū)之一。他10年前就得到了與哥德爾不完全性定理相似的結(jié)果，由于想對結(jié)果作更全面的分析而沒有及時發(fā)表。他也是最早意識到希爾伯特第十問題可能會有否定答案的數(shù)學(xué)家之一。1944年，他在一篇文章中明確提出希爾伯特第十問題“期待一個不可解性證明”。當(dāng)時波斯特在紐約市立大學(xué)任教，他的這一觀點(diǎn)深深打動了一位學(xué)生，使后者走上了畢生鉆研希爾伯特第十問題的征途。這位學(xué)生名叫戴維斯（MartinDavis，1928～），是解決希爾伯特第十問題的關(guān)鍵人物。圖靈獎與計(jì)算理論圖靈獎是由ACM于1966年首次設(shè)立的獎項(xiàng),它是為了紀(jì)念“計(jì)算機(jī)科學(xué)之父”圖靈而設(shè)立的,專門獎勵那些在計(jì)算機(jī)科學(xué)研究中做出創(chuàng)造性貢獻(xiàn)、推動了計(jì)算機(jī)科學(xué)技術(shù)發(fā)展的杰出科學(xué)家。雖然沒有明確規(guī)定，但從實(shí)際執(zhí)行過程來看，圖靈獎偏重于在計(jì)算機(jī)科學(xué)理論和軟件方面作出貢獻(xiàn)的科學(xué)家。獎金金額不算太高，設(shè)獎初期為2萬美元，1989年增至2萬5千美元，獎金通常由計(jì)算機(jī)界的一些大企業(yè)提供（通過與ACM簽定協(xié)議）。由于圖靈獎對獲獎?wù)咭髽O高，評獎程序又極嚴(yán)，一般每年只獎勵一名計(jì)算機(jī)科學(xué)家，只有極少數(shù)年度有兩名合作者或在同一方向作出貢獻(xiàn)的科學(xué)家共享此獎。因此它是計(jì)算機(jī)界最負(fù)盛名、最崇高的一個獎項(xiàng)，有‘計(jì)算機(jī)界的諾貝爾獎“之稱。從1966年到2000年共有41位科學(xué)家獲此殊榮，在這些學(xué)者中從事計(jì)算復(fù)雜性理論研究的有11人，幾乎占四分之一。他們是？？？？1976年圖靈獎獲得者拉賓和斯科特1976年的圖靈獎由當(dāng)時在以色列希伯萊大學(xué)的教授拉賓和英國牛津大學(xué)的數(shù)理邏輯教授斯科特共同獲得。他們是師兄弟，兩人在50年代中期先后師從于著名的數(shù)理邏輯與計(jì)算機(jī)科學(xué)家丘奇（他對可計(jì)算性理論做出了實(shí)質(zhì)性貢獻(xiàn)，如判定問題的解、演算的發(fā)明，90歲還在發(fā)表論文，圖靈也是他的學(xué)生），并在有限自動機(jī)及其判定問題的研究中進(jìn)行合作，奠定了非確定性有限自動機(jī)的理論基礎(chǔ)，之后，他們的研究方向不盡相同，拉賓側(cè)重于計(jì)算理論，而斯科特側(cè)重于邏輯學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用，在各自的領(lǐng)域中又分別獲得重大成果，做出了創(chuàng)造性貢獻(xiàn)。計(jì)算機(jī)科學(xué)家、數(shù)理邏輯學(xué)家丘奇拉賓是1931年出生于德國的布雷斯勞的猶太人，1948年以色列建國以后成為以色列公民，20世紀(jì)50年代拉賓博士畢業(yè)于普林斯頓大學(xué)，使拉賓成名的是IBM研究中心1957年向他和師弟斯科特提供的允許他們做自己感興趣的工作。于是他們二人聯(lián)手研究圖靈機(jī)----有限狀態(tài)自動機(jī)。他們定義了一種新的、“非確定性”行為的有限狀態(tài)自動機(jī)(NDFSA)，這種機(jī)器在讀去到一定的輸入后，有一個可以進(jìn)入的可能的新的狀態(tài)的‘菜單’可供選擇，這樣對給定的輸入計(jì)算便不單一了，每個選擇代表一種可能的計(jì)算。拉賓和斯科特將圖靈的有限狀態(tài)自動機(jī)從確定性一種擴(kuò)展到非確定的另一種形式，極大地推動了有限狀態(tài)自動機(jī)理論的發(fā)展，雖然非確定性有限狀態(tài)自動機(jī)的能力并不比確定性的有任何增加（拉賓和斯科特已經(jīng)證明他們等價），但是它可以簡化機(jī)器描述和加快解題速度。后來的時間證明，非確定性有限狀態(tài)自動機(jī)在機(jī)器翻譯、文獻(xiàn)檢索和字處理程序等應(yīng)用中都起到了重要作用。他們的研究結(jié)果發(fā)表于2年后的1959年IBM雜志上，題目為“有限自動機(jī)及其判定問題”。1958年夏天拉賓又來到IBM，當(dāng)時“人工智能之父”麥卡錫（1971年圖靈獎獲得者）正在那里研究往巴克斯（1977年圖靈獎獲得者）發(fā)明的FORTRAN語言中加入表處理功能，他給拉賓出了一道難題：設(shè)計(jì)一種口令即使口令被敵方竊取，也無法進(jìn)入系統(tǒng)。拉賓經(jīng)過艱苦探索，終于利用馮諾伊曼開發(fā)的一個單向函數(shù)解決了這個問題。正是這個問題促使拉賓進(jìn)一步研究計(jì)算任務(wù)的最小計(jì)算量這一一般性問題，也就是計(jì)算的固有難度問題，從而使拉賓成為最早研究計(jì)算復(fù)雜性問題的先驅(qū)之一。他的研究結(jié)果“計(jì)算速度和遞歸集合的分類”與“函數(shù)的計(jì)算難度和遞歸集合的偏序”分別于1959和1960年在耶路撒冷發(fā)表。論文中雖然沒有用“計(jì)算復(fù)雜性‘這個名詞而用了”計(jì)算速度“和”計(jì)算難度“，但學(xué)術(shù)界公認(rèn)這兩篇論文是研究計(jì)算復(fù)雜性的最早、最權(quán)威的論文中的兩篇，對1964年正式提出”計(jì)算復(fù)雜性“這一術(shù)語的哈特馬尼斯和斯特恩斯（這2人是1993年圖靈獎獲得者，后面介紹）以及計(jì)算復(fù)雜性理論的另一奠基人布盧姆（1995年圖靈獎獲得者，后面介紹）都產(chǎn)生了深刻影響。其中布盧姆正是聽到了拉賓的有關(guān)演講才開始研究計(jì)算復(fù)雜性并完成博士論文的。斯科特比拉賓小一歲，1932年出生于加利福尼亞，在加州大學(xué)伯克利分校獲得學(xué)士學(xué)位后，進(jìn)入普林斯頓大學(xué)研究生院深造，與拉賓一起師從于阿隆索丘齊。丘齊對學(xué)生要求很嚴(yán)，布置的問題也很難，斯科特開始時難以適應(yīng)，精神很緊張，經(jīng)常夜里作惡夢。但經(jīng)過努力，終于可以從容應(yīng)付。1957年他與師兄拉賓一起完成了對圖靈機(jī)的研究，提出了非確定性有限狀態(tài)自動機(jī)的理論以后，在1958年取得博士學(xué)位。之后他先后在芝加哥大學(xué)、加州大學(xué)伯克利分校、斯坦福大學(xué)、普林斯頓大學(xué)和牛津大學(xué)等國際知名高等學(xué)府任教。1981年被卡內(nèi)基梅隆大學(xué)聘為計(jì)算機(jī)科學(xué)、數(shù)理邏輯和哲學(xué)教授。斯科特的主要興趣和研究方向是邏輯學(xué)，包括集合論、模型論、自動機(jī)理論、非經(jīng)典邏輯中的模態(tài)邏輯和直覺主義邏輯。斯科特的最大貢獻(xiàn)是他與斯特雷奇合作，20世紀(jì)60年代提出了程序設(shè)計(jì)語言的“標(biāo)志語義模型”為標(biāo)志語義學(xué)奠定了堅(jiān)實(shí)的基礎(chǔ)。1978年圖靈獎獲得者弗洛伊德歷屆圖靈獎得主基本上都有高學(xué)歷、高學(xué)位，絕大多數(shù)都有博士學(xué)位，但事情總有例外，1978年圖靈獎得主、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授弗洛伊德就是一位“自學(xué)成才的計(jì)算機(jī)科學(xué)家”。說他自學(xué)成才并不是說他沒有接受過高等教育，他是芝加哥大學(xué)的畢業(yè)生，但學(xué)的是文學(xué)，1953年獲得文學(xué)學(xué)位，由于當(dāng)時經(jīng)濟(jì)不景氣，成為西屋電氣公司一名計(jì)算機(jī)操作員，他不懂計(jì)算機(jī)，但是個有心人，受過良好高等教育很快對計(jì)算機(jī)產(chǎn)生了興趣開始學(xué)習(xí)相關(guān)知識，1956年成為程序員，1965年被卡內(nèi)基-梅隆大學(xué)聘為副教授，1970年聘為教授。大家現(xiàn)在熟知的優(yōu)先文法，界限上下文文法都是他20世紀(jì)60年代提出的，優(yōu)先文法解決了自底向上的語法分析中的首要問題：如何找到”句柄“，也就是當(dāng)前需要?dú)w約的符號串。1964年與威廉姆斯共同發(fā)明了堆排序算法HEAPSORT，這是與英國學(xué)者霍爾（1980年圖靈獎獲得者）發(fā)明的QUICKSORT齊名的高效排序算法之一。1982年圖靈獎獲得者庫克NP完全性理論的奠基人庫克1939年出生于紐約州的布法羅。1957年中學(xué)畢業(yè)后，到密歇根大學(xué)學(xué)科學(xué)工程，一年級時選擇了一門新開設(shè)的課程—程序設(shè)計(jì)，作為作業(yè)，他編了一個ALGOL程序驗(yàn)證歌德巴赫猜想，由此他對計(jì)算機(jī)科學(xué)發(fā)生了興趣。1961年庫克獲得學(xué)士學(xué)位以后，轉(zhuǎn)入哈佛大學(xué)研究生院深造，第二年就取得了理科碩士學(xué)位，他接著攻讀了數(shù)學(xué)博士學(xué)位，原先打算研究代數(shù)學(xué)。然而這時他遇到了一些教師，對他產(chǎn)生了很大的影響，改變了他的興趣和方向。首先是哈佛研究生院對新興學(xué)科十分重視，雖然當(dāng)時計(jì)算復(fù)雜性理論這一學(xué)科還處于萌芽和初創(chuàng)時期，他們就邀請了這方面的一些先驅(qū)與奠基人，包括拉賓、哈特馬尼斯和斯特恩斯，由于對拉賓等人講學(xué)或做報(bào)告內(nèi)容產(chǎn)生興趣，庫克他們的研究和探索的問題發(fā)生了極大的興趣，從而把自己的研究定在這個方向。博士畢業(yè)后當(dāng)時美籍華人數(shù)學(xué)家王浩提出的圖靈機(jī)的一種變形叫B機(jī)器也引起了他的興趣。王浩指出，甚至在無限的時間里，要想證明確定謂詞演算中的某個公式是否可滿足，在計(jì)算上都是不可能的，因此王浩從復(fù)雜性角度去研究，他的工作給了庫克極大的啟發(fā)，庫克從比較單純和簡單的命題演算公式的自動證明入手研究計(jì)算復(fù)雜性，果然成功了，１９７１年發(fā)表了“定理證明過程的復(fù)雜性”。在這篇論文中庫克首次明確提出了NP完全問題，并奠定了NP完全性理論的基礎(chǔ)。以后我們將講授這些內(nèi)容。1985年圖靈獎獲得者卡普發(fā)明“分枝限界法”的三棲學(xué)者卡普是美國加州大學(xué)計(jì)算機(jī)、數(shù)學(xué)和工業(yè)工程三個系的教授，他被授予圖靈獎也是因?yàn)樵谒惴ㄔO(shè)計(jì)與分析、計(jì)算復(fù)雜性理論等方面的創(chuàng)造性貢獻(xiàn)，生于１９３５年的卡普興趣廣泛聰明過人，在哈佛大學(xué)時文理兼修，1955年先獲得文學(xué)學(xué)士學(xué)位，第2年又獲得理科碩士學(xué)位，之后進(jìn)入哈佛計(jì)算機(jī)實(shí)驗(yàn)室攻讀博士學(xué)位，1959年獲得數(shù)學(xué)博士學(xué)位后進(jìn)入IBM。

當(dāng)時，正是計(jì)算機(jī)科學(xué)的創(chuàng)立時期，高級語言剛剛誕生不久，計(jì)算機(jī)應(yīng)用開始被社會所重視并逐漸走向普及。有關(guān)數(shù)據(jù)結(jié)構(gòu)、算法、計(jì)算復(fù)雜性等課題吸引著眾多學(xué)者的注意。IBM作為美國乃至世界最大的計(jì)算機(jī)廠商，理所當(dāng)然成為這些研究問題的中心之一，集中了大批最優(yōu)秀的研究人員，在那里卡普主要研究了路徑問題、背包問題、覆蓋問題、匹配問題，調(diào)度問題等，但這些問題都存在組合爆炸問題。２０世紀(jì)６０年代初卡普仔細(xì)研究了路徑問題中的旅行商問題，和同事海爾特經(jīng)過反復(fù)研究，終于提出了一種稱為”分枝限界法“的新方法。該方法要點(diǎn)是：對解集合反復(fù)進(jìn)行分枝，每次分枝時都對所得的子集計(jì)算最優(yōu)解的界，如果對某個子集求得的界不優(yōu)于已知的允許解，則拋棄這個子集不再分枝。否則繼續(xù)分枝以探索更好的解。１９６８年卡普來到加州大學(xué)伯克利分校。這里是計(jì)算機(jī)科學(xué)理論的又一個研究中心，庫克、布盧姆（１９８５年圖靈獎獲得者）等一批知名學(xué)者當(dāng)時都在那里，學(xué)術(shù)氣氛十分濃厚。布盧姆是計(jì)算復(fù)雜性的主要奠基人之一，庫克則與1971年最早提出”NP完全性“問題，在這樣環(huán)境下，卡普對計(jì)算復(fù)雜性問題的研究日益深入。１９７２年卡普發(fā)表的論文“組合問題中的可歸約性”發(fā)展和加強(qiáng)了由庫克提出的”NP完全性”理論。尤其是庫克僅證明了命題演算的可滿足性問題是NP完全的，而卡普則證明了從組合優(yōu)化中引出的大多數(shù)經(jīng)典問題，包括背包問題、覆蓋問題、匹配問題、路徑問題、調(diào)度問題等，都是NP完全問題：只要證明其中任何一個問題是屬于P類的，就可以解決計(jì)算復(fù)雜性理論中的最大的一個難題P=?NP這是卡普論文的主要貢獻(xiàn)和意義。1986年圖靈獎獲得者霍普克洛夫斯特和陶爾揚(yáng)霍普克洛夫斯特１９３９年出生于西雅圖，１９６１年西雅圖大學(xué)畢業(yè)后進(jìn)入斯坦福大學(xué)研究生院深造，博士畢業(yè)后到普林斯頓大學(xué)工作。他成為著名的計(jì)算機(jī)科學(xué)家起源于一個十分偶然的機(jī)會。他學(xué)習(xí)的是電器工程專業(yè)，對計(jì)算機(jī)科學(xué)原本沒有多少知識。原打算到一所西海岸大學(xué)教授電器工程方面的課程。畢業(yè)前夕，有一次路過導(dǎo)師的辦公室門口，當(dāng)時普林斯頓大學(xué)的麥克盧斯基正為籌建”數(shù)字需要實(shí)驗(yàn)室“給霍普克洛夫斯特的老師打電話讓推薦博士，他的老師一眼瞥見了他，覺得勤奮好學(xué)、悟性又高的得意門生正是值得推薦的人才，就把他叫進(jìn)來并把話筒遞給他，經(jīng)過交談與考察，他接受了普林斯頓大學(xué)的邀請，從而改變了一生的道路。

年輕的霍普克洛夫斯特到普林斯頓之后接受的第1個任務(wù)是開設(shè)一門新課程：自動機(jī)理論，這對他來說是富有挑戰(zhàn)性的，因?yàn)樗安]有接觸過這個課程。面對挑戰(zhàn)，他虛心地請麥克盧斯基推薦關(guān)有參考資料。由于當(dāng)時沒有任何一所學(xué)校開設(shè)過自動機(jī)理論的課程，也沒有一本書籍，到底應(yīng)該講什么心里也沒有底。通過大量翻閱文獻(xiàn)，他開設(shè)了包括圖靈、麥柯勞赫和皮孜、拉賓和斯科特、巴克斯和諾爾、哈特馬尼斯和斯特恩斯以及喬姆斯基所寫的6篇論文課程。他對圖靈的計(jì)算模型，麥柯勞赫和皮孜的神經(jīng)網(wǎng)絡(luò)，拉賓和斯科特的有限自動機(jī)，巴克斯和諾爾描述程序的BNF，喬姆斯基的上下文無關(guān)文法等進(jìn)行了深入專研與消化，并加以分析、綜合和比較，逐漸理出了頭緒，成功地開出了新課。后來與厄爾曼合作編寫了《形式語言及其與自動機(jī)的關(guān)系》，感興趣的同學(xué)可以作為參考書閱讀。１９７０年霍普克洛夫斯特和陶爾揚(yáng)合作提出了深度優(yōu)先算法等一些圖論中的難題而獲圖靈獎。陶爾揚(yáng)1948年生于加利福尼亞，從小就是一個富于幻想、追求新鮮事物的人，幼年夢想成為登上火星的人，小學(xué)7年級開始看《科學(xué)美國人》雜志。1964年，陶爾揚(yáng)參加了一個中學(xué)生夏令營，第一次接觸了計(jì)算機(jī)，立即被神奇的計(jì)算機(jī)所吸引，因此他上加州理工學(xué)院時，輔修了學(xué)校開設(shè)的所有計(jì)算機(jī)課程，1969年畢業(yè)后進(jìn)入斯坦福大學(xué)師從于著名的計(jì)算機(jī)科學(xué)家克納斯(Knuth，1974年圖靈獎得主)，1970年在克納斯的有意安排下與康乃爾大學(xué)到普林斯頓學(xué)術(shù)休假的霍普克洛夫斯特共同研究圖論的算法。這個課題實(shí)際上是”人工智能之父“麥卡錫的建議下進(jìn)行的，霍普克洛夫斯特的新思路