第二類計算機(jī)構(gòu)想

楊正瓴

(天津大學(xué)電氣與自動化工程學(xué)院，天津 300072)

0 引言

未來的超級計算機(jī)到底是怎樣的?在簡要回顧現(xiàn)有的各種計算機(jī)基礎(chǔ)上，本文主要對“第二類計算機(jī)”進(jìn)行初步的構(gòu)想。著名物理學(xué)家費(fèi)密(Enrico Fermi)說［1］:“做理論物理計算有兩種方法。第一種是對所計算的過程有一個清晰的物理圖像，這是我喜歡的方法。另外一種是有一個精確的自洽的數(shù)學(xué)形式?！北疚膶⒅攸c(diǎn)放在“一個清晰的物理圖像”上，即主要提出一種概念性的構(gòu)想。并且盡可能采用直觀的自然語言。為彌補(bǔ)可能引起的“精確的自洽的數(shù)學(xué)形式”方面不足，有關(guān)概念的嚴(yán)謹(jǐn)數(shù)學(xué)表述請參考本文列出的各相關(guān)文獻(xiàn)。

1 數(shù)學(xué)準(zhǔn)備

1.1 康托定理(Cantor，1878 年)

對任何集合A，它的冪集P(A)的復(fù)雜性(基數(shù))是A的基數(shù)的指數(shù)方式，即|P(A)|=|2A|=2|A|。P(A)由所有A的子集(A的部分)構(gòu)成。

康托定理的另外一種表述為:

下面各集合 A，2A，22A，……中的任何兩個，都不具有相同的基數(shù)［2～4］。

依此，康托構(gòu)造了無窮基數(shù)第二序列

a，c，f，h，i，b，……，其中，a 為全體自然數(shù)集的基數(shù)，c=2a為全體實(shí)數(shù)集的基數(shù)，f=2c為全體幾何曲線集的基數(shù)［3］。為方便，接著記 h=2f，i=2h，b=2i。

這個序列是這樣構(gòu)造的:首先選可數(shù)無窮集，它的基數(shù)為a，這樣的集合有全體自然數(shù)集、全體整數(shù)集和全體有理數(shù)集等;這種集合冪集的基數(shù)為c，它是全體實(shí)數(shù)集的基數(shù)，或連續(xù)統(tǒng)的基數(shù)等;進(jìn)一步，基數(shù)c集合冪集的基數(shù)為f，它是全體幾何曲線集的基數(shù)，一切只取0或1為值的單值實(shí)變函數(shù)集合的基數(shù)等。人腦的常規(guī)復(fù)雜性為h，社會運(yùn)動的復(fù)雜性為i［5］。

1.2 Chaitin定理(1974年)

一般認(rèn)為，Chaitin定理是歌德爾第一不完備性定理(G?del's first incompleteness theorem，1931 年［3，4］)的信息論形態(tài)下的具體化。

對于由0、1字符串構(gòu)成的形式邏輯系統(tǒng)［6］。

(1)在一個n位公理的形式系統(tǒng)中，不能證明復(fù)雜性高于n+cT的命題。這里cT是一個常數(shù)。

(2)相反地，在n+cT位公理的形式系統(tǒng)中，可以證明那些復(fù)雜性不高于n的命題;并且可以構(gòu)造出復(fù)雜性等于或高于n的命題，盡管不能證明它們。

(3)不幸地，對于一個可以證明的命題，會遇到下面兩種困難之一:在一個位數(shù)少的公理系統(tǒng)中，需要一個難以置信長的證明過程;想得到一個短的證明過程，則需要一個難以置信長位數(shù)的公理系統(tǒng)。

1.3 Kuratowski定理(1930 年)

一個有限無向圖是平面圖，當(dāng)且僅當(dāng)它不含有與 K5或 K3，3同胚的子圖［4，7］。Kuratowski圖 K5和K3，3如圖 1 所示。

圖1 Kuratowski圖 K5 和 K3，3

以下是工作介紹。

2 超級計算機(jī)分類方法

這個方法發(fā)表在1999年《哲學(xué)研究》［5］，有關(guān)細(xì)節(jié)還可見參考文獻(xiàn)［8，9］。相關(guān)要點(diǎn)回顧如下。

國家自然科學(xué)基金委員會的發(fā)展戰(zhàn)略報告指出:“從一般意義上說，任何物理過程中的信息活動都是某種計算，都和其他運(yùn)動形式中的信息活動有某種共性，計算的本質(zhì)是一種模擬。因而有人指出，不能把計算歸結(jié)為符號變換，應(yīng)該弄清形式符號系統(tǒng)和連續(xù)信號處理系統(tǒng)之間的異同［10］?！?/p>

1981年Nobel生理及醫(yī)學(xué)獎得主Sperry的研究表明:“大腦兩半球在功能上有明顯的分工，左半球同抽象思維、象征性關(guān)系和對細(xì)節(jié)的邏輯分析有關(guān)，它具有語言(包括書寫語言)的、理念的、分析的、連續(xù)的和計算的能力，它能說、寫和進(jìn)行數(shù)學(xué)計算，在一般功能方面它主要是分析，猶如計算機(jī)一樣。”“右半球則與知覺和空間有關(guān)，處理單項(xiàng)的事物而不是數(shù)理的排列。它具有音樂的、繪畫的、綜合的、整體性和幾何 － 空間的鑒別能力［11，12］?！?/p>

這些實(shí)驗(yàn)研究結(jié)果，以及包括康托定理、Chaitin定理和歌德爾不完備性定理在內(nèi)的諸多現(xiàn)有理論研究［13］，都為超級計算機(jī)的研究提供了堅實(shí)基礎(chǔ)。

2.1 現(xiàn)存科學(xué)、不同思維方式的復(fù)雜性的一種分層方法

命題1(科學(xué)、思維方式的復(fù)雜性分層方法):各種科學(xué)、思維方式，按信息復(fù)雜性可以歸入下面序列(*)中的某個元素，并相應(yīng)地稱為第某類系統(tǒng)。

這里信息復(fù)雜性的度量，選為該系統(tǒng)基本結(jié)構(gòu)的基數(shù)。

顯然，類型編號高的科學(xué)與思維方式比編號低的信息能力強(qiáng)得多，二者是不能近似相等的。這樣一種劃分，十分類似于兩千多年前老子《道德經(jīng)》“修觀第五十四”中的觀點(diǎn):“故，以身觀身，以家觀家，以鄉(xiāng)觀鄉(xiāng)，以國觀國，以天下觀天下，吾何以知天下之然哉?依此?！崩献釉谶@里提出了一種“分層”和“相似”的認(rèn)識方法論。

老子明確指出:①對于某種復(fù)雜性的客觀世界，應(yīng)該用與之類似的復(fù)雜性工具去研究它，不能使用復(fù)雜性低的工具去研究復(fù)雜性高的問題，即不能“以身觀家”。②客觀世界的復(fù)雜性并不都一樣，它們之間有質(zhì)的差別，“身”和“家”的復(fù)雜性就處在不同的層次。③某個復(fù)雜性層次內(nèi)的事物，有內(nèi)在的相似性，可以根據(jù)這種相似性來研究它們。

命題1可以進(jìn)一步約束為“廣義丘奇－圖靈論題”，或者應(yīng)該更公正地稱為“老子論題”。“廣義丘奇－圖靈論題”既不是丘奇也不是圖靈建立的，甚至他們是反對這種思想的(丘奇－圖靈論題［3］:所有合理的計算機(jī)彼此等價)，而是仿照老子思想建立的。這是將命題1的分層思想運(yùn)用到“可計算性、計算復(fù)雜性”理論領(lǐng)域的結(jié)果。

2.2 超級計算機(jī)分類方法

命題2(老子論題，或稱作廣義丘奇－圖靈論題):任何智能計算機(jī)器，可按其信息復(fù)雜性歸入序列(*)中的某個元素，并相應(yīng)地稱為第某類計算機(jī)器。

這里信息復(fù)雜性的度量，選為該系統(tǒng)基本結(jié)構(gòu)的基數(shù)。并且:

(1)同一編號的不同計算機(jī)模型的能力彼此相當(dāng)，具有某種相似性。

(2)編號大的計算機(jī)比編號小的計算機(jī)，在可解性或計算復(fù)雜性這兩個方面(或其中之一)有本質(zhì)性的提高，彼此并不等價。

(3)同一編號的不同計算機(jī)模型，可以以該編號的復(fù)雜性為上限互相模擬，還可以以不超過該編號的復(fù)雜性模擬編號低的計算機(jī)。反之，編號低的計算機(jī)，只能以“指數(shù)方式”或“指數(shù)的指數(shù)方式”等高的復(fù)雜性模擬編號高的計算機(jī)。

將命題2僅限制在第0類，可以得到原來意義上的丘奇－圖靈論題。

眾所周知，丘奇－圖靈論題只是一種直觀信念，不能加以證明［3］。類似的問題還有AI中含混性極強(qiáng)的關(guān)于智能判斷的“圖靈測試”:它測試的是“符號能力”，但人類的許多智能是“非符號”的。時至今日，這些信念實(shí)際上已經(jīng)開始成為人類智能、智能機(jī)器研究的束縛。

2.3 一些直觀解釋

現(xiàn)有的數(shù)字計算機(jī)，即目前最流行的計算機(jī)，是第0類計算機(jī)。它以有限個0、1字符串作為基本計算單元。

模擬系統(tǒng)(如模擬計算機(jī)［14］)，是第一類計算機(jī)。它以實(shí)數(shù)作為基本計算單元。由于模擬計算機(jī)的靈活性、計算精度等限制，目前已經(jīng)很少使用。當(dāng)前熱點(diǎn)研究的量子計算機(jī)［15］，也是第一類計算機(jī)。1個量子位可以出現(xiàn)從0到1數(shù)值的波狀重疊，因此一個n位量子位可以同時存儲2n個不同的數(shù)值，因此量子計算可以通過一次操作產(chǎn)生個2n結(jié)果。

人眼的視覺功能，是第二類復(fù)雜性?！爱?dāng)大量的生物物理機(jī)制以極復(fù)雜的方式相互作用時，可以認(rèn)為是對神經(jīng)元的輸入進(jìn)行一種非線性計算。而且在不同狀態(tài)下，同一神經(jīng)元可以對輸入信息進(jìn)行幾種不同的計算?！薄叭藗兒苋菀椎凸郎镉嬎愕碾y度及復(fù)雜性。……真正令人驚奇的是:即使是一些相對低層次的計算(如將兩只眼睛的信息結(jié)合在一起形成雙眼視覺、顏色計算、運(yùn)動計算、外緣檢測等等)，也有難以置信的復(fù)雜［10］?！睅缀喂鈱W(xué)計算系統(tǒng)，如現(xiàn)有的“4f系統(tǒng)”［16，17］，屬于第二類計算機(jī)。

一個直觀的對比:電影膠片(第二類)，比模擬電視(第一類)清晰度高;模擬電視比數(shù)字電視(第0類)清晰度高。這就是日本首先采用模擬電視進(jìn)行高清電視研究的原因;由于目前沒有高精度的模擬計算，所以日本人沒有成功。美國人的高清數(shù)字電視，是采用無損、有損壓縮，以及采用巨復(fù)雜硬件后獲得的有限效果。眾所周知，傳統(tǒng)膠片攝影的清晰度，明顯高于現(xiàn)有的數(shù)字?jǐn)z影。

進(jìn)一步的推斷:人腦的常規(guī)復(fù)雜性為h，社會運(yùn)動的復(fù)雜性為i，各星際文明間融合的復(fù)雜性為b。這是人類現(xiàn)有文化能夠顯式想象出的6個復(fù)雜性層次［5］。

3 “P對NP”的一個答案

一般認(rèn)為，《集合論》是整個現(xiàn)代數(shù)學(xué)的基礎(chǔ)，至多“范疇論”除外。康托定理在計算復(fù)雜性方面的一個具體表現(xiàn)或變形，就是著名的7個Millennium Problems中的第4 個:P vs NP(P 對 NP)［18］?！癙 對 NP”還是2005年美國著名的Science雜志公布的當(dāng)前人類最需要解決的前25個難題中的第19個(The Top 25:What are the limits of conventional computing?)［19］。

“P對NP”的介紹，請看文獻(xiàn)［20～23］等。這里首先回顧筆者1995年報告內(nèi)容的要點(diǎn)［24］，之后介紹其后的相關(guān)認(rèn)識。

這里“P對NP”是原本意義上的問題。對于實(shí)數(shù)環(huán)上的計算機(jī)(第一類計算機(jī))，1989年由著名數(shù)學(xué)家Steve Smale等人建立了其上的計算復(fù)雜性理論，并且構(gòu)造了相應(yīng)的“P對 NP”［25］。沿著這條思路，我們還可以建立第二類計算機(jī)的可計算性、計算復(fù)雜性理論等。但本文不再進(jìn)行這些具體的工作。

3.1 1995年報告要點(diǎn)回顧

記DTM為確定型圖靈機(jī)(deterministic Turing machine);NDTM 為“非確定型圖靈機(jī)”(non－deterministic Turing machine)。示意圖分別如圖2、圖3所示。

(1)“P對NP”不能被直接證明。它實(shí)際上是3個問題的合成:

①對于NDTM，PA=NPA;

②對于DTM，PB≠NPB;

③“P對NP”具有獨(dú)立性，不指明在那種計算機(jī)理論里進(jìn)行研究。

(2)對于DTM，PB≠NPB，是通常研究的核心。

從數(shù)學(xué)研究的整體方法看，“P對NP”是屬于“數(shù)”的范圍。既然在“數(shù)”的方法下沒有獲得明確答案，就應(yīng)該轉(zhuǎn)移到“形”的方法進(jìn)行研究。對于第一個NPC，即布爾可滿足性問題(SAT，boolean satisfiability problem)，不難發(fā)現(xiàn)，在圖論模型下，2SAT一定是平面圖，3SAT及4SAT則可能包含Kuratowski圖K3，3，是立體圖。而5SAT可能包含 Kuratowski圖 K5和 K3，3，也是立體圖。

這種數(shù)、形結(jié)合的研究思路，不僅來自恩格斯的數(shù)學(xué)定義;還直接受到笛卡爾采用代數(shù)來研究幾何的方法的啟發(fā):解析幾何的創(chuàng)立。

(3)在無窮化版本下，NPI的存在性，就是“連續(xù)統(tǒng)假設(shè)CH”［4］:可數(shù)無窮基數(shù)a和連續(xù)統(tǒng)基數(shù)c之間是否存在一個其他的無窮基數(shù)。

(4)超級計算機(jī)分類理論(見本文2.2超級計算機(jī)分類方法)。

3.2 其后的認(rèn)識

(1)用旅行推銷員問題(TSP，travelling salesman problem)，可以比用SAT更直觀地說明“P對NP”的關(guān)系。所有頂點(diǎn)度數(shù)為2的TSP，稱為2TSP。顯然，2TSP只能是一個回路，或者若干不相交的回路。因此2TSP是平面圖。相反，3TSP或更高的各TSP，可能包含與K5或K3，3同胚的子圖，不是平面圖。

(2)在無窮版本下的非確定型圖靈機(jī)NDTM，不是平面圖。它包含至少與K3，3同胚的子圖。

(3)完全證明:“P對NP”關(guān)系的多樣合理答案，啟發(fā)人們用“完全證明”作為未來數(shù)學(xué)證明的新標(biāo)準(zhǔn)。由于任何證明都是依賴特定的、未加證明的邏輯系統(tǒng)，因此所有“證明”都是相對的［4］。

一個“完全證明”是指，證明一個命題，需要同時給出下面的3種情況:

①在某個指定的邏輯系統(tǒng)或數(shù)學(xué)系統(tǒng)，該命題成立。即被證明。

②在另外某個指定的邏輯系統(tǒng)或數(shù)學(xué)系統(tǒng)，該命題不成立。即被否證。

③如果沒有指明所采用的邏輯系統(tǒng)或數(shù)學(xué)系統(tǒng)，該命題既不成立，也不不成立。即獨(dú)立性。

“完全證明”并非一種實(shí)質(zhì)上的新發(fā)明，而是將現(xiàn)有大量具體的數(shù)學(xué)證明實(shí)踐，進(jìn)行理性提煉得到的看法。即從現(xiàn)有的大量的“自發(fā)”，到“自覺”的一種轉(zhuǎn)變。歌德爾不完備性定理、Chaitin定理，對這種“自覺”的提煉提供了重要的數(shù)學(xué)基礎(chǔ)保證。

3.3 對“四色定理”的個人看法

康托定理在地圖繪制著色方面的一個具體表現(xiàn)，就是著名的“四色定理”。因?yàn)椤八纳孪搿币呀?jīng)被計算機(jī)證明為成立。

一般地，對于n個相異元素，最多可以形成2n種獨(dú)立關(guān)系。因此，對于“點(diǎn)”，只有0個自由度，最多需要20=1種顏色就可以完全區(qū)分;對于直線，有1個自由度，最多需要21=2種顏色就可以完全區(qū)分;對于平面，有2個自由度，最多需要22=4種顏色就可以完全區(qū)分;對于立體塊，有3個自由度，最多需要23=8種顏色就可以完全區(qū)分。

4 第二類數(shù)學(xué)初步與第二類計算機(jī)的直觀概念

直觀地，自然數(shù)在通常意義下的加減乘除，構(gòu)成有理數(shù)域，這里稱為第0類數(shù)域。一個實(shí)數(shù)可以看成至多可數(shù)無窮多個(a個)自然數(shù)的序列;實(shí)數(shù)在通常意義下的加減乘除，構(gòu)成實(shí)數(shù)域，這里稱為第一類數(shù)域。一條“幾何曲線”可以看成c個實(shí)數(shù)的序列;本文將定義幾何曲線的加減乘除，構(gòu)成第二類數(shù)域。

“幾何曲線”在本文特指“定位實(shí)曲線”。其含義為:形狀相同的曲線，若在實(shí)平面上的位置不同的話，則被認(rèn)為是不同的曲線。這樣一條曲線，可以抽象為一個f數(shù)或第二類數(shù)。

4.1 “第二類數(shù)”——f數(shù)

定義3 f數(shù)(或第二類數(shù)):定義一條“定位實(shí)曲線”為一個f數(shù)?；蛘哒f，一個長度不超過c的實(shí)數(shù)序列，構(gòu)成一個f數(shù)。

全體f數(shù)構(gòu)成集合F。

注釋:從數(shù)的歷史看，人們在古希臘時就已經(jīng)抽象出“自然數(shù)”，這是“第0類”數(shù)。后來，人們發(fā)現(xiàn)了像這樣的本質(zhì)上比自然數(shù)復(fù)雜得多的數(shù)。為此，據(jù)說Hippasus惹怒了Pythagoras學(xué)派的眾學(xué)者。他們把Hippasus扔到大海里，以消除這一發(fā)現(xiàn)的“壞影響”［26］。隨著歷史的進(jìn)步，無理數(shù)的合理性已不容懷疑。于是，人們將“無理數(shù)(實(shí)數(shù))”定義為一個有理數(shù)的序列。例如，可用{1，1.4，1.41，1.414，……}去逼近(這是 G.Cantor的方法)，或?qū)ⅰ皩?shí)數(shù)定義為一切有理數(shù)的分劃之集合 R=，(=Φ)”(R.Dedekind，1872 年)［4］。簡言之，分割有理數(shù)導(dǎo)致了實(shí)數(shù)。實(shí)數(shù)系是完備的，在其中再作分劃或再作柯西序列，都不會得到新的數(shù)。實(shí)數(shù)與直線上的點(diǎn)可以一一對應(yīng)，在這個意義上稱實(shí)數(shù)系具有完備性，也因此稱實(shí)數(shù)系為連續(xù)統(tǒng)［3，4］。

那么，現(xiàn)在的問題是，由于實(shí)數(shù)系的完備性，對實(shí)數(shù)的分劃不再導(dǎo)致新的數(shù)。這提示人們，反其道而行之，對實(shí)數(shù)的擴(kuò)充可得到一種新的“數(shù)”——基數(shù)為f的數(shù)“f數(shù)”，即本處的定義3。而且，這樣的數(shù)具有線性序，可構(gòu)成有序的阿基米德域。它完全具備數(shù)的要求。

定理4(f數(shù)中的線性序≤):根據(jù)良序定理［2～4］，每一個集合都能良序(線性序)，即，對于?集合A，?P(A)－{φ}上的一個選擇函數(shù)，它可良序A。

f數(shù)間的線性序可按字典序建立［2，4］。

下文記 x，y，z，…∈F。

(1)由于x，y，z，…均為有序?qū)崝?shù)序列，分別取其最左端元素(為兩個實(shí)數(shù))，按通常意義下的“≤”確定x，y間的序關(guān)系。若x的最左端元素≤y的，則定義 x≤y，否則，定義 y≤x。

(2)若x，y中的最左端元素相同，則比較它們的次左端元素，可依此確定它們之間的序關(guān)系。

(3)若x，y的元素數(shù)目不等，如x實(shí)數(shù)點(diǎn)的數(shù)目小于y的，且x是y的子序列，則定義x≤y。

證明:不難驗(yàn)證這樣確立的序關(guān)系滿足“自反性”、“反對稱性”、“傳遞性”及“任給 x，y，x≤y或y≤x總有一個成立”，即全體f數(shù)構(gòu)成一個線性序。

由于f數(shù)為不超過c個實(shí)數(shù)點(diǎn)的序列，因此，對任意2個f數(shù)，可按字典序的方式確定其間的序關(guān)系。例如，按通常意義下的“≤”確定序關(guān)系。

例如，為直觀，令 x={e，2，π}，y={7，2，π}，z={e，2}，對于 x，y，因?yàn)?e＜7，故 x≤y;對于 y，z，因?yàn)?e＜7，故 z≤y;對于 x，z，因?yàn)?e=e，2=2，而且 z包含在x中，故 z≤ x。x，y，z間的序關(guān)系為 z≤x≤y。而且有，因?yàn)橛衵≤x以及x≤y，所以有z≤y。

定理5:全體f數(shù)(或第二類數(shù))集合上的域F0。

下文記 x，y，z，…∈F。

容易驗(yàn)證下述關(guān)系成立，即F集上有一個域F0。

(1)x+y=y+x

(2)x+(y+z)=(x+y)+z

(3)0+x=x+0=x

(4)存在 －x，使 x+(－x)=(－x)+x=0

(5)x·y=y·x ，x·(y·z)=(x·y)·z

(6)x·(y+z)=x·y+x·z

(7)存在1≠0，使1·x=x·1=x

(8)對每個 x≠0，都有 x－1，使 x·x－1=x－1·x=1

證明:加法、乘法為通常意義下的函數(shù)加法、乘法。即x+y定義為實(shí)平面上橫坐標(biāo)相同時的x、y的縱坐標(biāo)的實(shí)數(shù)加法。x·y也作類似地定義。值得注意的是，為方便，其中0元素為全體橫軸;1元素為橫軸的平行線，位于橫軸上方，距離為1。

由定理4、5可知，全體f數(shù)(或第二類數(shù))集合具備數(shù)的基本性質(zhì)，即線性序，而且其上可建立阿基米德有序域。故稱這個域?yàn)閿?shù)域F0。相應(yīng)的數(shù)稱為f數(shù)(或第二類數(shù))。

注釋:第二類數(shù)學(xué)是我們首次提出來的，目前尚未見到相同或類似的工作。

數(shù)域F0由“二維實(shí)平面上的通常意義下的定位實(shí)曲線的加法、乘法”構(gòu)成。由于一維實(shí)空間可以和n維實(shí)空間建立一一對應(yīng)關(guān)系［3］，因此選二維實(shí)空間，完全是為了最直觀、最方便。顯然，“n維實(shí)空間上的通常意義下的定位實(shí)曲線(或曲面)的加法、乘法”，也構(gòu)成了不同維數(shù)的空間上的元素的基數(shù)為f的域，并且它們和域F0是等價的。它們的信息復(fù)雜性都是f，即第二類的。

4.2 “第二類計算機(jī)”的直觀概念

定義6(第二類計算機(jī)):能夠把“定位實(shí)曲線作為基本單元”進(jìn)行加減乘除等運(yùn)算的計算機(jī)，定義為第二類計算機(jī)?；蛘哒f，第二類計算機(jī)是以“定位實(shí)曲線”，即f數(shù)為基本單元進(jìn)行運(yùn)算的計算機(jī)。

人類的視覺功能、信息光學(xué)中的4f系統(tǒng)，是第二類計算機(jī)的一些實(shí)際表現(xiàn)。

第二類計算機(jī)對復(fù)雜問題的求解能力有質(zhì)的提高。例如，決定長度為n的Presburger命題的真?zhèn)涡?，DTM需要至少“指數(shù)的指數(shù)次冪”方式22kn的時間;量子計算機(jī)需要至少“指數(shù)次冪”方式2kn的時間;第二類計算機(jī)只需要O(n)的時間。這里，k為某個常數(shù)。

關(guān)于第二類計算機(jī)的可計算性，還需要更多的研究。“停機(jī)問題”是邏輯系統(tǒng)的局限性，在第二類計算機(jī)里仍然存在。

圖像識別(人臉、指紋等)、運(yùn)動物體定位與跟蹤等，在第二類計算機(jī)上的速度將得到飛躍性提高，這是它在戰(zhàn)爭中有效應(yīng)用的管窺之一。

4.3 一些推論

推論7(高精度實(shí)數(shù)實(shí)現(xiàn)方法):現(xiàn)有的數(shù)字計算機(jī)，實(shí)際上是模擬量的特殊使用。一般地，將一個連續(xù)變化的實(shí)數(shù)量，人為劃分為2種狀態(tài)，盡管這大幅度降低了實(shí)數(shù)的能力，但卻獲得了數(shù)字值0、1的高精度、高可靠性實(shí)現(xiàn)。類似地，將“定位實(shí)曲線”(f數(shù))人為劃分為c種狀態(tài)，盡管這大幅度降低了f數(shù)的能力，但卻獲得高精度、高可靠性的實(shí)數(shù)實(shí)現(xiàn)。

因此，第二類計算機(jī)除了可以直接進(jìn)行一定精度的f數(shù)計算外，還可以經(jīng)過特殊處理退化為高精度、高可靠性的模擬計算機(jī)。

5 第二類計算機(jī)發(fā)展歷史簡要回顧

由于作者水平，這里回顧的只是作者知道的。相信還有其他重要觀點(diǎn)，未能在這里出現(xiàn)。

(1)1878年的康托定理，是導(dǎo)致超級計算機(jī)分類的基本理論。

(2)大數(shù)學(xué)家 J.H.Poincaré(1854－1912)在1887年獲得瑞典和挪威國王Oscar II的懸賞征答的“天體力學(xué)中的n體問題”獎的時候，就發(fā)現(xiàn)在萬有引力作用下的多體運(yùn)動問題，軌道的數(shù)量超過實(shí)數(shù)的數(shù)目c。這其實(shí)不難理解，天體軌道的(曲線的)數(shù)目可以達(dá)到f?！疤祗w力學(xué)中的n體問題”，是著名“三體問題”的一般形式。

(3)在《集合論》中，對于包含“空集?”和“全集1”的集合，以及定義在其上的“對稱減”和“交”(分別作為“加法”和“乘法”)，可以構(gòu)成一個環(huán)［2，27］。令 x，y，z，… 該集合中的元素，并定義對稱減 x+y=(x－y)∪(y－x)，交 x·y=x∩y兩種運(yùn)算，則有下述環(huán)公理滿足:

這是一個一般的環(huán)［2，27］。顯然，將 x，y，z，...作不同的復(fù)雜性的解釋，可以得到各種復(fù)雜性的環(huán)。若將x，y，z，...解釋成“幾何曲線”，可以得到一個第二類復(fù)雜性的環(huán)R0。

(4)K.G?del說過:沒有一個在特定分辨率層次上形成的知識系統(tǒng)，能夠完全解釋那個層次，必須具有一個高層元知識才能完全解釋它。然而，當(dāng)我們著手去構(gòu)造這個更一般的元知識時，它也要求更高一層的元－元知識去解釋它［28］。

(5)幾何光學(xué)計算。如信息光學(xué)中的4f系統(tǒng)［16，17］，就是現(xiàn)有的典型“第二類計算機(jī)”。

(6)在20世紀(jì)80年代，陳霖院士提醒我們:“在各個歷史時期，由于對人腦的奧秘一無所知或所知甚少，人腦總是被比擬成那個時期最先進(jìn)的人類的技術(shù)成果。遠(yuǎn)的不說(比如，把人腦比做水力機(jī)械，比做自動鐘表，比做電話交換機(jī)，等等)，在這里我們只談一下50年代初期，隨著維納控制論的創(chuàng)立，把人腦比做控制和通信系統(tǒng)中的通訊道的類比［12］?！薄巴?fù)湫再|(zhì)檢測的實(shí)驗(yàn)支持這樣的論點(diǎn):視覺整體像的變換，而不是離散符號操作的計算，可能在視覺過程中起著重要作用［12］?！?/p>

(7)錢學(xué)森認(rèn)為［12］:“思維學(xué)又可以細(xì)分為抽象(邏輯)思維學(xué)、形象(直感)思維學(xué)和靈感(頓悟)思維學(xué)3個部分?！薄叭藗兂Ｕf語言是思維的工具，所以語言先于思維?，F(xiàn)在對形象思維的研究表明，只是抽象思維靠語言，形象思維不靠語言，形象的感知是只可意會，不可言傳的。幼兒心理學(xué)也證明，形象思維先于語言，也先于抽象思維。”“以相關(guān)函數(shù)的分布來識別圖形，這個方法計算量非常大，顯然不是人腦用的方法，人腦識別圖形幾乎是瞬時的!”“如果邏輯思維是線形的，形象思維是二維的，那么靈感思維好象是三維的?！薄瓣P(guān)于視覺的認(rèn)知心理研究，陳霖同志認(rèn)為，圖象或者模式識別是跟圖形象的拓?fù)鋵W(xué)有關(guān)系，是一個整體分析問題。”

(8)盡管實(shí)際上早就存在模擬計算機(jī)［14］，但有關(guān)的復(fù)雜性理論研究卻明顯滯后。1989年才由著名數(shù)學(xué)家Steve Smale等人建立實(shí)數(shù)環(huán)上的計算復(fù)雜性理論［25］。它是對DTM的本質(zhì)性擴(kuò)充。粗略地說，DTM是第0類計算機(jī);Smale等人建立的是第一類計算機(jī)的復(fù)雜性理論。

自然地，再往下就是建立第二類計算機(jī)理論。

(9)近年筆者發(fā)現(xiàn)，1965年L.Zadeh建立的“模糊集合理論”，是現(xiàn)有的“第二類數(shù)學(xué)”的退化形式。不難發(fā)現(xiàn)，隸屬函數(shù)為連續(xù)函數(shù)的模糊集合，本質(zhì)是對“一條曲線”的整體掌握。因此這樣的模糊集合，是第二類數(shù)的退化形式。因此，模糊控制成為實(shí)用中最有效的兩種控制方法之一，并被近年美國人用于火星自動車的控制，有其必然性。這是“第二類數(shù)學(xué)”能力勝過現(xiàn)有有理數(shù)、實(shí)數(shù)理論的直接實(shí)踐表現(xiàn)。

(10)近年筆者發(fā)現(xiàn)，大家都熟悉的幾何學(xué)，都是以特殊形式的曲線為基本元素的。即:幾何圖形，是f數(shù)的一種具體解釋。所以幾何學(xué)也是“第二類數(shù)學(xué)”的特殊形式、退化形式。

1872年F.Klein提出了數(shù)學(xué)史上著名的埃爾朗根綱領(lǐng)(Erlangen program)，他把到當(dāng)時為止已發(fā)現(xiàn)的所有幾何統(tǒng)一在變換群論觀點(diǎn)之下，明確地給出了幾何的一種新定義，把幾何定義為一個變換群之下的不變性質(zhì)［4］。埃爾朗根綱領(lǐng)實(shí)質(zhì)的一種第二類數(shù)學(xué)理解:某些f數(shù)，可以構(gòu)成群。

6 結(jié)語

根據(jù)集合論中康托定理等，定義“定位幾何曲線”為f數(shù)，并建立了相應(yīng)的數(shù)域F0。這是對實(shí)數(shù)、實(shí)數(shù)域的一種本質(zhì)性擴(kuò)充。以f數(shù)為基本運(yùn)算單元的計算機(jī)，是第二類計算機(jī)。人類的視覺、信息光學(xué)中的4f系統(tǒng)，就是第二類計算機(jī)的一些實(shí)際表現(xiàn)。

未來的第二類計算機(jī)，除了可以直接進(jìn)行“定位幾何曲線”的一定精度計算外，還可以在特定的退化情況下構(gòu)成高精度、高可靠性的模擬計算機(jī)。第二類計算機(jī)是比現(xiàn)在熱點(diǎn)研究的量子計算機(jī)能力更強(qiáng)的計算機(jī)。

［1］DYSON F.A Meeting with Enrico Fermi［J］.Nature，2004，427(6972):297－297.

［2］KURATOWSKI K，MOSTOWSKI A.Set Theory［M］.Amsterdam:North－Holland Publishing Company，1976.

［3］王憲鈞.數(shù)理邏輯引論［M］.北京:北京大學(xué)出版社，1982.

［4］HAZEWINKEL M.Encyclopaedia of Mathematics［M］.Dordrecht:Kluwer Academic Publishers，2001.［DB/OL］，http://eom.springer.de/.

［5］楊正瓴，林孔元.人類智能模擬的“第二類數(shù)學(xué)(智能數(shù)學(xué))”方法的哲學(xué)研究［J］.哲學(xué)研究，1999(4):44－50.

［6］CHAITIN G J.Information－theoretic Computational Complexity［J］.IEEE Transactions on Information Theory，1974，20(1):10－15.

［7］HARARY F.Graph Theory［M］.Massachusetts:Addison－Wesley，1969.

［8］楊正瓴.人腦有多復(fù)雜?［J］.百科知識，1997(7):39－40.

［9］楊正瓴.人腦復(fù)雜性的估計及其哲學(xué)意義［M］//盧繼傳.中國新時期社會科學(xué)成果薈萃.北京:中國經(jīng)濟(jì)出版社，1999.

［10］國家自然科學(xué)基金委員會.計算機(jī)科學(xué)技術(shù)［M］.北京:科學(xué)出版社，1994.

［11］SPERRY R.Some Effects of Disconnecting the Cerebral Hemispheres［J］.Science，1982，217(4566):1223－1226.

［12］錢學(xué)森.關(guān)于思維科學(xué)［M］.上海:上海人民出版社，1986.

［13］GRABINER J V.Computers and the Nature of Man［J］.Bulletin(New Series)of the American Mathematical Society，1986，15(2):113－126.

［14］中國大百科全書·自動控制與系統(tǒng)工程卷［M］.北京:中國大百科全書出版社，1991.

［15］Encyclopedia Britannia［DB/OL］.［2011－02－24］.http://www.britannica.com/.

［16］宋菲君.從波動光學(xué)到信息光學(xué)［M］.北京:科學(xué)出版社，1992.

［17］FEDUS K，BOUDEBS G，LEBLOND H.Degenerate Multiwave Mixing Inside a 4f Imaging System in Presence of Nonlinear Absorption［J］.Applied Physics B，2010，100(4):827－831.

［18］THE CLAY MATHEMATICS INSTITUTE.P vs NP Problem［EB/OL］.［2011－02－24］.http://www.claymath.org/millennium/P_vs_NP/.

［19］SEIFE C.What are the Limits of Conventional Computing?［J］.Science，2005，309(5731):96.

［20］楊正瓴.密碼學(xué)與非確定型圖靈機(jī)［J］.中國電子科學(xué)研究院學(xué)報，2008，3(6):558－562.

［21］COOK S.The Importance of the P Versus NP Question［J］.Journal of the ACM，2003，50(1):27－29.

［22］ALLENDER E.A Status Report on the P Versus NP Question［J］.Advances in Computers，2009，77:117－147.

［23］FORTNOW L.The Status of the P Versus NP Problem［J］.Communications of the ACM，2009，52(9):78－86.

［24］楊正瓴.從NP結(jié)構(gòu)到超級計算機(jī)分類理論［R］.天津大學(xué)百年校慶研究生院學(xué)術(shù)報告會(一等獎?wù)撐?和天津大學(xué)百年校慶自動化系學(xué)術(shù)報告會，1995.

［25］BLUM L，SHUB M，SMALE S.On a Theory of Computation and Complexity over the Real Numbers［J］.Bulletin(New Series)of the American Mathematical Society，1989，21(1):1－47.

［26］KLINE M.Mathematical Thoughts from Ancient to Modern［M］.New York:Oxford University Press，1972.

［27］GRATZER G.Universal Algebra［M］.New York:Springer－Verlag，1979.

［28］張鈸.近十年人工智能的進(jìn)展［J］.模式識別與人工智能，1995，8(增刊):1－9.