若干細胞自動機的符號動力學研究.pdf

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

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

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

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

5、ernoulli移位性質(zhì)的不變子系統(tǒng)以及決定系統(tǒng)，然后分析了三個子系統(tǒng)之間的關(guān)系，最后給出全局映射在各個子系統(tǒng)上的動力學性質(zhì)，例如拓撲傳遞性，拓撲混合性，正拓撲熵等。進一步，本章對規(guī)則41的動力學行為進行了研究，給出規(guī)則41的一個非游蕩集，并且分析了全局映射在這個游蕩集上的一些動力學性質(zhì)。第三章系統(tǒng)研究了規(guī)則61中滑翔機、滑翔碰撞等滑翔動力學性質(zhì)。首先以De Bruijn圖為工具給出滑翔機在以(1，1，1，1，0，1，0，0，0)*為初

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