普適細胞自動機若干動力學性質.pdf

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

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

3、、基礎知識、經驗分類以及本文的主要結構和內容。第二章討論了初等細胞自動機110號規(guī)則滑翔機E3，由此找到了它的全局映射的一個不變子系統，討論了在子系統上的動力學性質，刻畫了它的復雜性。例如，拓撲傳遞、拓撲混合、正拓撲熵等，從而得到它們是Li-Yorke和Devaney意義下混沌的。第三章介紹了二維細胞自動機符號動力學的基礎知識，用拓撲共軛的方法初步對二維 Moore鄰域 Outer Totalistic細胞自動機規(guī)則進行了分類，并且通過