若干細(xì)胞自動(dòng)機(jī)的符號(hào)動(dòng)力學(xué)研究.pdf

1、細(xì)胞自動(dòng)機(jī)是一類研究復(fù)雜系統(tǒng)的數(shù)學(xué)模型，由現(xiàn)代計(jì)算機(jī)的創(chuàng)始人John von Neumann于二十世紀(jì)四、五十年代在研究生命系統(tǒng)的自我復(fù)制現(xiàn)象時(shí)提出。細(xì)胞自動(dòng)機(jī)在數(shù)學(xué)意義下是一種離散的動(dòng)力系統(tǒng)，其時(shí)間、空間和狀態(tài)均是離散的。對(duì)于不同的局部規(guī)則，細(xì)胞自動(dòng)機(jī)的時(shí)空演化具有豐富的形態(tài)。尤其是其中的一些簡(jiǎn)單的規(guī)則，卻能產(chǎn)生十分復(fù)雜的動(dòng)力學(xué)行為。細(xì)胞自動(dòng)機(jī)理論一直受到許多學(xué)者的潛心研究，其中包括細(xì)胞自動(dòng)機(jī)復(fù)雜性的內(nèi)在機(jī)理，細(xì)胞自動(dòng)機(jī)在不同意義下的

2、分類，以及與其他相關(guān)學(xué)科的聯(lián)系等。另外，細(xì)胞自動(dòng)機(jī)為動(dòng)力學(xué)理論中關(guān)于混沌、分形等整體行為的研究提供了有效的模型。在大量理論研究成果的基礎(chǔ)上，細(xì)胞自動(dòng)機(jī)的應(yīng)用領(lǐng)域也十分廣泛，尤其是在并行計(jì)算、復(fù)雜工業(yè)系統(tǒng)、密碼學(xué)和自然現(xiàn)象模擬等方面的應(yīng)用。
　　 滑翔機(jī)作為一種隨時(shí)間周期性演化的結(jié)構(gòu)，其動(dòng)力學(xué)性質(zhì)得到了廣泛的關(guān)注?；炯?xì)胞自動(dòng)機(jī)中有關(guān)滑翔機(jī)的研究開(kāi)始于M.Cook對(duì)規(guī)則110的研究。在規(guī)則110中，Cook將這些具有周期性的演化結(jié)

3、構(gòu)進(jìn)行了分類。G.J.Martinez等學(xué)者在Cook的工作基礎(chǔ)上對(duì)一維細(xì)胞自動(dòng)機(jī)規(guī)則110和規(guī)則54演化過(guò)程中出現(xiàn)的滑翔、碰撞以及滑翔槍等進(jìn)行了深入的研究，并分析了滑翔機(jī)、滑翔槍和滑翔碰撞的性質(zhì)。同時(shí)，滑翔機(jī)也具有十分廣泛的應(yīng)用。例如，用于細(xì)胞自動(dòng)機(jī)的計(jì)算理論的研究，與邏輯門(mén)運(yùn)算的關(guān)系，具有并行計(jì)算能力的細(xì)胞自動(dòng)機(jī)的群體運(yùn)算等。本文在符號(hào)動(dòng)力系統(tǒng)的框架下，以兩類基本細(xì)胞自動(dòng)機(jī)為研究對(duì)象，討論它們所具有的拓?fù)鋭?dòng)力學(xué)和滑翔動(dòng)力學(xué)性質(zhì)。首先

4、，本文分別給出兩類基本細(xì)胞自動(dòng)機(jī)規(guī)則的具有Bernoulli移位性質(zhì)的不變子系統(tǒng)，并且分析了在這些子系統(tǒng)上的動(dòng)力學(xué)行為。然后，利用De Bruijn圖為工具對(duì)滑翔機(jī)和滑翔碰撞進(jìn)行了分類。最后，分別對(duì)不同組合的滑翔碰撞進(jìn)行計(jì)算機(jī)模擬，得出它們的演化軌道，并且建立了滑翔碰撞與邏輯計(jì)算之間的聯(lián)系。
　　 第二章第一部分以符號(hào)動(dòng)力系統(tǒng)為工具，在雙邊無(wú)窮符號(hào)序列空間中對(duì)基本細(xì)胞自動(dòng)機(jī)規(guī)則61的動(dòng)力學(xué)行為進(jìn)行了分析。給出規(guī)則61的三個(gè)具有B

5、ernoulli移位性質(zhì)的不變子系統(tǒng)以及決定系統(tǒng)，然后分析了三個(gè)子系統(tǒng)之間的關(guān)系，最后給出全局映射在各個(gè)子系統(tǒng)上的動(dòng)力學(xué)性質(zhì)，例如拓?fù)鋫鬟f性，拓?fù)浠旌闲?，正拓?fù)潇氐取＿M(jìn)一步，本章對(duì)規(guī)則41的動(dòng)力學(xué)行為進(jìn)行了研究，給出規(guī)則41的一個(gè)非游蕩集，并且分析了全局映射在這個(gè)游蕩集上的一些動(dòng)力學(xué)性質(zhì)。第三章系統(tǒng)研究了規(guī)則61中滑翔機(jī)、滑翔碰撞等滑翔動(dòng)力學(xué)性質(zhì)。首先以De Bruijn圖為工具給出滑翔機(jī)在以(1，1，1，1，0，1，0，0，0)*為初

6、始構(gòu)型的以太背景下的分類，得出每一類的基本滑翔機(jī)以及基本滑翔因子，接著分析了不同滑翔機(jī)之間相互組合之后產(chǎn)生的碰撞現(xiàn)象。在第四章中，進(jìn)一步對(duì)滑翔碰撞進(jìn)行分析，建立了滑翔碰撞與邏輯運(yùn)算之間的關(guān)系。首先對(duì)不同類的滑翔機(jī)進(jìn)行組合，得出碰撞演化圖和對(duì)應(yīng)的邏輯運(yùn)算真值表，然后對(duì)所有二輸入滑翔碰撞進(jìn)行了分類，找到了可以作為基本邏輯運(yùn)算單元的滑翔碰撞，接著對(duì)三輸入的滑翔碰撞進(jìn)行了分類，并且給出部分滑翔碰撞對(duì)應(yīng)的邏輯真值表，最后給出部分實(shí)例驗(yàn)證。最后一章