若干細(xì)胞自動(dòng)機(jī)規(guī)則的符號(hào)動(dòng)力學(xué)及其偽隨機(jī)數(shù)發(fā)生器.pdf

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

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

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