若干細胞自動機規(guī)則的符號動力學(xué)行為.pdf

1、由計算機創(chuàng)始人John von Neumann提出的細胞自動機是一種時間,空間與狀態(tài)都離散的動力系統(tǒng).通過設(shè)計不同的局部規(guī)則,細胞自動機可以展現(xiàn)無限的多樣性和復(fù)雜性,產(chǎn)生復(fù)雜的動態(tài)交互和自我復(fù)制現(xiàn)象.即使是最簡單的基本細胞自動機規(guī)則,也蘊藏著豐富的動力學(xué)行為.因此近年來,細胞自動機在圖像處理,交通流模型,生物模型,密碼學(xué)等領(lǐng)域有著十分廣泛的應(yīng)用.
　　 通過大量計算機模擬實驗,在細胞自動機的演化過程中,出現(xiàn)會周期循環(huán)其狀態(tài)(形狀

2、)并且能穩(wěn)定地移動的結(jié)構(gòu),即為我們現(xiàn)在所知的滑翔機.滑翔機的首次提出是在著名數(shù)學(xué)家Conway的生命游戲(Game of Life,一種能夠進行計算的簡單的2個狀態(tài)的8個鄰居的細胞自動機).像滑翔機這種會移動并維持形態(tài)的結(jié)構(gòu),在生命游戲中扮演傳遞訊號的角色.而訊號的儲存與傳遞是生物演化機制的重要特征,也是建構(gòu)一臺計算機的必要條件.因此,滑翔機可謂是細胞自動機演化中出現(xiàn)的極為重要的動力學(xué)現(xiàn)象.
　　 符號動力學(xué)是研究動力系統(tǒng)動力學(xué)

3、行為的一個重要工具.近些年來,在數(shù)學(xué),密碼學(xué),工程和物理學(xué)等研究領(lǐng)域提出的眾多實際模型中,人們發(fā)現(xiàn)在刻畫其復(fù)雜性時往往要涉及符號動力系統(tǒng)的理論與方法.從符號動力學(xué)的觀點看,滑翔機實際上是嵌入到雙邊無窮序列中的周期性移位.本文從符號動力學(xué)的觀點對基本細胞自動機規(guī)則的演化過程中出現(xiàn)的滑翔機,滑翔機碰撞以及其他一些現(xiàn)象給出了數(shù)學(xué)上的刻畫.
　　 首先本文對Bernoulli移位規(guī)則14和規(guī)則9,從符號動力學(xué)的角度進行了深入的研究.在第

4、二章首先證明了規(guī)則14具有兩個混沌子系統(tǒng),并且在其子系統(tǒng)上具有復(fù)雜的動力學(xué)性質(zhì),如在其子系統(tǒng)上具有拓撲混合性和正的拓撲熵.進而可證f14在其子系統(tǒng)上是Li-Yorke意義和的Devaney意義下得混沌.另外本章對規(guī)則14中出現(xiàn)的周期軌道中給出了一系列性質(zhì).在第三章,研究了基本細胞自動機規(guī)則9.規(guī)則9屬于Chua提出的Bernoulli移位規(guī)則,同時也屬于Wolfram提出的第二類規(guī)則.本文從符號動力學(xué)的觀點對規(guī)則9出現(xiàn)的基本滑翔機,滑翔