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

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

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

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