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

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

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

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

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