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

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

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

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

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