普適細(xì)胞自動(dòng)機(jī)若干動(dòng)力學(xué)性質(zhì).pdf

1、從數(shù)學(xué)上看，細(xì)胞自動(dòng)機(jī)（Cellular Automata，簡(jiǎn)稱 CA）是一種時(shí)間、空間和狀態(tài)都離散的動(dòng)力系統(tǒng)。研究表明，通過(guò)設(shè)計(jì)不同的局部映射，細(xì)胞自動(dòng)機(jī)可以表現(xiàn)出復(fù)雜豐富的動(dòng)力學(xué)行為。比如，初等細(xì)胞自動(dòng)機(jī)規(guī)則110具有普適的計(jì)算功能，是目前發(fā)現(xiàn)的最簡(jiǎn)單的圖靈系統(tǒng)。同樣，在二維細(xì)胞自動(dòng)機(jī)中，Conway發(fā)明的生命游戲（Game of Life）是最早的從分析角度被證明的一個(gè)具有普適計(jì)算功能的規(guī)則，其演化可以涌現(xiàn)出豐富的動(dòng)力學(xué)現(xiàn)象，如滑

2、翔機(jī)（Glider）、滑翔槍（Glider gun）、碰撞（Collision）、宇宙飛船(Spaceship)等。因此，細(xì)胞自動(dòng)機(jī)可以用來(lái)模擬許多現(xiàn)實(shí)的動(dòng)態(tài)系統(tǒng)，比如，交通、人口和生態(tài)模型等。
　　本文主要在符號(hào)動(dòng)力系統(tǒng)的觀點(diǎn)下討論一維的細(xì)胞自動(dòng)機(jī)規(guī)則110和二維的細(xì)胞自動(dòng)機(jī)規(guī)則B2/S7（Diffusion Rule）和B3/S23（Game of Life）的一些動(dòng)力學(xué)性質(zhì)。論文具體安排如下：第一章介紹了細(xì)胞自動(dòng)機(jī)的發(fā)展簡(jiǎn)史

3、、基礎(chǔ)知識(shí)、經(jīng)驗(yàn)分類以及本文的主要結(jié)構(gòu)和內(nèi)容。第二章討論了初等細(xì)胞自動(dòng)機(jī)110號(hào)規(guī)則滑翔機(jī)E3，由此找到了它的全局映射的一個(gè)不變子系統(tǒng)，討論了在子系統(tǒng)上的動(dòng)力學(xué)性質(zhì)，刻畫了它的復(fù)雜性。例如，拓?fù)鋫鬟f、拓?fù)浠旌?、正拓?fù)潇氐?，從而得到它們是Li-Yorke和Devaney意義下混沌的。第三章介紹了二維細(xì)胞自動(dòng)機(jī)符號(hào)動(dòng)力學(xué)的基礎(chǔ)知識(shí)，用拓?fù)涔曹椀姆椒ǔ醪綄?duì)二維 Moore鄰域 Outer Totalistic細(xì)胞自動(dòng)機(jī)規(guī)則進(jìn)行了分類，并且通過(guò)