李廉

摘 要：本文討論了計算思維兩個特有的性質(zhì)，即可解釋證明和關(guān)聯(lián)世界。這兩個特質(zhì)是計算思維區(qū)別于實證思維和邏輯思維的界石。依據(jù)科學(xué)思維的分類標準，本文從理論上闡述了這兩種特質(zhì)的內(nèi)涵以及在計算思維中的位置。同時，還進一步探討了這兩種特質(zhì)對于計算機科學(xué)和計算機工程的意義與作用，特別是在計算機工程中，這些特質(zhì)成為重要的理論基礎(chǔ)和背景，并且影響著工程技術(shù)的質(zhì)量標準和開發(fā)規(guī)范。結(jié)合教學(xué)改革實踐，本文提出了應(yīng)該在教學(xué)內(nèi)容中加強這方面理解的培養(yǎng)。

關(guān)鍵詞：計算思維；特質(zhì)性；可解釋證明；關(guān)聯(lián)世界；人才培養(yǎng)

自從周以真明確提出計算思維的概念后[1]，國內(nèi)經(jīng)過陳國良、王飛躍、徐志偉等人的研究和宣傳[2-4]，促進了對于大學(xué)計算機教育的重新認識和重新定位，并且持續(xù)影響著計算機課程的改革與建設(shè)。對計算思維本身的研究也在不斷地深化，形成了研究工作和教學(xué)實踐之間良性的互動。本文試圖就計算思維的核心概念做一些探討，基本問題是——計算思維有沒有屬于自己的獨特的思維方式和判斷標準，而這些方式和標準在實證思維和邏輯思維框架中是不被認可的？

一種思維模式實際上就是一種看待世界和認識世界的方法與觀點，也就是我們所說的世界觀，其核心內(nèi)容是對于思維結(jié)論正確性的判斷標準。任何思維都是以產(chǎn)生某種結(jié)論為目標的，對于結(jié)論的判斷標準，構(gòu)成了思維模式的獨有特質(zhì)。比如說唯心主義和唯物主義對于世界本源的看法就是不同的，因此擁有各自的世界觀。在科學(xué)思維中，以物理學(xué)為代表的實證思維與以數(shù)學(xué)為代表的邏輯思維，其看待世界的觀點也是不同的，并且形成了各自的判斷結(jié)論是否正確的不同的標準。那么比起實證思維和邏輯思維，稍晚以后發(fā)展起來的計算思維有沒有自己的世界觀呢？與實證思維和邏輯思維的世界觀究竟有什么不同呢？這個問題的確需要認真加以研究。

本文以下分為五個部分：第一部分我們簡要說明科學(xué)思維的分類標準；并且在第二部分回顧一下，作為實證思維的物理學(xué)和作為邏輯思維的數(shù)學(xué)，判斷結(jié)論正確性的標準是什么，有什么本質(zhì)上的不同；在第三部分，我們介紹計算思維的一些思維特點和理論基石，這些特點和基石奠定了計算思維的基礎(chǔ)，并且形成了有別于實證思維和邏輯思維的不同之處，從而使得計算思維之所以能夠成為第三種科學(xué)思維模式；在第四部分，我們介紹計算思維的一種特質(zhì)，即可解釋證明；它的另一種特質(zhì)，即關(guān)聯(lián)世界，將在第五部分討論；最后我們做一些總結(jié)。

一、科學(xué)思維的分類與特點

科學(xué)思維指的是在科學(xué)活動中的思維。一般而言，我們通過思維的外在形式進行分類，這種外在形式主要是思維的表現(xiàn)形式，以及判定結(jié)論正確性的標準?？茖W(xué)思維都是以產(chǎn)生結(jié)論為目的，因此以什么方式產(chǎn)生結(jié)論和以什么標準接受結(jié)論構(gòu)成了一種思維的特有標志，也是區(qū)別不同思維模式的主要依據(jù)。

比如說，在實證思維的模式中，人們通過觀察和實驗得出一些揭示客觀世界的結(jié)論，這些結(jié)論最重要的部分是以定律的形式出現(xiàn)的，而其他的結(jié)論則是以邏輯推論或者實驗驗證的方式出現(xiàn)的。對于同一個客觀世界，可以建立多種理論系統(tǒng)來進行解釋，因此人們必須約定一種解釋來展開對于客觀世界規(guī)律的認識和描述。這就是我們現(xiàn)在所使用的基于伽利略、牛頓、愛因斯坦等科學(xué)家建立的物理科學(xué)系統(tǒng)。在這個系統(tǒng)中，我們從少數(shù)幾個定律出發(fā)，建立起來解釋整個客觀世界的架構(gòu)。其中最顯著的特點是，任何結(jié)論，無論是通過什么方式得到的，只要在實驗中未被觀察或者驗證，則該結(jié)論不會被認可。實證成為判定結(jié)論正確性的唯一標準，這就是實證思維的特質(zhì)性。

而在邏輯思維中，產(chǎn)生結(jié)論和判定結(jié)論正確性則完全是另外一種方式。首先要有一個稱為公理的命題（結(jié)論）的集合，然后有一個推理規(guī)則，從公理出發(fā)通過推理規(guī)則產(chǎn)生的結(jié)論（包括公理本身）都被認為是正確的。無論這個結(jié)論聽起來多么荒謬。而對于有些結(jié)論，盡管可能在現(xiàn)實世界中被反復(fù)驗證，但只要不能從這個系統(tǒng)中通過推理得到，都不會被認為是正確的結(jié)論。邏輯推理成為判定結(jié)論的唯一標準，這就是邏輯思維的特質(zhì)性。

上述兩種思維模式顯然有著十分不同的特點，因此成為科學(xué)思維中的兩類思維模式，它們的代表分別是物理學(xué)和數(shù)學(xué)。我們不排除可以通過其他方式建立科學(xué)體系，只是因為人類社會的歷史發(fā)展，采用并且接受了目前這種關(guān)于物理學(xué)和數(shù)學(xué)的表達體系。因此大家必須共同遵循其中的原則，符合判定標準的結(jié)論必須認為是正確的，不符合判定標準的結(jié)論只能予以存疑。這是人類社會的基本的科學(xué)契約，只有大家遵守這一契約，科學(xué)才能健康有序地發(fā)展。

根據(jù)這樣的原則，可以解釋為什么沒有化學(xué)思維和生物學(xué)思維，也沒有經(jīng)濟學(xué)思維和管理學(xué)思維。不同的學(xué)科可以采取相同的思維方式，只要產(chǎn)生結(jié)論的方式和判定標準相同，其思維模式也就是相同的。在化學(xué)或者經(jīng)濟學(xué)中間，其思維的方式和標準與物理學(xué)和數(shù)學(xué)沒有什么不同，或者只是它們的混合而已。區(qū)別僅在于思維的對象不同，而產(chǎn)生思維結(jié)論的方式和判定標準是一樣的。思維模式的分類不是以思維對象來區(qū)別的。人文科學(xué)里面的某些學(xué)科，例如文學(xué)、藝術(shù)等，這些學(xué)科中含有藝術(shù)思維的特點，不完全是科學(xué)思維的范疇，在這些思維中產(chǎn)生的結(jié)論和判定標準有其他要求，不屬于本文討論的范圍。

由此而論，作為計算思維，也應(yīng)該有獨特的產(chǎn)生結(jié)論方式和判定標準，這樣才能成為一種新的思維模式。按照周以真的觀點，計算思維最本質(zhì)的特點是抽象和自動化，它的表現(xiàn)形式具有有限性、程序性、機械性、可行性這樣一些特點。但是這樣的表述仍然沒有把計算思維和邏輯思維完全脫開，僅從抽象和自動化這樣的概念，其闡述過于簡單，難以展開為一個理論體系。實際上，抽象本身也是數(shù)學(xué)的一個特點，數(shù)學(xué)本身也承認可構(gòu)造性、可實現(xiàn)性，循環(huán)迭代這樣的對象生成方式。因此僅從這些方面來闡述計算思維的特點，雖然把握了本質(zhì)，但是缺乏一定的理論基礎(chǔ)和特征刻畫，似乎還不足以將計算機科學(xué)從數(shù)學(xué)中脫離出來，因此我們需要探討計算思維背后更為本質(zhì)的內(nèi)容和徹底區(qū)別于實證思維和邏輯思維的特征。也就是說，要探討計算思維究竟提供了一種什么樣的看待世界的方式與標準，探討計算思維視野下的世界觀。

參考文獻[5]對這些問題有更詳細的論述，可參閱。

二、實證思維和邏輯思維的模式與基石

確立一種思維模式的主要依據(jù)是它產(chǎn)生結(jié)論的方式和判斷結(jié)論的標準。在這一節(jié)中，我們將繼續(xù)深入討論這一問題，為了更加清楚，我們選擇物理學(xué)和數(shù)學(xué)這兩個最具代表性的學(xué)科進行討論。

物理學(xué)的科學(xué)體系是建立在以觀察事實為根據(jù)的假設(shè)上面，這些假設(shè)是經(jīng)過無數(shù)次的觀察和實驗得到的，一般稱為定律或者原理，例如在經(jīng)典力學(xué)中的牛頓三定律，熱力學(xué)中的熵增原理，相對論中的光速不變定律，甚至包括量子力學(xué)中的測不準原理和泡利不相容原理。這些原理構(gòu)成了物理學(xué)的基石。人們從這些原理出發(fā)，可以通過新的實驗得出新的結(jié)論，也可以通過邏輯推導(dǎo)得出新的結(jié)論。以此不斷地豐富著物理學(xué)的科學(xué)體系。如果通過新的觀察和實驗得出了結(jié)論，則進一步分析這一結(jié)論與已有結(jié)論的關(guān)系，是否獨立于已有的結(jié)論。如果與已有結(jié)論不獨立的話，則這一結(jié)論成為一個推論或者定理；如果獨立于已有的結(jié)論，并且與已有結(jié)論不矛盾的話，則這一結(jié)論將會成為物理學(xué)新的原理或者定律；如果與已有結(jié)論矛盾的話，則物理學(xué)將發(fā)生重大變革，重新建立一種新的理論體系。在這個過程中，結(jié)論與常識是否矛盾不作為判斷結(jié)論正確性的標準，唯一的標準就是與實驗觀察是否矛盾。這是物理學(xué)產(chǎn)生結(jié)論的方式以及判斷結(jié)論的標準。如果一個結(jié)論是從邏輯推導(dǎo)出來的，那么不管這個結(jié)論能否解釋以前的事實，以及是否多么優(yōu)美，只要其預(yù)見的事實沒有在實驗中被觀察到，都不會作為物理學(xué)的結(jié)論被接受。其中最典型的例子是弦理論，弦理論有一套十分完美的數(shù)學(xué)表達，又能夠很圓滿地解釋目前為止觀察到的所有物理現(xiàn)象，但是在弦理論預(yù)報的事實被觀察或者實驗證實以前，仍然只能作為一種數(shù)學(xué)結(jié)論，而不是物理結(jié)論。至今為止，弦理論可以獲得菲爾茨獎，但還不能獲得諾貝爾物理學(xué)獎。物理學(xué)的體系大廈就是通過這樣的方式建立起來的，實證是其檢驗真理的唯一標準。

數(shù)學(xué)體系的建立遵循另外一種方式。在數(shù)學(xué)體系里面，首先有一些稱為公理的結(jié)論，這些結(jié)論的正確性在體系內(nèi)部是無需證明的。然后選擇一種推理規(guī)則，由公理出發(fā)，經(jīng)過推理得到的新的結(jié)論稱為體系中的定理。這些結(jié)論的正確性只依賴于推理過程的正確性，與該結(jié)論是否與自然世界的現(xiàn)象符合沒有關(guān)系。因此，可以有各種各樣的數(shù)學(xué)體系，甚至有常識看來不可思議的數(shù)學(xué)體系。從邏輯思維的角度來說，這些數(shù)學(xué)體系都是符合邏輯思維標準的。當(dāng)然為了保證數(shù)學(xué)體系“有用”，能夠用于真實世界的解釋和演繹，就不是每一種數(shù)學(xué)體系都被等同對待，而是對于在科學(xué)中“有用”的數(shù)學(xué)予以特別的關(guān)注。當(dāng)今，這個數(shù)學(xué)體系基本上是建立在重言式公理上，應(yīng)用三段式推理規(guī)則的體系，通過添加不同的附加公理形成不同的數(shù)學(xué)分支。三段式推理規(guī)則和重言式公理構(gòu)成了數(shù)學(xué)的基石。

從上面的討論可以看出，物理學(xué)與數(shù)學(xué)產(chǎn)生結(jié)論方式是不同的，判斷結(jié)論也采取了不同的標準。其共同點是，它們都有一個作為結(jié)論產(chǎn)生起點的基石，有一種產(chǎn)生結(jié)論的程式，以及判斷結(jié)論的標準。這些內(nèi)容構(gòu)成了實證思維和邏輯思維的特質(zhì)。物理學(xué)的一些結(jié)論可以完全不符合數(shù)學(xué)結(jié)論的標準，數(shù)學(xué)的一些結(jié)論也可以完全不符合物理學(xué)的標準。因此這是兩種不同的科學(xué)思維模式。

這里強調(diào)兩點。首先，基本假設(shè)與學(xué)科領(lǐng)域有關(guān)，在一個學(xué)科領(lǐng)域里面的定律或者假設(shè)，有時可以在另一個領(lǐng)域中得到解釋乃至推論，這一點不影響在本領(lǐng)域中的地位，任何領(lǐng)域內(nèi)部的科學(xué)思維都需要有一個約定的起點，這個起點在本領(lǐng)域中被認為是不證自明的。比如在經(jīng)典物理學(xué)中的關(guān)于時間和空間的性質(zhì)就是該領(lǐng)域中的基本假設(shè)，但是在現(xiàn)代物理學(xué)中，可能是更加基本的假設(shè)的推論。其次，基本假設(shè)并不是絕對不能否定，但是如果基本假設(shè)被否定，將會導(dǎo)致整個領(lǐng)域體系的重新構(gòu)建，因此都是重大的突破和革命，這樣的事情在科學(xué)發(fā)展史中有過，但是很少出現(xiàn)。

做了這些討論之后，現(xiàn)在我們討論關(guān)于計算思維的模式和基石。

三、計算思維的模式與基石

根據(jù)上面的討論，計算機科學(xué)體系也有它的基本假設(shè)，這些基本假設(shè)構(gòu)成了計算機科學(xué)的基石。本文中我們提出計算機科學(xué)的三個重要基石，它們分別是：

（1）圖靈機理論，即理論可計算性（theoretic computability）；

（2）復(fù)雜性理論，即現(xiàn)實可計算性（feasible computability）；

（3）交互式證明系統(tǒng)，即交互可計算性（interactive computability）。

圖靈機理論奠定了計算機科學(xué)的基礎(chǔ)，這一點毫無疑問。并且從理論上建立了關(guān)于計算和可計算的概念。復(fù)雜性理論提出了現(xiàn)實可計算問題，特別是NP問題，使得計算機科學(xué)與數(shù)學(xué)開始分道揚鑣，計算機科學(xué)所特有的思維和方法逐步顯現(xiàn)和建立。這些內(nèi)容都是已經(jīng)熟悉的了，下面我們專門介紹一下交互式證明系統(tǒng)，這也是一種計算模型。

一個交互式證明系統(tǒng)（Interactive Proving System，IPS）是一對圖靈機，分別記作V和P，稱為驗證者（Verifier）和證明者（Prover），其中V是確定的，P是非確定的。問題x初始被放置在公共的輸入帶上，證明者P產(chǎn)生一個符號串y，稱為證據(jù)（witness），而驗證者V檢查這個y是否為問題x的解，如果是解，則停機，宣布問題解決。這個過程稱為P和V的一次交互。這個過程可以反復(fù)進行，即P和V可以反復(fù)通訊，V不斷地向P提出詢問，而P根據(jù)V的問題，不斷地提供證據(jù)給V，而V通過檢查證據(jù)來確定是否停機。如果x確實有解，則V最終必然停機。

如果規(guī)定V只有多項式時間的計算能力，這時所能解決的問題類稱為多項式交互時間可解決的問題類，記作IP（Interactive polynomial-time）。在任何情況下，我們總假定Prover相對于Verifier而言有無窮的能力，這意味著，如果問題x有解，P總能為V提供適當(dāng)?shù)淖C據(jù)使得V停機。

IP可以看作是從NP問題發(fā)展而來的。一個NP問題，它的解具有多項式長度，而且解的驗證可以在多項式時間完成，難點在于如何找到這個解，這個一般需要猜測。假設(shè)有一個上帝，即前面說的Prover，對于任何輸入的NP問題x，如果x有解，那么Prover就可以產(chǎn)生這個解y，繼而由Verifier驗證y是否的確是一個解，這只需要多項式時間。因此NP問題只需要Prover和Verifier一次交互即可。反過來，只需要在多項式時間做一次交互就可以判斷的問題類也一定是NP問題類。因此NP問題類是IP問題類的一個子類。

更一般的情形是要求如果問題x有解，則V以大于零的概率停機，宣布問題有解。這種系統(tǒng)稱為交互式概率證明系統(tǒng)（Interactive Probabilistic Proving System，IPPS），這個系統(tǒng)可解的問題類記作IPP（Interactive Probabilistic Polynomial-time）。顯然IPPIP，但是現(xiàn)在還不知道是否IPP=IP，特別地，甚至還不知道一個NP完全問題如果有解，是否能夠以大于零的概率給出判斷。在應(yīng)用的背景下，經(jīng)常使用概率交互式證明系統(tǒng)的概念，因為這種系統(tǒng)更容易作為工程問題的模型。

下面我們從另外一個更加形式的角度來定義NP和IP。

令是一個字母表，L*是一個語言， 是定義在*上的二值函數(shù)，并且是確定的多項式時間可計算函數(shù)，|x|表示符號串x的長度， 表示x長度的某個多項式。語言L屬于NP，如果

這里面的y就稱為 的證據(jù)。量詞 和 各出現(xiàn)了一次，稱為一次交互。

多次交互（有限次）的語言類IP定義為：

其中，F(xiàn)是定義*上的2n元的確定的多項式時間可計算函數(shù)，n稱為交互次數(shù)。

還可以繼續(xù)推廣為多項式次交互的語言類IP。即交互次數(shù)是輸入長度的多項式。對于IPP，只需要在上面的定義作一點改動。

其中Pro（E）表示事件E的概率。

關(guān)于IPP更加詳細的內(nèi)容可以參看參考文獻[6]、[7]、[8]。

IP（或者IPP）提供了一種新的解決問題和判斷結(jié)論的方法。通過Prover和Verifier的反復(fù)交互，使得Verifier得以正確判定問題的解。Verifier的判定算法是多項式的，而Prover以“神諭”的方式提供判定問題的證據(jù)。從計算機科學(xué)的角度來看，這種證明問題的方式是NP問題理論的發(fā)展，給出了完全新穎的一種思維形式。在下一節(jié)中，我們將說明這種思維模式是計算思維特有的，而數(shù)學(xué)所不包含的。

直觀地說，交互式證明系統(tǒng)是一種問答式證明，當(dāng)問題x1放置在公共輸入帶上時，如果x1L，Prover將提供證據(jù)y1試圖使Verifier相信這個事實，而Verifier則根據(jù)算法來驗證y1是否能夠證明x1L，如果可以，則Verifier接受x1，否則將向Prover提出詢問x2，而Prover繼續(xù)提供新的證據(jù)x2，以此反復(fù)，直到Verifier接受x1。Verifier是確定的多項式時間圖靈機，它的能力是有限的，但是它的結(jié)論是可靠的。Prover具有無限的猜測能力，但是它給出的證據(jù)需要Verifier來驗證，這是二者的區(qū)別。

實際上，我們對于Verifier限定為確定的多項式時間，這完全是從現(xiàn)實可行的角度。理論上，Verifier可以具有任意的時間度量t，相應(yīng)的語言類也稱之為交互式t時間復(fù)雜度類的語言。本文中我們約定的是多項式時間復(fù)雜度，即IP（或者IPP）這個語言類。

如果我們只是要求交互過程能夠給出解，則這時解決的問題類就是IP。如果更進一步，要求給出解的概率大于零，這時解決的問題類就是IPP。IPP的要求比起IP要嚴格，也就是說，在交互證明過程中，如果解存在，不僅要求能夠給出解，還要求以一定的概率給出解，這個在工程上是重要的，因為工程問題要求的往往不僅是能夠解決問題，而是要求必須在一定程度上保證解決問題。因此IPP是解決工程問題的很好的模型，而IP是理論上的常用的模型。在實際模型中，一般要求系統(tǒng)以大于3/4概率給出正確判斷。在發(fā)起一次問題解決中，我們應(yīng)該有大于3/4 的把握得到正確答案。換句話說，在不知道問題解的前提下，如果我們得到一個答案，則這個答案正確的概率應(yīng)該大于3/4。這種問題求解的方式?jīng)Q定了計算思維特有的模式，交互式證明也成為計算思維體系中的基石之一。

四、計算思維的特質(zhì)性——可解釋證明

交互式證明系統(tǒng)是一種新的判斷結(jié)論的方式，這是通過Verifier和Prover的信息交互實現(xiàn)證明過程的。P和V雙方在交互過程逐步達到對于證明的認可。由于V是以確定的方式進行驗證，因此結(jié)論的判定是可靠的。P是以一種“神諭”的方式提供證據(jù)，雖然能力是無限的，但是沒有V的驗證，證明過程不能結(jié)束。這種證明方式很像在課堂里，學(xué)生和老師的互動，學(xué)生相當(dāng)于V，老師相當(dāng)于P，學(xué)生不斷向老師發(fā)問，而老師總是可以正確地回答學(xué)生的提問，最終使學(xué)生相信結(jié)論。因此這種方式在文獻[8]中稱為“可解釋證明”，這個名稱很形象地說明了交互式證明的特點。可解釋證明是不同于數(shù)學(xué)的一種新的證明方式，我們稱之為計算可證明。

數(shù)學(xué)證明是一次性證明，即對于一個數(shù)學(xué)問題，它的證明可以一次性地寫下來，而以后任何人只要閱讀這個證明就可以相信這個結(jié)論。為了將這個問題限制在一個合理的范圍，我們一般將數(shù)學(xué)可證明問題類與NP問題類等同起來。一個NP問題，如果能夠找到解，則證明這個解的長度不會太長，因此可以書寫下來，所以NP問題類是可書寫證明類。從這個觀點，可書寫證明的問題類是NP，可解釋證明問題類是IP，因此，可書寫證明問題類（即數(shù)學(xué)可證明）是否等于可解釋證明問題類（即計算可證明）就等價于IP=？NP。這是一個目前還不知道答案的問題。如果IP≠NP（正如人們所猜測的），那么數(shù)學(xué)可證明就不能涵蓋計算可證明。如果IP=P，則計算科學(xué)將會塌縮為數(shù)學(xué)。

一次交互的證明是數(shù)學(xué)證明，必須多次交互才能得到的證明不符合數(shù)學(xué)的標準。因此IP已經(jīng)超出了數(shù)學(xué)可證明的范圍。一個NP問題如果未被證明，找到證明只是時間問題，而一旦找到證明，就可以寫下來從而一勞永逸。但是一個IP問題卻會在不同的場合經(jīng)歷不同的證明過程，這些過程可能沒有重復(fù)性和一致性，只是一種“就事論事”的證明方式。一個問題的可解釋證明性本身不能被數(shù)學(xué)證明，除非IP=NP。自然也不可能事先將所有的問題及答案都寫下來，以備后人的提問。因為對于一個多項式時間的交互式證明系統(tǒng)而言，各種可能的交互過程在規(guī)模上是指數(shù)時間的，因此全部寫下來是不可能的。交互式證明只能根據(jù)V的提問和P的回答而展開，無法事先規(guī)定好的。這是可解釋證明本身不能被數(shù)學(xué)證明的原因。

交互式系統(tǒng)強調(diào)問題的解決是在交互過程中實現(xiàn)的，這個思想在工程中得到很好的體現(xiàn)。無論是在軟件開發(fā)、系統(tǒng)設(shè)計以及問題求解中，我們都不能期望數(shù)學(xué)意義上的一次性解決所有問題，或者一次性證明軟件或者系統(tǒng)的正確性。在絕大多數(shù)情況下，這種數(shù)學(xué)意義上的證明是不存在的。因此在實際工程中，我們要求所開發(fā)的軟件，或者設(shè)計的系統(tǒng)對于控制對象或者運行環(huán)境有很好的響應(yīng)性，即當(dāng)控制對象和運行環(huán)境發(fā)生變化時，控制系統(tǒng)或者運行系統(tǒng)能夠及時予以響應(yīng)，以保證系統(tǒng)能夠正確運行。在這個過程中，控制對象或者運行環(huán)境看作V，而系統(tǒng)本身看作P，無論V出現(xiàn)什么問題，P都能正確予以響應(yīng)，從而使得V保持在正確的狀態(tài)運行。因此一個系統(tǒng)控制或者運行的過程就是一個與對象和環(huán)境交互的過程。甚至在軟件工程中，對于用戶的需求和軟件的設(shè)計之間也是不斷交互的過程。交互式系統(tǒng)更適合作為描述這類工程問題的理論基礎(chǔ)，而不是數(shù)學(xué)。在工程背景下，看重的是系統(tǒng)對于環(huán)境變化的響應(yīng)性和適應(yīng)性，這種問題用傳統(tǒng)的數(shù)學(xué)觀點來思維基本上行不通，因此交互式證明的理論和應(yīng)用可以很好地解決這一類問題。在這個意義上，我們所說的一個軟件的正確性，一個系統(tǒng)的正確性都應(yīng)該是在交互式證明意義上的正確性。

由于可解釋證明本身不能數(shù)學(xué)證明，因此在工程中采取了一些專門的方法來說明（不是證明！）軟件或者系統(tǒng)在可解釋證明意義上的正確性。其中一種辦法是測試，測試是一種交互，采取事先設(shè)計好的測試程序，對于可能發(fā)生的問題進行檢查，以判斷軟件或者系統(tǒng)應(yīng)對變化的能力。測試不是窮舉方法，因此不可能覆蓋所有可能的問題，只是希望測試的內(nèi)容有一定的代表性，盡可能反映可能出現(xiàn)的問題。這就有各種測試理論和實踐方法。在實際應(yīng)用中，建立測試平臺（benchmark）是常用的方式，通過測試平臺，不同的產(chǎn)品之間有一個客觀的比較依據(jù)，除了測試產(chǎn)品本身的性能評價，也提供了相同類型不同產(chǎn)品之間的性能比較。

工程上另一種處理方式是建立規(guī)范和標準。凡是符合規(guī)范和標準的產(chǎn)品都被認為是合格的，這也是對于產(chǎn)品在可解釋意義下具有正確性的一種說明?，F(xiàn)在網(wǎng)絡(luò)的軟件開發(fā)和系統(tǒng)設(shè)計大量采用規(guī)范和標準，通過規(guī)范和標準，產(chǎn)品的性能有一定的保證，從工程意義上講，這樣的產(chǎn)品是可以信任和使用的。當(dāng)然如何制定好的規(guī)范，以確保依據(jù)規(guī)范開發(fā)的產(chǎn)品具有可靠性和穩(wěn)定性，這是規(guī)范理論中需要研究的內(nèi)容，其中交互式證明系統(tǒng)理論具有重要的意義。

交互以及交互式證明是我們在計算機課程中應(yīng)該重點培養(yǎng)的意識，這種訓(xùn)練以前是不夠的。由于受到數(shù)學(xué)的深刻影響，在計算機的很多課程里，也經(jīng)常習(xí)慣于用數(shù)學(xué)的觀點和標準來考慮求解問題和設(shè)計系統(tǒng)，這些方法在很多工程問題上效果不佳。究其原因，還是因為計算機科學(xué)或者計算機工程與數(shù)學(xué)是兩種不同的思維方式，用數(shù)學(xué)的思維方式來解決工程問題會使我們的思路過于狹窄和絕對，難以培養(yǎng)出真正的計算機科學(xué)和工程應(yīng)用人才。另一個極端是，由于工程問題難以用數(shù)學(xué)的方法來評價，因此在很多工程問題的設(shè)計和開發(fā)中，干脆處于完全沒有理論指導(dǎo)的狀況，采取了就事論事或者隨心所欲的方式，使得軟件或者產(chǎn)品的質(zhì)量沒有嚴格的保證。這兩種情況現(xiàn)在都存在，后者似乎更普遍一些，因此將交互式證明系統(tǒng)理論引入工程設(shè)計和開發(fā)，是一個合適的選擇。這是計算思維帶給我們的一種完全不同于邏輯思維的啟示，也是我們推進以計算思維為導(dǎo)向的計算機課程改革所應(yīng)重點關(guān)注的問題之一。

五、計算思維的特質(zhì)性——關(guān)聯(lián)世界

計算思維另一個特質(zhì)性是關(guān)聯(lián)關(guān)系。這是從計算思維角度看世界的一種方式。物理學(xué)看世界的觀點是因果關(guān)系，比如說，一個物體改變了運動形式，那么一定是受到某個力的作用。而數(shù)學(xué)看世界的方式是邏輯關(guān)系，比如說，如果從等腰三角形的頂點向底邊做一個垂線，則該垂線一定平分底邊。這是物理學(xué)和數(shù)學(xué)看待世界的不同方式，也就是物理學(xué)和數(shù)學(xué)的世界觀。

與物理學(xué)和數(shù)學(xué)不同，計算機科學(xué)看待世界的方式是關(guān)聯(lián)，關(guān)聯(lián)是現(xiàn)象之間的一種聯(lián)系。對于計算機科學(xué)來說，不關(guān)心現(xiàn)象之間的內(nèi)部因果關(guān)系，也不關(guān)心現(xiàn)象之間的邏輯關(guān)系，只關(guān)心現(xiàn)象之間的空間關(guān)系和時間關(guān)系。計算機處理的是符號，而符號是客觀對象的抽象，所有的現(xiàn)象都被作為數(shù)據(jù)成為計算機處理的內(nèi)容，因此在計算機科學(xué)看來，現(xiàn)象是世界萬物的表現(xiàn)形式，具體的內(nèi)容就是數(shù)據(jù)。特別是當(dāng)前已經(jīng)進入大數(shù)據(jù)時代，關(guān)于數(shù)據(jù)與數(shù)據(jù)，也就是現(xiàn)象與現(xiàn)象之間關(guān)系的研究日益成為計算機科學(xué)的重要內(nèi)容。這些研究也推進了計算思維在內(nèi)涵上的豐富，即形成了從關(guān)聯(lián)關(guān)系來看待世界的一種新的世界觀[9，10]。

關(guān)聯(lián)研究現(xiàn)象出現(xiàn)的關(guān)系主要有兩種：一種是空間關(guān)系，研究現(xiàn)象之間的位置關(guān)系；另一種是時間關(guān)系，研究現(xiàn)象之間的次序關(guān)系。為了從大量的現(xiàn)象或者數(shù)據(jù)中找出其中的位置關(guān)聯(lián)或者時間關(guān)聯(lián)，目前已經(jīng)發(fā)展出一些技術(shù)來挖掘這些關(guān)聯(lián)。其中關(guān)于空間關(guān)聯(lián)，這里的空間既包含通常所說的幾何空間，也包含問題所定義的抽象空間，主要是對于數(shù)據(jù)的分類，在定義的空間里面，把相近的數(shù)據(jù)進行劃分，或者說找出數(shù)據(jù)之間的聚類關(guān)系。技術(shù)上被大量采用的是熟悉的支持向量機（SVM）以及神經(jīng)網(wǎng)絡(luò)（NN）。這兩種技術(shù)都是通過學(xué)習(xí)和訓(xùn)練，給出劃分數(shù)據(jù)相互空間關(guān)系的模型。關(guān)于時間關(guān)聯(lián)，當(dāng)前比較常見的是貝葉斯網(wǎng)絡(luò)以及通過貝葉斯公式演化出來的各種動態(tài)模型。通過對于模型的修正，得到接近于實際情況的數(shù)據(jù)之間的次序（時間）關(guān)聯(lián)關(guān)系[11，12]。

關(guān)聯(lián)關(guān)系是統(tǒng)計意義上的，一個事件A與另一個事件B關(guān)聯(lián)，是在統(tǒng)計意義上說的。因此當(dāng)A發(fā)生時，未必一定發(fā)生B，而是在一定程度上會發(fā)生B，這是關(guān)聯(lián)關(guān)系與因果關(guān)系和邏輯關(guān)系最大的區(qū)別。在人類行為分析的研究中，更多的是現(xiàn)象的關(guān)聯(lián)關(guān)系，定性的或者定量的建立并且分析這些關(guān)聯(lián)關(guān)系，在社會科學(xué)和人文科學(xué)方面占據(jù)了重要的內(nèi)容。

從小學(xué)到中學(xué)，我們的所有思維訓(xùn)練基本上都是因果的或者邏輯的，也就是說，物理課和數(shù)學(xué)課對于我們的影響太深，并由此養(yǎng)成了非此即彼的思維習(xí)慣。但是，計算思維卻訓(xùn)練我們另外一種思維方式，這種思維方式關(guān)注事物之間的關(guān)系，并由此產(chǎn)生定性的甚至是定量的分析，這種關(guān)系具有一定的不確定性和變化性，這種思維拓寬了看世界的角度和方法。因此在大學(xué)里要逐步學(xué)會從關(guān)聯(lián)的角度來看世界。這對于使用計算機解決問題是十分基礎(chǔ)的。現(xiàn)象之間最重要的是其中的關(guān)聯(lián)程度，如果弄清楚了這些關(guān)聯(lián)，也就能夠提出解決問題的思路和方法。至于這些現(xiàn)象內(nèi)部的因果關(guān)系或者邏輯關(guān)系，從計算思維角度來說都不是重要的。

現(xiàn)在大數(shù)據(jù)分析和網(wǎng)絡(luò)科學(xué)方面引進了大量關(guān)于關(guān)聯(lián)的理論和分析工具。比如網(wǎng)絡(luò)中的無尺度理論、小世界理論以及在對于人類行為分析的冪律現(xiàn)象，都是關(guān)聯(lián)分析中得到的重要規(guī)律[13]。從事物的關(guān)聯(lián)來思考問題，而不是從因果或者邏輯角度思考問題，是計算思維的特有性質(zhì)，作為計算機基礎(chǔ)課程，訓(xùn)練這種思維自然是一個重要的內(nèi)容。

六、總結(jié)

在本文中，我們討論了計算思維的兩個特質(zhì)，即可解釋證明和關(guān)聯(lián)世界。這是計算思維區(qū)別于實證思維和邏輯思維的界石，也是不同于前兩種思維的新的世界觀和價值觀。以此衍伸出來一些工程的方法和模式都無不與此有關(guān)，奠定了計算思維在計算機科學(xué)和工程中的重要地位。因此從教學(xué)的角度，這種思維的養(yǎng)成以及兩種特質(zhì)的掌握需要深刻探討。這也是學(xué)生從高中學(xué)習(xí)到大學(xué)學(xué)習(xí)需要經(jīng)歷的重大轉(zhuǎn)變。大學(xué)計算機課程在計算思維的培養(yǎng)方面，要逐步使得學(xué)生能夠在交互過程中解決問題，通過觀察建立事物之間關(guān)聯(lián)規(guī)律，養(yǎng)成這樣一些思考問題的觀念和習(xí)慣，對于提高學(xué)生科學(xué)思維的綜合素質(zhì)無疑是十分重要的。

在實際的科學(xué)活動中，各種思維是混合運用的，基本不會單純使用一種思維模式來認識問題和解決問題。因此本文所提出的計算思維這些特質(zhì)，是作為一種研究單獨抽取出來，目的是清楚地勾畫出計算思維的特有方式和標準，把這些都搞清楚了，有利于提高在解決實際問題時綜合應(yīng)用各種思維的能力。這是我們要強調(diào)的一點。

隨著網(wǎng)絡(luò)和數(shù)據(jù)科學(xué)的進一步發(fā)展，更多的計算思維特征還會被進一步挖掘和表現(xiàn)，發(fā)揮越來越重要的作用。當(dāng)然，涉及這兩種計算思維特質(zhì)的具體形式，由于其基本內(nèi)容過于專門，即使計算機專業(yè)的學(xué)生也不一定學(xué)習(xí)這些內(nèi)容，因此在大學(xué)計算機基礎(chǔ)課程中也不可能專門講授這些內(nèi)容，但是對于教師，應(yīng)該了解這方面的材料，并把其中的基本特點教給學(xué)生，以培養(yǎng)學(xué)生在這些方面的理解和意識，我們在教學(xué)改革中應(yīng)該認真地加以重視。

參考文獻：

[1] Jeannette M. Wing. Computational Thinking[J]. Communications of the ACM， 2006， 49（3）： 33-35.

[2] 陳國良，董榮勝. 計算思維與大學(xué)計算機基礎(chǔ)教育[J]. 中國大學(xué)教學(xué)，2011（1）.

[3] 王飛躍. 計算思維與計算文化[N]. 科學(xué)時報，2007-10-12.

[4] Xu ZW， Tu DD. Three new concepts of future computer science[J]. Journal of Computer Science and Technology， 2011， 26（4）： 616-624.

[5] R. Penrose. The Emperors new mind， concerning computers， mind， and the law of physics[M]. Oxford， New York， Melbourne： Oxford University Press；中譯本：徐明賢，吳忠超譯. 長沙：湖南科學(xué)技術(shù)出版社，1999.

[6] L.Babai， S. Moran. Arthur-Merlin games： A randomized proof system， and a hierarchy of complexity classes[J]. Journal of computer and system scineces， 1988， 36， 254-276.

[7] R. Canetti. More on BPP and the polynomial-time hierarchy[J]. Information processing letters， 1996， 57， 237-241.

[8] S. Goldwasser， S. Micali， C. Rackoff. The knowledge complexity of interactive proof-system[J]. SIAM Journal on Computing， 1989， 18（1）， 186-208.

[9] Lindsay， R. & Gorayska， B. Relevance. Goals and Cognitive Technology[J]. International Journal of Cognitive Technology， 2002， 1（2）： 187-232.

[10] Hjorland， Birger. The foundation of the concept of relevance[J]. Journal of the American Society for Information Science and Technology， 2010， 61（2）： 217-237.

[11] T. Mitchell. Machine Learning[M]. 中譯本： 曾華軍，張銀奎譯. 北京：機械工業(yè)出版社，2003.

[12] 鄧乃揚，田英杰. 數(shù)據(jù)挖掘中的新方法：支持向量機[M]. 北京：科學(xué)出版社，2004.

[13] A. L. Barabasi. Bursts， the hidden pattern behind everything we do[J]. Publisher Penguin， 2010.

[責(zé)任編輯：余大品]