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

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

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

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

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

5、ernoulli移位性質(zhì)的不變子系統(tǒng)以及決定系統(tǒng)，然后分析了三個子系統(tǒng)之間的關(guān)系，最后給出全局映射在各個子系統(tǒng)上的動力學(xué)性質(zhì)，例如拓?fù)鋫鬟f性，拓?fù)浠旌闲?，正拓?fù)潇氐?。進(jìn)一步，本章對規(guī)則41的動力學(xué)行為進(jìn)行了研究，給出規(guī)則41的一個非游蕩集，并且分析了全局映射在這個游蕩集上的一些動力學(xué)性質(zhì)。第三章系統(tǒng)研究了規(guī)則61中滑翔機(jī)、滑翔碰撞等滑翔動力學(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)一步對滑翔碰撞進(jìn)行分析，建立了滑翔碰撞與邏輯運(yùn)算之間的關(guān)系。首先對不同類的滑翔機(jī)進(jìn)行組合，得出碰撞演化圖和對應(yīng)的邏輯運(yùn)算真值表，然后對所有二輸入滑翔碰撞進(jìn)行了分類，找到了可以作為基本邏輯運(yùn)算單元的滑翔碰撞，接著對三輸入的滑翔碰撞進(jìn)行了分類，并且給出部分滑翔碰撞對應(yīng)的邏輯真值表，最后給出部分實例驗證。最后一章