復雜Bernoulli移位細胞自動機的動力學研究.pdf

1、細胞自動機作為一種特殊的數(shù)學模型,其實質是一類時間、空間和狀態(tài)都離散的動力學模型。二十世紀四、五十年代John von Neumann和Stanislaw Ulam在研究生命系統(tǒng)的自我復制現(xiàn)象時推斷局部迭代簡單動力系統(tǒng)有可能產(chǎn)生非常復雜的動力學現(xiàn)象,從此細胞自動機及其相關理論受到許多學者的潛心研究。其中包括細胞自動機復雜性的內在機理,在不同意義下的分類,以及與其他相關學科的聯(lián)系等。二十世紀八十年代初,S.Wolfram針對細胞自動機具備

2、規(guī)則簡單性、局部互連性以及信息處理的高度并行性等優(yōu)點,提出并號召人們研究結構最為簡單的具有兩個狀態(tài)、鄰域半徑為一的基本細胞自動機(ECA)。在S.Wolfram針對256個基本細胞自動機模擬結果的基礎上,L.O.Chua等結合細胞神經(jīng)網(wǎng)絡和非線性電路的研究成果對其進行了一系列非線性動力學的刻畫。
　　 符號動力系統(tǒng)是研究細胞自動機的一個重要工具。根據(jù)不同的細胞自動機,設計其相關的局部規(guī)則,均可以誘導出雙邊無窮序列所組成的構型空間

3、上相應的拓撲動力系統(tǒng)。借助計算機模擬將發(fā)現(xiàn),細胞自動機呈現(xiàn)豐富的動力學行為。此外,細胞自動機也具有適合在超大規(guī)模集成器上實現(xiàn)的并行信息處理結構。1986年,C.Langton提出細胞自動機可以為信息傳遞、存儲和修改等操作提供最基本的條件支持。另外,細胞自動機的一種特殊的時空周期演化結構一滑翔機,及其相關動力學性質也得到了廣泛的關注。大量的理論研究成果為細胞自動機的應用領域奠定了基礎,尤其是在自然現(xiàn)象模擬、密碼學、復雜工業(yè)系統(tǒng)和并行計算等

4、方面有廣泛的應用。
　　 本文第二、三章以符號動力系統(tǒng)為主要工具,利用周期邊界條件借助計算機進行模擬,在雙邊無窮符號序列空間中對復雜Bernoulli移位細胞自動機規(guī)則73的拓撲動力學和滑翔動力學行為進行了分析。第二章得到73號細胞自動機規(guī)則的8個具有Bernoulli移位性質的不變子系統(tǒng)及其相關決定系統(tǒng),并給出這8個子系統(tǒng)之間的關系,最后通過分析全局映射f73在每個子系統(tǒng)上的動力學行為,證明其具有拓撲傳遞性,拓撲混合性,正拓撲

5、熵等動力學性質?；诘玫降牟蛔冏酉到y(tǒng),第三章系統(tǒng)地研究了規(guī)則73中滑翔機、滑翔碰撞等滑翔動力學行為。借助De Bruijn圖對滑翔機在不同以太背景下進行分類,并給出每一類的基本滑翔機及其相關的基本滑翔因子。同時發(fā)現(xiàn),不同滑翔機之間相互組合之后會產(chǎn)生的多種不同的碰撞現(xiàn)象。結合分布式計算可以看到,ECA規(guī)則73的任意Bernoulli移位子系統(tǒng)提供了信息存儲或者信息傳遞的基本條件,并且在特定的以太背景下可以設計速度不同的滑翔因子以實現(xiàn)信息的

6、修改。
　　 一直以來,對細胞自動機進行更加完整和精確的分類是一項極具挑戰(zhàn)又頗有意義的理論任務。諸多學者嘗試從不同的角度進行討論,但是由于受到許多條件的限制,分類結果缺乏一般性。最初,Wolfram通過大量的計算機實驗將所有的細胞自動機分成四個大類。隨后,L.O.Chua等通過三個幾何變換,將所有的基本細胞自動機規(guī)則分成88個全局等價類。在L.O.Chua等對細胞自動機分類的基礎之上,本文第四章針對其中3個全局等價類進行研究,通

7、過構造相應的同胚映射將此3類細胞自動機與單邊無窮符號序列空間上的移位映射建立拓撲共軛關系,進而將它們規(guī)結為同一類,記作PECA。此外,容易證明由這些具有特殊性質的規(guī)則誘導出的乘積動力系統(tǒng)與移位系統(tǒng)仍然保持等價關系,即二者具有等價的拓撲動力學性質,如正拓撲熵、拓撲混合、拓撲傳遞和拓撲正合等,從而是Devaney意義上和Li-Yorke意義上的混沌。
　　 文章最后對本文主要工作進行總結,根據(jù)研究中發(fā)現(xiàn)的問題與困難,提出對進一步研究