Bernoulli移位細胞自動機的符號動力學研究.pdf

1、由計算機創(chuàng)始人John von Neumann提出的細胞自動機(Cellular Automata，CA)是一種時間、空間和狀態(tài)都離散的數(shù)學模型.從數(shù)學角度看，CA是與連續(xù)Cantor映射動力學系統(tǒng)相對應的離散動力學系統(tǒng).通過設(shè)計不同的局部規(guī)則，CA可以展現(xiàn)無限的多樣性和復雜性，產(chǎn)生復雜的動態(tài)交互和自我復制現(xiàn)象，即使是最簡單的基本細胞自動機(Elementary CA，ECA)也具有豐富而復雜的動力學性質(zhì).同時，CA又具有適合超大規(guī)模集

2、成電路(VLSI)上實現(xiàn)的并行信息處理結(jié)構(gòu)，被廣泛應用于社會學、生物學、生態(tài)學、信息科學、計算機科學、數(shù)學、物理學、化學、軍事學等不同領(lǐng)域. 符號動力學是研究動力系統(tǒng)動力學行為的一個重要工具.近年來基本細胞自動機全局映射的符號動力學行為的研究得到了發(fā)展，成果比較豐富.例如，關(guān)于加性的、滿的、等度連續(xù)的、正擴張的以及置換的細胞自動機的動力學行為分析相對比較完整.但是，仍然有許多全局映射(尤其是具有普適性的細胞自動機)的符號動力學行

3、為還知之甚少，特別是一些重要的拓撲性質(zhì)，比如拓撲熵、敏感依賴性、拓撲混合性等.本文將細胞自動機的構(gòu)形與雙邊無窮符號序列建立起聯(lián)系，在符號動力系統(tǒng)的框架下研究細胞自動機的符號動力學性質(zhì).因此，本文選取了三個代表性Bernoulli移位規(guī)則119，88和25作為研究對象，利用符號動力系統(tǒng)理論，得到了適用于研究Bernoulli移位規(guī)則動力學性質(zhì)的一些方法，并揭示了這類規(guī)則豐富復雜的動力學性質(zhì). 本文第二章首先從符號動力學角度討論了1

4、19號規(guī)則的復雜動力學行為.借助于有限型子移位相關(guān)理論，證明了119號規(guī)則的全局映射f119具有一個Bernoulli移位的全局吸引子，并且f119在全局吸引子上是拓撲混合的，以及f119在全空間上的拓撲熵人于零.因而f119在全局吸引子上具有Li-Yorke意義和修改的Devaney意義下的混沌.其次考慮全局映射f88的符號動力學性質(zhì).不同于119號規(guī)則，第三章首先嚴格地找出f88在雙邊無窮符號序列空間中的三個不同Bernoulli移