邏輯深度與元胞自動(dòng)機(jī)計(jì)算機(jī)之父馮·諾伊曼對(duì)復(fù)雜性問題研究方法的貢獻(xiàn)及其影響

邏輯深度與元胞自動(dòng)機(jī)計(jì)算機(jī)之父馮·諾伊曼對(duì)復(fù)雜性問題研究方法的貢獻(xiàn)及其影響

計(jì)算機(jī)之父馮諾伊曼的自動(dòng)機(jī)理論經(jīng)歷了對(duì)“復(fù)雜性”的研究。他對(duì)復(fù)雜自動(dòng)機(jī),尤其是人的神經(jīng)系統(tǒng),未來的巨型計(jì)算機(jī)系統(tǒng)十分感興趣,他想要建立復(fù)雜系統(tǒng)的邏輯組織理論,并相信這樣的理論是建造大型計(jì)算機(jī)的最本質(zhì)的前提?！霸?0世紀(jì)40年代早期,計(jì)算系統(tǒng)的復(fù)雜性還沒有被清楚地認(rèn)識(shí)。大多數(shù)早期計(jì)算機(jī)研究者的眼光沒有超出元件設(shè)計(jì)、硬件工程的細(xì)節(jié)。馮·諾伊曼對(duì)計(jì)算機(jī)的發(fā)展產(chǎn)生重大影響的原因之一是他對(duì)計(jì)算系統(tǒng)復(fù)雜性的認(rèn)識(shí)以及從不同方面對(duì)復(fù)雜性的貢獻(xiàn)?！?算法信息的提出馮·諾伊曼提出了度量復(fù)雜性———“邏輯深度”(Logicaldepth)的概念。在比較自然和人工自動(dòng)機(jī)的可靠性與復(fù)雜性時(shí),他認(rèn)為自然自動(dòng)機(jī)和人工自動(dòng)機(jī)的一個(gè)不同之處是計(jì)算組織不同,即自然自動(dòng)機(jī)是并行運(yùn)行而人工自動(dòng)機(jī)序列運(yùn)行的。在這里,他提出了一個(gè)計(jì)算的“邏輯深度”概念。一個(gè)計(jì)算包括許多基本邏輯步驟(開關(guān)、延遲),每步的結(jié)論都依賴于前面的步驟。馮·諾伊曼把每個(gè)依賴于前面步驟組成的序列稱為“計(jì)算鏈”。計(jì)算的邏輯深度是它的最長的計(jì)算鏈的邏輯步驟的數(shù)字。由于計(jì)算機(jī)的高速度高效率,計(jì)算機(jī)常被用來完成極長邏輯深度的計(jì)算,最后的結(jié)果錯(cuò)誤需限定在很小的概率內(nèi),這就要求每個(gè)邏輯步驟具有高度可靠性,所以馮·諾伊曼認(rèn)為,自動(dòng)機(jī)邏輯中的失敗的可能性促使人們?nèi)タ紤]計(jì)算度的大小。數(shù)理邏輯的通常方法是去考慮一個(gè)自動(dòng)機(jī)器是否能在有限步驟內(nèi)完成某些任務(wù),無論這個(gè)數(shù)字有多大,但是現(xiàn)實(shí)是計(jì)算數(shù)字越大,機(jī)器在計(jì)算中出錯(cuò)的可能性就越大。馮·諾伊曼沒有建議如何去構(gòu)造一個(gè)計(jì)算大小的理論,但“邏輯深度”概念的提出對(duì)度量計(jì)算的復(fù)雜性非常具有啟發(fā)性意義:要準(zhǔn)確把握復(fù)雜性的概念,我們需要考慮如何度量復(fù)雜性的問題。馮·諾伊曼的后繼者勃克斯后來對(duì)這個(gè)理論做了研究,認(rèn)為這個(gè)理論是建立在“計(jì)算的量”這個(gè)量的概念上,考慮到計(jì)算的深度(邏輯深度)和寬度(并行的量),計(jì)算的量的理論和錯(cuò)誤的可能性必須包括連續(xù)數(shù)學(xué)和離散數(shù)學(xué)。沿著這個(gè)思路,在20世紀(jì)60年代,俄羅斯數(shù)學(xué)家柯爾莫哥洛夫(A.N.Kolmogorov)、美國數(shù)學(xué)家蔡廷(G.Chaitin)和索洛莫洛夫(R.Solomonoff)又分別提出“算法信息量”的概念。算法信息量是指一種計(jì)算機(jī)程序的長度。算法信息量的提出是基于這樣的思想:為了確定一個(gè)具體的信息(比特)串的復(fù)雜性,先考慮一臺(tái)理想的計(jì)算機(jī)(圖靈機(jī)),它具有無限的存儲(chǔ)能力;然后針對(duì)這一信息串,尋找一個(gè)計(jì)算程序,讓這個(gè)程序在這臺(tái)理想計(jì)算機(jī)上運(yùn)行到打印出這個(gè)信息串,最后停機(jī)。一個(gè)能夠生成該信息串的最短程序的長度便是它的算法信息量。20世紀(jì)80年代早期,美國物理學(xué)家貝內(nèi)特(GBen-nett)為了刻畫計(jì)算的復(fù)雜性,又提出了一個(gè)考慮到信息與付出這兩個(gè)方面的概念:“邏輯深度”(Logi-caldepth),不過這個(gè)概念與馮·諾伊曼提出的邏輯深度概念的內(nèi)涵不太一樣。貝內(nèi)特把對(duì)一個(gè)信息串或數(shù)據(jù)集的最似真說明等同于能產(chǎn)生該信息串或數(shù)據(jù)集的最短程序,然后再考慮這一程序的計(jì)算復(fù)雜性,他把從運(yùn)行該程序開始到產(chǎn)生信息串所需的付出也叫做“邏輯深度”。貝內(nèi)特的邏輯深度所指的是比特串、計(jì)算機(jī)程序和邏輯運(yùn)算。邏輯上深的信息串具有更復(fù)雜的結(jié)構(gòu)和行為。2計(jì)算機(jī)數(shù)值分析的目的和方法馮·諾伊曼是現(xiàn)代數(shù)值方法的創(chuàng)始人。19世紀(jì)早期,K.F.高斯(Gauss)對(duì)其進(jìn)行了全面研究,在他的研究基礎(chǔ)上,19世紀(jì)到20世紀(jì)早期發(fā)展應(yīng)用數(shù)值方法是為了解決線性方程的小系統(tǒng)、倒置小矩陣、近似組合以及一般微分方程。馮·諾伊曼看到了計(jì)算機(jī)在無人干涉的情況下快速執(zhí)行長序列運(yùn)算的能力,并把此作為擴(kuò)大數(shù)值技術(shù)應(yīng)用領(lǐng)域的機(jī)遇。這個(gè)機(jī)遇包括研究線性方程大系統(tǒng)、更復(fù)雜的系統(tǒng),偏微分方程以及它們?cè)诮?jīng)典物理學(xué)、量子物理學(xué)、生物學(xué)、地球科學(xué)中的應(yīng)用。馮·諾伊曼早在1940年就知道數(shù)值方法將使計(jì)算機(jī)成為時(shí)髦有效地科學(xué)工具,他也知道計(jì)算機(jī)將引起對(duì)數(shù)值分析這門學(xué)科的重新研究。他在設(shè)計(jì)IAS計(jì)算機(jī)的同時(shí)開始對(duì)數(shù)值分析進(jìn)行思考,這個(gè)早早的開端使他成為對(duì)新計(jì)算機(jī)方向的數(shù)值分析感興趣的早期科學(xué)家之一。他的一些結(jié)論持續(xù)影響了40年,蒙特-高利法(MonteGarlo)和線性算法是很好的例子;其它一些例子———譬如為解決PDES和大型矩陣的方法,調(diào)整沖擊(Accomodationshocks)的方法以及解決數(shù)值穩(wěn)定性分析法———他的工作雖然被后人大大地超越,但他的工作是第一步,他使這些問題的重要性成為人們注意焦點(diǎn),并建設(shè)性地提出了解決方法。馮·諾伊曼認(rèn)為數(shù)值方法的變化主要目的是為了讓計(jì)算機(jī)更有效、更可靠的運(yùn)行。計(jì)算機(jī)在一些關(guān)鍵方面與臺(tái)式計(jì)算器及穿卡裝置(Punched-cardequipment)這些先前進(jìn)行數(shù)值分析的機(jī)器不同。計(jì)算機(jī)執(zhí)行乘法運(yùn)算是手動(dòng)方法的105倍,但在存儲(chǔ)數(shù)據(jù)、指令、中間計(jì)算結(jié)果的能力上嚴(yán)重地受到限制。而穿卡機(jī)卡片上可以無限制地儲(chǔ)存大量信息,系統(tǒng)也非?？煽?但高速計(jì)算機(jī)裝置中只能儲(chǔ)存20到150個(gè)數(shù)字。對(duì)數(shù)值問題的復(fù)雜性以及計(jì)算裝置的速度的分析令馮·諾伊曼和戈德斯汀(Godstine)相信偏微分方程、組合方程以及線性方程系統(tǒng)的新基礎(chǔ)將被打破,但他們又擔(dān)心數(shù)值穩(wěn)定性問題———也就是,結(jié)果錯(cuò)誤的積累與放大———將使過去150年數(shù)值方法發(fā)生改變成為必然。在1946年的報(bào)告《論巨型計(jì)算機(jī)的原則》中,馮·諾伊曼和戈德斯汀為計(jì)算機(jī)數(shù)值分析法列出了研究日程,這個(gè)研究工作從他們開始研究計(jì)算機(jī)起一直到馮·諾伊曼患癌癥去世。倒置矩陣與解決線性方程系統(tǒng)的相關(guān)問題在數(shù)學(xué)中是非常普通的問題。在20世紀(jì)20年代,有許多種方法用于解決這個(gè)問題,但這些方法僅對(duì)于方程的小系統(tǒng)以及低階矩陣,對(duì)小于20級(jí)的矩陣有用,是因?yàn)槭艹朔ㄟ\(yùn)算步驟的限制當(dāng)時(shí)的計(jì)算只能用鉛筆和紙或臺(tái)式計(jì)算器。20世紀(jì)30年代,情況有所改變,主要是因?yàn)閮蓚€(gè)原因。哥倫比亞大學(xué)的WallaceEcket、英國國家年歷辦公室主任JComrie以及其他人主張穿卡分類與列表裝置可有效地用于解決科學(xué)問題,用這個(gè)裝置緩解了乘法運(yùn)算步驟的限制,于是線性系統(tǒng)規(guī)模問題趨于解決。同時(shí),科學(xué)正需要找到解決大型問題的方法———例如,在天文學(xué)以及飛機(jī)設(shè)計(jì)的動(dòng)力分析中對(duì)電子工程的網(wǎng)絡(luò)分析、對(duì)農(nóng)業(yè)與心理學(xué)的統(tǒng)計(jì)分析以及對(duì)機(jī)械工程的結(jié)構(gòu)分析等。為了滿足這些需求,統(tǒng)計(jì)學(xué)家以及應(yīng)用數(shù)學(xué)家在數(shù)值線性代數(shù)上做出了新的研究。解決高階線性系統(tǒng)的方法是馮·諾伊曼研究計(jì)算機(jī)數(shù)值分析的主題之一。在二戰(zhàn)中,他曾在研究所組織過一個(gè)研究小組為流體動(dòng)力學(xué)研究做數(shù)值分析。ValentineBargmann和DeaneMontgomary是他的合作者。在1949年10月他們?nèi)税l(fā)表了一篇論文,分析了現(xiàn)有的解決大型線性系統(tǒng)的可靠性方法,并建議把重復(fù)方法(IterativeMethod)用于計(jì)算機(jī)。論文第一節(jié)比較了常見的解決線性系統(tǒng)算法的復(fù)雜性。用乘法的步驟數(shù)來測(cè)度解決一個(gè)線性系統(tǒng)所需的總時(shí)間。他們?yōu)槊糠N計(jì)算方法確定了一個(gè)測(cè)度復(fù)雜性的級(jí)別,級(jí)別為n的系統(tǒng)的函數(shù),他們估算了排除法為n研究者們也考慮到了數(shù)值穩(wěn)定性。如果連串錯(cuò)誤不可避免地在每個(gè)階段出現(xiàn)而不累積起來破壞結(jié)果,那么一個(gè)計(jì)算方法被認(rèn)為是數(shù)值穩(wěn)定的。在做手動(dòng)計(jì)算時(shí),數(shù)值穩(wěn)定性并不是嚴(yán)重的問題,因?yàn)樵谟?jì)算的數(shù)值上做了限制。所以這個(gè)問題還不被人重視。在使用高速計(jì)算裝置時(shí),它變得極為重要,因?yàn)橛?jì)算機(jī)能執(zhí)行數(shù)千次重復(fù)的數(shù)值過程。研究者們承認(rèn)估算單獨(dú)的數(shù)值方法的穩(wěn)定性非常困難,但他們判定了排除法、分割法、正交法、決定法都不是穩(wěn)定的,不適用于計(jì)算機(jī)。從他們的視角看,數(shù)值方法的穩(wěn)定性比復(fù)雜性更重要。電子計(jì)算機(jī),譬如ENIAC,比過去的計(jì)算裝置快數(shù)千倍,所以使用者非常樂意在一個(gè)控制連串錯(cuò)誤運(yùn)算程序里加大計(jì)算的復(fù)雜性或步驟。由此,馮·諾伊曼小組選擇了重復(fù)方法為最適用于高速計(jì)算機(jī)的方法。該方法在重復(fù)的步驟中得到所給定的精確程度非常有效,更重要的是它很穩(wěn)定,為計(jì)算精確而起鋪墊作用的額外數(shù)字少,算法可以實(shí)踐應(yīng)用于高速計(jì)算機(jī)。后來,馮·諾伊曼與戈德斯汀合作發(fā)表了兩篇論文,主要是為了考查計(jì)算機(jī)裝置中由噪聲引起的累積起來的錯(cuò)誤。第一篇論文他們從嚴(yán)格決定基礎(chǔ)法對(duì)錯(cuò)誤進(jìn)行估算,但他們發(fā)現(xiàn)錯(cuò)誤本質(zhì)上象隨意變體,所以他們建議使用概率法。第二篇論文研究了概率法。馮·諾伊曼在偏微方程的數(shù)值分析法中的貢獻(xiàn)是研究了數(shù)值穩(wěn)定性。在馮·諾伊曼的指導(dǎo)下,電子計(jì)算機(jī)工程成為計(jì)算機(jī)數(shù)值分析的重要中心。赫爾曼·戈德斯汀組織了大約50人在這個(gè)領(lǐng)域耕耘,并從與計(jì)算機(jī)的接觸中受益。這個(gè)組織無疑是戰(zhàn)后十年唯一活躍的數(shù)值分析研究中心。馮·諾伊曼是?？?在研究中心的各個(gè)方面做出了貢獻(xiàn),直到他成為原子能委員會(huì)委員因工作太繁忙而結(jié)束。在數(shù)學(xué)界以及政府部門中地位的提升有助于他呼吁的學(xué)科的合法化以及招募研究基金。由于以上所有理由,馮·諾伊曼被看作是現(xiàn)代數(shù)值分析的創(chuàng)始人。在復(fù)雜性科學(xué)的發(fā)展中,由于傳統(tǒng)的數(shù)學(xué)解析方法對(duì)非線性、變系數(shù)及不規(guī)則復(fù)雜問題無法解決,只能依靠計(jì)算機(jī)輔助下的數(shù)值實(shí)驗(yàn)方法對(duì)復(fù)雜問題給出更系統(tǒng)、更豐富而直觀的啟示,因此數(shù)值方法變得得越來越重要。3德國法上的自然和外在表現(xiàn)馮·諾伊曼的元胞自動(dòng)機(jī)為我們提供了一種新的建構(gòu)方法:自下而上的方法。所謂“自下而上”的方法是指:“先從底部定義許多小的單元以及幾條關(guān)系到它們內(nèi)部的、完全是局部的相互作用的簡單規(guī)則,從這些相互作用中產(chǎn)生出連貫的‘整體’行為,這種行為并不是根據(jù)特殊規(guī)則預(yù)先編好的?！瘪T·諾伊曼在亞瑟·勃克斯編輯整理的《自增殖自動(dòng)機(jī)理論》第二章第二節(jié)中,詳細(xì)介紹了元胞自動(dòng)機(jī)模型的“態(tài)”及其轉(zhuǎn)換規(guī)則。他認(rèn)為元胞自動(dòng)機(jī)模型是基于晶狀媒介(Cristallinemedia)的,可以在二維空間里用平方(規(guī)則)晶格(Quadraticlat-tice)結(jié)構(gòu)構(gòu)造它。假定這個(gè)晶狀體上的每個(gè)格點(diǎn)具有有限個(gè)不同的態(tài)(記為N態(tài)),其行為可以用明確的轉(zhuǎn)換規(guī)則來描述或(控制)。轉(zhuǎn)換規(guī)則中包含當(dāng)其受近鄰元胞影響時(shí),這些態(tài)之間的轉(zhuǎn)換。按照轉(zhuǎn)換規(guī)則的步驟演化,元胞自動(dòng)機(jī)會(huì)形成各種各樣不同的復(fù)雜圖案。元胞自動(dòng)機(jī)的復(fù)雜行為并非預(yù)先設(shè)計(jì)好的,而是“涌現(xiàn)”出來的,涌現(xiàn)是指“在復(fù)雜的(非線性)形態(tài)中許多簡單單元彼此相互作用時(shí)產(chǎn)生出來的引人注目的整體特性”在馮·諾伊曼的元胞自動(dòng)機(jī)的啟發(fā)下,劍橋大學(xué)數(shù)學(xué)家約翰·康韋(JohnCoway)于1970年編制了一個(gè)名為“生命”的游戲程序,他所用的二維元胞的狀態(tài)以及這個(gè)模擬生態(tài)原理的行為規(guī)則是非常簡單的,該程序只有幾條簡單的規(guī)則,但簡單的行為通過相互作用和迭代運(yùn)作后,模擬出了自然生命、人工生命的各種形態(tài)和現(xiàn)象,如代謝、生長、繁殖,進(jìn)化與混沌邊緣的多樣性等。英國科學(xué)家沃爾弗拉姆從1986年起,在計(jì)算機(jī)上將元胞自動(dòng)機(jī)用于模擬復(fù)雜現(xiàn)象?；趯?duì)元胞自動(dòng)機(jī)的思考與研究,沃爾弗拉姆選擇了一種由最簡單的規(guī)則所構(gòu)成的元胞自動(dòng)機(jī)作為研究對(duì)象,“我采用一個(gè)簡單的程序,然后讓其系統(tǒng)地