復(fù)雜Bernoulli移位細(xì)胞自動(dòng)機(jī)的動(dòng)力學(xué)研究.pdf

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

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

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

4、方面有廣泛的應(yīng)用。
　　 本文第二、三章以符號(hào)動(dòng)力系統(tǒng)為主要工具,利用周期邊界條件借助計(jì)算機(jī)進(jìn)行模擬,在雙邊無(wú)窮符號(hào)序列空間中對(duì)復(fù)雜Bernoulli移位細(xì)胞自動(dòng)機(jī)規(guī)則73的拓?fù)鋭?dòng)力學(xué)和滑翔動(dòng)力學(xué)行為進(jìn)行了分析。第二章得到73號(hào)細(xì)胞自動(dòng)機(jī)規(guī)則的8個(gè)具有Bernoulli移位性質(zhì)的不變子系統(tǒng)及其相關(guān)決定系統(tǒng),并給出這8個(gè)子系統(tǒng)之間的關(guān)系,最后通過(guò)分析全局映射f73在每個(gè)子系統(tǒng)上的動(dòng)力學(xué)行為,證明其具有拓?fù)鋫鬟f性,拓?fù)浠旌闲?正拓?fù)?/p>

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

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

7、過(guò)構(gòu)造相應(yīng)的同胚映射將此3類(lèi)細(xì)胞自動(dòng)機(jī)與單邊無(wú)窮符號(hào)序列空間上的移位映射建立拓?fù)涔曹楆P(guān)系,進(jìn)而將它們規(guī)結(jié)為同一類(lèi),記作PECA。此外,容易證明由這些具有特殊性質(zhì)的規(guī)則誘導(dǎo)出的乘積動(dòng)力系統(tǒng)與移位系統(tǒng)仍然保持等價(jià)關(guān)系,即二者具有等價(jià)的拓?fù)鋭?dòng)力學(xué)性質(zhì),如正拓?fù)潇?、拓?fù)浠旌稀⑼負(fù)鋫鬟f和拓?fù)湔系?從而是Devaney意義上和Li-Yorke意義上的混沌。
　　 文章最后對(duì)本文主要工作進(jìn)行總結(jié),根據(jù)研究中發(fā)現(xiàn)的問(wèn)題與困難,提出對(duì)進(jìn)一步研究