若干細胞自動機規(guī)則的符號動力學及其偽隨機數(shù)發(fā)生器.pdf

1、從現(xiàn)代計算機的創(chuàng)始人John von Neumann提出細胞自動機的概念,到本世紀初wolfram出版的《新科學》,具有簡單結構的細胞自動機吸引了大量的科學工作者。在過去的幾十年里,人們對細胞自動機的研究不僅單單局限于嚴格的數(shù)學與物理分析,細胞自動機在科學的各個方面當中的應用都得到了研究。這一切都歸結于細胞自動機由簡單的規(guī)則,簡單的結構卻可以成為復雜系統(tǒng)的一個模型。細胞自動機作為一種時間、空間和狀態(tài)都離散的動力系統(tǒng),由多個獨立的細胞構成

2、。通過設計不同的局部規(guī)則,每個獨立的細胞根據(jù)鄰居的狀態(tài)隨著時間的推移改變狀態(tài),這可以看成一種簡單并行處理的結構。然而這種簡單的結構可展現(xiàn)出時空演化的多樣性和復雜性,產(chǎn)生復雜的動態(tài)交互和自我復制現(xiàn)象。
　　 符號動力學是研究動力系統(tǒng)動力行為的一個重要工具。這種系統(tǒng)的狀態(tài)均可表示為有限個符號的無限序列,而由任一狀態(tài)點引出的運動軌道可由表示該狀態(tài)的無窮序列通過簡單的規(guī)則來確定。許多復雜動力系統(tǒng)均可經(jīng)過變換等價于這類系統(tǒng),從而可通過對符

3、號動力系統(tǒng)的分析來研究一般動力系統(tǒng)的行為。這種方法在復雜行為研究中占有重要的地位,特別是對于混沌等復雜行為。
　　 計算理論證明“有關細胞自動機的任何一個非平凡命題都是不可判定問題”,因此必須對細胞自動機及其動力學行為進行分門別類的研究。本文以基本細胞自動機規(guī)則41和90為研究對象,在雙邊無窮符號序列空間中對其部分動力學行為進行了分析。首先給出了規(guī)則41的三個具有Bernoulli移位性質的不變子系統(tǒng)及其動力學性質,例如拓撲傳遞