（基础数学专业论文）若干周期类ca规则的复杂动力学性质.pdf

细胞自动机由j o h ny o nn e u m a n n 于上世纪5 0 年代提出在形态表现上每 个细胞自动机均是一个离散型的动力系统，它由一些特定规则的格子组成，每个 格子可视为一个细胞随着时问的变化( 称之为叠代过程) ，每一个细胞根据周围 细胞的情形按照相同的法则改变状态通过设计不同的局部规则，细胞自动机展 现出无限的多样性和复杂性以及复杂多样的动态交互和自我复制现象即便是 最简单的摹本细胞自动机其动力学性质也极复杂自产生以来细胞自动机已被 广泛应用于社会、经济、军事和科学研究的各个领域 本文主要旨在从符号动力系统的角度，在双边无穷条件下研究鲁棒周期娄细 胞自动机规则9 6 号和6 2 号的符号动力学性质，探索这类看似简单的细胞自动 机规则下蕴含的复杂动力学性质 本文第一章介绍丁符号动力学的研究背景细胞自动机的定义盼7 1 ! ：= - ： 主要内容和结构第二章研究鲁棒周期1 规则中的非鲁棒b e r n o u l l i 移位性质以 规则9 6 为代表，利用树图及其f o r w a r dt i m e 7 映射分析了该规则的定性性质，发 现该规则具有非鲁棒b e r n o u l l i 移位特征，并利用符号动力学的相关理论与方法， 严格证明了9 6g 规则具有混沌的子系统第三章讨论了6 2 号规则一作为唯一一 个鲁棒周期3 规则展现其丰富日复杂的动力学性质本章系统分析了( 、2 号规 则中存在的滑翔机及其相互间作用产生的丰富多彩的现象，定义丁规则c 二幸窟j 基础滑翔机滑翔机之间的碰撞以及滑翔枪而这些现象之前大都被认为佼存在 l 摘要 于x b l f r a m 的复杂类规则5 4 和1 1 0 号规则中另外，类似规则9 6 ，6 2 号规则同样 也定义了复杂的子系统，该子系统不仅拓扑混合还具有正的拓扑熵本文最后一 章是对全文的总结及对未来研究的展望 关键词：基本细胞自动机；符号动力学；滑翔机；碰撞；混沌 l l i 叫 一 擎 叠1 z ，1 0 0 ， ， - c o m p l e xd y n a m i c so fs o m ep e r i o dc e l l u l a r a u t o m a t ar ul e s a b s t r a c t c e l l u l a ra u t o m a t a ( c a ) ，c o n c e i v e db yj o h nv o nn e u m a n ni nt h e19 5 0 s ，a r ed 、， n a m i cs y s t e m si nw h i c hs p a c ea n dt i m ea r ed i s c r e t e t h ec aa l g o r i t h mi sap a r a l l e l p r o c e s so p e r a t i n go nt h ea r r a yo fc e l l s t h es i m u l t a n e o u sc h a n g eo fs t a t eo fe a c h c e l l i ss p e c i f i e db yal o c a lt r a n s i t i o nr u l e t h r o u g hd i f f e r e n tl o c a lr u l e sd e s i g n e d ，c ac a n e x h i b i ta l lk i n d so fv a r i e t i e sa n dc o m p l e x i t i e s ，a n dp r o d u c ec o m p l i c a t e dp h e n o m e n a o f d y n a m i ci n t e r a c t i o na n ds e l f - d u p l i c a t i n g e v e ne l e m e n t a r yc e l l u l a ra u t o m a t a w i t hv e r y s i m p l el o c a lr u l e sh a v er i c hd y n a m i c a lb e h a v i o r s s i n c ec a c a m ei n t ob e i n g ，t h e yh a v e b e e nw i d e l ya p p l i e di nt h er e s e a r c ho fs o c i o l o g y ，e c o n o m i c s ，s t r a t e g i e s ，s c i e n c e ，e r e i nt h i st h e s i s ，s y m b o l i cd y n a m i c so fr o b u s tp e r i o d i ce l e m e n t a r yc e l lu l a ra u t o m a t a r u l e s6 2a n d9 6i si n v e s t i g a t e di nt h eb i i n f i n i t es y m b o l i cs e q u e n c es p a c e o n e = 、fj m a i nc o n t e n t i o n si st h a tt h e s er o b u s tp e r i o dr u l e s ，w h i c hw e r cs a i dt ob es i m p l ya s p e r i o d i cb e f o r e ，a c t u a l l yd i s p l a yr i c ha n dc o m p l e xn o n l i n e a rd y n a m i c si n t h ei n f i n i t e c a s e i nc h a p t e r1 ，w er e v i e wb r i e f l yt h en o t a t i o n sa n dc o n c e p t so fo r l e d i m e n s i o n a l c a sa n ds y m b o l i cd y n a m i c s ，a sw e l la st h er e s e a r c hp r o g r e s so fc a s i nc h a p t e r2 w e e x p l o i tt h ec o n c e p t so fc a b a s i nt r e ed i a g r a ma n df o r w a r dt i m e 丁m a p st ou n t o 叮t h e q u a l i t a t i v ep r o p e r t i e so fr u l e9 6 w h i c hr e v e a li t sn o n r o b u s tb e r n o u l l i - s h i f tc h a r a c t e r 。 i i i a bs t r a c t i s t i c s b a s e do nc o n c e p t sf r o ms u b s h i f lo ff i n i t et y p e 。t h i sc h a p t e rc o n d u c t sar i g o r o u s a n a l y s i so fi t s rc h a o t i cp r o p e r t i e s ，s u c ha st o p o l o g i c a l l ym i x i n ga n dt o p o l o g i c a le l l t r o p y i nc h a p t e r3 ，w ec o n c e n t r a t eo nt i m ea s y m p t o t i cd y n a m i c so fu n i q u er o b u s t p e r i o d 一3r u l e6 2 t h i sc h a p t e rp r o v i d e sas y s t e m a t i ca n a l y s i so fg l i d e rd y n a m i c sa n d i n t e r a c t i o n si nr u l e6 2 ，i n c l u d i n gs e v e r a ln a t u r a lg l i d e r s ，ac a t a l o go fg l i d e rc o l l i s i o n s a n dm a n yg l i d e rg u n s i ti si m p o r t a n tt oe m p h a s i z et h a tg l i d e r sa r eb e l i e v e dt ob et h e c h a r a c t e r i s t i cs i g n a t u r e sa l l o w i n go n et or e c o g n i z ec l a s si vb e h a v i o r c e r t a i n l y ，t h e c a t a l o go fi t sa l lp o s s i b l eg l i d e r sa n dg l i d e rc o l l i s i o n si sl e s sp l e n t i f u lt h a nt h a to fr u l e s 5 4a n d110 a l s o ，i ti sp r o v e dt h a tt h ei n t r i n s i ct e m p o r a lc o m p l e x i t yo fr u l e6 2i sh i g h a c c o r d i n gt ot h eu s u a lf e a t u r e sq u a n t i f y i n gt h ec o m p l e x i t yo fd i s c r e t ed y n a m i c s ，s u c h a st o p o l o g i c a le n t r o p ya n dt o p o l o g i c a l l ym i x i n g f i n a l l 3 w em a k eab r i e fs u mm a r yo n t h i sw o r k a n dp r o s p e c tf o rf u r t h e rr e s e a r c hi nc h a p t e r4 k e yw o r d s ： e l e m e n t a r yc e l l u l a ra u t o m a t a ( e c a ) ；s y m b o l i cd y n a m i c s ；g l i d e r ： c o l l i s i o n ；c h a o s f；j ，卞4 一q广一 广 目录 摘要 1 a b s t r a c t i l l a 录 l 绪论 1 1 1符号动力学的研究背景 1 1 1 1 符号动力学发展的简要回顾 1 1 1 2 符号动力系统的基本定义及定理 2 1 2 细胞自动机的定义及研究背景 5 1 2 1 细胞自动机研究背景 5 1 2 2 一维基本细胞自动机及逻辑表示 7 1 3 论文的主要内容与结构 8 2 周期l 规则一一9 6 号规则的符号动力学性质1 0 2 19 6 号规则的b e r n o u l l i 移位性质l l 2 1 19 6 号规则的树图：】 2 1 29 6 号规则的f o r w a r dt i m e 丁映射r ! 2 29 6 号规则的子系统1 9 2 3 ，9 6 的复杂性2 0 3 周期3 规则一一6 2 号规则的符号动力学性质2 3 3 1 f s ：的三个子系统2 3 3 2 规则6 2 的滑翔机。碰撞以及滑翔枪2 5 3 2 i 滑翔机及碰撞的定义二5 3 2 2 规则6 2 中的滑翔机二o 3 3 规则6 2 中的碰撞现象3 0 v 目录 3 4 规则6 2 的滑翔枪3 4 3 5 规则6 2 的复杂动力学性质3 4 4 总结与展望3 8 4 1 总结3 8 4 2 展望3 8 参考文献4 0 致谢4 4 在学期间的研究成果及发表的论文4 5 学位论文独创性声明及授权声明4 6 学位论文诚信承诺书4 7 v l i 一 一 一 毛 、 一 ，；， i 1绪论 1 1 符号动力学的研究背景 1 1 1 符号动力学发展的简要回顾 符号动力学是指通过某些符号组成的无穷符号序列来刻划动力系统轨道结 构的方法及与之相关的理论，是动力系统理论研究的强有力工具符号动力系统 的状态可表示为有限个符号组成的无穷序列，由任一状态引出的运动轨道可由表 示该状态的无穷序列通过一定的规则来确定由于许多复杂动态系统均可经过变 换等价于这类系统，因此可通过分析较简单的符号动力系统，研究一般动力系统 的行为这种方法在研究混沌等复杂行为方面占有重要地位除此之外，符号动力 系统的方法还被广泛应用于计算机科学、密码学、物理学、通讯等领域 符号动力学产生于2 0 世纪初，起源于动力系统的抽象拓扑理论的研究1 8 9 8 年h a d a m a r d 就将符号动力学技巧用于负曲率曲面上的测地线的研究i l 】2 0 世 纪2 0 年代，m o r s e 首先注意到符号动力学方法在动力系统研究中的重要性1 2 】，并 在2 0 世纪3 0 年代和他的学生h e d l u n d 进一步发展了符号动力学，并将它用于 变分学和微分几何中，首次将符号动力系统作为一个独立的学科正式提出这期 间b i r k h o f f 也利用符号动力学的方法对动力系统展开研究1 3 】从2 0 世纪6 0 年 代开始，符号动力学逐渐应用于维映射的研究中，不断发展和完善其中s m a i e 研究的马蹄映射就是一个可用符号动力系统进行很好描述的典型1 4 1 通过对一些 实际模型( 例如细胞自动机和细胞神经网络j 的深入研究后发现，由一维亏三穷j l 孚 列构成的符号空间存在局限性于是符号动力系统的研究进一步向高维拓屡与 延伸期间b e r g e r k a s t e l v n 和r m r o b i n s o n 等人探讨了有关高维符号主一：等兰 的几个问题，特别是有限型子移位拓扑熵的可计算性的研究1 5 1 9 7 7 年，m i l n o r 和t h u r s t o n 完成了讨论一维映射符号动力学的长篇预印本揉捏理论i 引与此 同时g u c k e n h e i m e r 、c o l l e t 、e c k m a n n 等人从数学的角度完成了对一维映射的 符号动力学的详细讨论 到了8 0 年代。随着混沌理论的兴起，符号动力系统也被视为混沌系统的原 型，进而将符号动力系统的行为特征作为混沌的描述成为混沌的一种严格的数学 定义，符号动力学有了更广阔的生存与发展空问1 9 8 1 年j f o r d 为一篇关子符号 动力学的纯数学综述文章写了序言1 9 j ，强调丁符号动力学方法对物理学基磁研元 的重要意义此后，s i l n i k o v 等人用符号动力学方法讨论了著名的l o r e n z 乃程t 】n 除此之外国内外众多数学、物理学家在符号动力系统的理论、应用和表示等多 l 绗沦 领域作了一系列探索取得了许多重要的成果例如：在讨论一些数学模型的复杂 性时，由于经常要借助符号动力系统的有限型子移位的思想与方法，在一维符号 动力系统中，有限型子移位得到了较系统的研究，得到了一系列完整的结果和广 泛的应用，如：强拓扑混合性与弱拓扑混合性具一致性：拓扑混合性蕴涵正拓扑熵 和混沌；拓扑熵等于其转移矩阵的谱半径等等此后，一些学者开始逐渐将对一维 符号空间上的有限型子移位的研究，从有限摹数的扩大到无穷基数，并讨论了无 穷基数的一维符号空间上的有限型子移位的混沌性状与此同时，越来越多的众 多学者开始将目光投向了高维符号动力学 1 1 - 1 4 随着各学科间的不断交叉、融 合、渗透，不断促使人们对符号动力学的理论进行探索与完善，符号动力学得到 了更加迅速的发展，其应用也将更加广泛 1 1 2 符号动力系统的基本定义及定理 近十几年来，动力系统的研究不断向各个应用领域渗透、发展，动力系统展 示了其广泛的应用前景，例如在细胞神经网络等领域，得到了一系列有意义的结 果首先简要介绍本文需要用到的动力系统相关知识 定义1 1离散拓扑动力系统 设x 为紧致度量空间，f ：x x 为从x 到自身的连续映射，称x 上连续 自映射序列 ，o ，f ，f 2 ) ，为x 上由连续自映射，经叠代生成的离散拓扑半动 力系统 当，为x 上自同胚映射时，存在相反方向的叠代，则有 ，厂n ，厂1 ，o ，：厂钉，) ， 称之为x 上由自同胚，经叠代而生成的离散拓扑动力系统 定义1 2 子系统 设( x ，) 为紧致系统，若紧致子集cx 对，不变，即 ，( ) c ， 则把，在上的限制映射： f i x o ：x u _ x n 所生成的紧致系统( x o f i x 。) 或f 1 x 。，称为( x f ) 或，的子系统 一 一 i i 一 霉 j ， 、 t j ， 一 ，：j 1 绪论 定义1 3轨道 设x 是紧致度量空间。广：x _ x 为一个自同胚映射对于任意的卫x ， 集合 ( 1 ) o r b l ( x ) = ，血( x ) l k z ) ( 2 ) o r b l ( x ) = ，七( x ) l k z + ) ( 3 ) ( ) r b 一( z ) = ，七( 丁) i 七z 一) 分别称为离散动力系统，过点z 的轨道、正半轨道和负半轨道显然， o r b l ( x ) = 0 7 b ( x ) u0 r 。b j 一( z ) 定义1 4符号空间 设整数k 2 ，记s = o ，1 ，七一1 ) ，称s 为“由k 个符号组成的状态空 间” 作拓扑积s z = s = s s = ：t ：= ( ? z 一2 ，z 一1 ，z o ，z 1 ：z 2 ) l 如s z 定义s z 上的度量d ( z ：y ) = m a x 丛鲁掣ii z ，z ，y s z ， ，( ，) 为s 上的度量，作如下定义：若以= 纨，则p ( ：y i ) = o ；反之p ( x i ，y i ) = 1 称由有限k 个符号( 状态) 生成的紧致的、完备的、完全不连通的度量窄间 s z 为k 一双边符号空间也可把s z 记为七 定义1 5序列包含关系 对于一个有限长度的序列n = ( a o ，z 1 ，a n 1 ) 钉1 ，n fes t = 0 ，1 ，、 一 l ，若存在m z ，使得z m + i = a i 丁s z 。称。出现在丁中，或称丁包含一一一。 o z ，反之记为o z 定义1 6柱形 设m z ，m 【n o ，t 1 1 ，一1 】= 丁s z i 丁m “= 啦，f = 0 ，1 ，n 一1 ) 称这 样的集合为s 上有限序列( a o ，口1 ，! a n 1 ) 上的柱形易知，柱形是既开且闭的 s z 上有由全体柱形构成的可数拓扑基则s z 的每一个开集均可写成可数个柱 形的并 定义1 7s z 上的转移自同胚仃l ，仃尺 仃l ：s z 叫s z ，定义为【仃l ( 丁) 】l = 以+ 1 ，v x s z ，f z 即在仃工的作用下， 3 1 绪沦 点丁的坐标依次向左移一位 仃r ：s z s z 定义为【仃月( 丁) ，= 以一1 协s z ，i z 即在o b 的作用下， 点卫：的坐标依次向右移一位称盯工和仃r 为”双边尼一符号空间铲上的转移自 同胚” 显然，( s z ，盯尺) 和( s z 仃l ) 则构成双边离散动力系统 定义1 8不变集，强不变集 设集合l c 铲，满足仃( y ) cl i 则称l 为a 一不变集；满足0 0 ，) = 则称 】+ 为仃一强不变集 定义1 9子转移 令仃= 仃尺或o l ，若ac | l ：是一个紧致了集且对盯不变，则称限制映射 一 = 盯l ：a _ a 为仃的子移位 令人c 七，且人对仃不变，则一定存在u 铲，使得人= 人= 丁 l v n - kz 0 1 若中元素- i 、数有限，则称盯的不变闭了集人c k 或于移 位仃 是有限型的任何有限型子移位均与一个2 阶有限型子移位拓扑共轭，其性 质可由与其相对应的转移矩阵a = ( j ) 完全决定， 4 巧= o ：称 a 为非周期的，若3 n 0 ，当钉n 时，使n 乙 0 v o i j 七一1 定义1 1 1拓扑传递和拓扑混合 设( x ，) 为紧致系统，x ，：xxx _ x xx ，是拓扑传递的若存在丁x 使得丽= x 即，的轨道在x 内处怂 稠密 ，是拓扑弱混合的，若，是拓扑传递的；，是拓扑强混合的，若对任意非 4 ， ， 一， 一 一 1 绪论 空开集u ，vcx ，3 n 0 ，使得，n ( u ) nv 0 ，n 引理i i i t s 一1 6 】 ( 1 ) ( 人，仃) 是拓扑混合的，当且仅当其转移矩阵a 是非可约的且非周期的； ( 2 ) 仃a 的拓扑熵为其转移矩阵a 的谱半径的对数，即e n t ( c r a ) = z o g ( p c a ) ) ， 其中p ( a ) 是月的谱半径； ( 3 ) 若( 人盯) 的转移矩阵月是非周期的，则o a 的非游荡点集q ( 吼) = 人 1 2 细胞自动机的定义及研究背景 1 2 1 细胞自动机研究背景 细胞自动机最初由j o h nv o nn e u m a n n 于1 9 5 0 年代提出，在形态表现上细胞 自动机是一个离散型的动力系统当细胞自动机在电脑上模拟时，几乎可以复制 出类似于自然界当中实际发生的动力系统行为，这使得细胞自动机成为了研究复 杂系统行为的最初理论框架，c h r i s t o p h e rl a n 昏o n 由此提出”人工生命”( a r t i f i c i a l l i f e ) 这个名词，细胞自动机便是人工生命的第一个雏形m ，并且变成复杂性科 学或者说是复杂适应性系统的其中一支从数学角的度看细胞自动机是由一些 特定的细胞( c e l l ) 组成，每一个细胞可以具有一些状态，但在某一时刻只能处于 一种状态之中随着时间的变化( 称作叠代过程) ，每一个细胞根据周围细咆的情 形，按照相同的法则改变状态从人工生命的角度看，c a 可以视为一个让许多单 细胞生物生活的世界。在设定好初始状态后，它们便按照同一个规则演化丈兰就是 c a 的基本思想 设计一个细胞自动机需要包含以下四个部分：决定细胞活动空间的嚣专之 义细胞可能具有的状态数：定义细胞改变状态的规则；设定细胞自动机中各个细 胞的初始状态细胞自动机在细胞活动的空间上，可以是一维的，二维的，三维的， 或更高维度通过不同的设计，细胞自动机可以展现无限的多样性最让人惊异的 是有些细胞自动机可以产生存在于大自然的景象，例如贝壳上的图案，雪花的结 构，蜿蜒的河流等等另外也可以发现，这些小方格的变化似乎蕴含了许多真实 生命的特质，例如细胞自动机中的细胞们会像有机生物一样，有移动、生长、灭 亡与自我复制等类似行为 就形式而言，细胞自动机有三个特征：甲行计算( p a r a l l e lc o m p u t a t i o n 每一 个细胞个体都同时同步的改变；局部的( 1 0 c a l ) ：细胞的状态变化只受周国领域虎 细胞的影响；一致性( h o m o g e n e o u s ) ：所有细胞均受同样的规则所支配有些研究 学者更是进一步思考：我们存在的这个宇宙是否就是一种极其复杂的细胞自机 机理论物理学家s t e p h e nw o l f r a m 就指出，细胞自动机的数学架构与一些造成真 实世界的复杂物理系统的数学架构完全一样，并于2 0 世纪8 0 年代号召对细胞自 动机进行简化提出状态数为2 邻域半径为l 的初等细胞自动机( e l e m e n t a r yc a ) 的规则及运行条件w o l f r a m 在详细分析研究了一维细胞自动机的演化行为，和 大量计算机模拟的基础上，将初等细胞自动机按行为模式分为四类： 1 固定值型：经过若干步演化后停留在一个固定的状态，不随时间变化而变 化( 如图2 1 所示) ； 2 周期型：经过一定时间的演化，趋于一系统简单的固定结构或周期结 构( 如图2 2 所示) ； 3 混沌型：自任何初始状态开始，经过一定时间演化后，表现出混沌的非周期 行为，处于一种完全无序随机的状态，几乎找不到任何规律( 如图2 3 所示) ： 4 复杂型：演化过程中可能产生复杂的结构，这种结构既不是完全的随机混 乱又没有同定的周期和状态( 如图2 4 所示) o f 。- - m l p 图1 1e c a 规则1 2 8 的演化图图1 2e c a 规则2 7 的演化图 图1 3e c a 规则9 0 的演化图图1 4e c a 规则5 4 的演化图 w o l f r a m 对细胞自动机的简化极大丰富了细胞自动机理论，引起了科学界的 ， i l f t l 绪i ：仑 广泛关注随后。n p a c k a r d 和c l a n g t o n 提出了“混沌的边缘”( e d g eo fc h a o s ) 的 概念【1 8 】，这是当前复杂性科学研究的一个重要成果值得一提的是。在2 0 0 2 年， w o l f r a m 在大量计算机模拟和经验观察的基础上创造性地称基本细胞自动机及 其研究方法为一种新科学( an e wk i n do fs c i e n c e ) t 1 9 2 0 0 2 年以来，为了从数学角 度对w o l f r a m 的基于计算机模拟和经验观察得到的结果给出严格解释，著名非 线性学者l o c h u a 等人结合他们的细胞神经网络的研究成果，用非线性动力学 的思想对其进行了一系列数学上的刻划，极大地推动了人们在理论上进一步对基 本细胞自动机的研究【2 2 】一1 2 4 】 细胞自动机以简单的规则，却能够产生复杂的动态交互现象，显然不该只是 以一个数学游戏来看待近些年来，细胞自动机已被运用于不同领域的研究，包括 通讯、计算、建设、生长、再生、竞争及演化，其巨大的应用前景越来越受到人 们的关注 。 1 2 2 一维基本细胞自动机及逻辑表示 细胞自动机是一类特殊的有限状态机，是与连续c a n t o r 映射动力学系统 相对应的离散动力学系统，具有时间、空间和状态的离散性构成细胞自动 机四个基本要素分别为：细胞( c e l l ) 、网格( 1 a t t i c e ) 、邻域( n e i g h b o r h o o d ) 及规则 ( r u l e ) 1 2 5 1 细胞自动机可以是一维、二维、三维或更高维；网格指细胞活动的空 间：邻域一般指某个细胞自身及其直接相邻的细胞；规则则规定了细胞之间以 何种方式相互作用而基本细胞自动机指的是最简单的一维情况，即所有细咆 ( g ，f = ，一2 ，一1 ，0 1 ，2 ) 均匀排列在一条直线上，细胞邻域为中心细胞与互 右最邻近的一个细胞，细胞状态为o 或j 两个状态这样每一个细胞和它峦0 瓴屠 可以表示如下： 圈盈 黑色方格是当前细胞，两边的灰色方格是它的邻居由于状态集只有 0 ，1 ) 两个状态即方格只能有黑、白两种颜色，那么任意一个细胞加上它的两个邻 居，3 个细胞的所有可能状态数为2 3 ，如下图示： _ ll 7 一1 一缔论一一一 表示的状态分别是：0 0 0 0 0 1 ，0 1 0 ，0 1l ，1 0 0 1 0 1 ，1 1 0 1 l1 考虑细胞。的当前状态为 t ：，其左右两个邻居的状态分别为z ：一1 和z t 件l ，在e c a 的局部规则f ：s 3 _ s 作 用下，细胞g 在下一状态输出为： z ：+ 1 = f ( x i 一1 ：z ：，z ：+ 1 ) 输出的所有可能状态为2 ，故共得到2 2 3 = 2 5 6 个e c a 局部规则故每一个e c a 局部规则均可唯一与一个逻辑函数的真值表相对应，如表1 1 所示： z ：一1 z ； 丁：+ 1 t ：“ oo00 y o 1001 一y 1 2o1o 7 2 30ll 仇 4l00 饥 5lo1 一y 5 6 11 0 1 6 7lll 1 7 表1 1 ：e c a 局部规则对应的逻辑真值表 其对应的局部规则编号定义为： n = ：0 1 i 2 。 由于每个真值表可转化为布尔表达式，因此局部规则也可由布尔表达式来表示 记每一个规则对直的全局映射为人n = 0 1 2 5 5 v 3 规则6 2 为例奠布j i 表达式为： 歹6 2 ( z ) i = z i l 磊。豇一1 黝e 五一1 瓢z 件1 z ，其中“”，“o ” 及“一”分别表示“和( a n d ) ”，“异或( x o r ) ”和“非( n o t ) ”逻辑运算。 1 3 论文的主要内容与结构 本文借助符号动力系统的相关定义与理论对c h u a 的分类中的周期类规则进 行研究发现这类规则中也蕴含着丰富而且复杂的动力学性质由于从鲁棒性角 度周期类规则被分为三类：鲁棒周期1 规则鲁棒周期2 规则鲁棒周期3 瓶 则其中前两类细胞自动机规则的符号动力学性质已有了一定的研究“3 4 j i 正 明了在鲁棒周期1 和周期2 规则中，共有1 4 个非鲁棒b e r n o u l l i r r ，一移位规则 本文将选取鲁棒周期一l 规则中的规则9 6 研究该规则的复杂动力学性质另一方 8 t ， p 一 1 绪论 面周期3 规则6 2 的符号动力学性质的研究是本文的熏点作为鲁棒周期3 规 则中的唯一成员，6 2 号本身就带有某种特殊性更让人意外的是，在规则6 2 的作 用下，选取一些合适的初始状态，竟能演化出丰富多样的周期结构，例如滑翔机 这也为以后的研究提供了一个方向促使我们进一步思考能否找到规则6 2 中碰 撞与逻辑算子间的联系，完善其相关理论，进而推广到其他类型规则的研究中此 外，6 2 号规则还具有正的拓扑熵和一个混沌的子系统，这也就意味着该规则具有 l i y o r k e 意义下的混沌且也具有d e v a n e y 意义下的混沌 本文的结构安排如下：第2 章研究鲁棒周期1 规则中的非鲁棒b e r n o u l l i 移 位性质以规则9 6 为代表，利用树图及其f o r w a r dt i m e 丁映射分析了该规则的定 性性质，发现该规则具有非鲁棒b e r n o u l l i 移位特征利用符号动力学的相关理论 与方法，严格证明了9 6 号规则具有混沌的子系统本文第3 章讨论唯一一个鲁棒 周期3 规则规则6 2 展现其丰富且复杂的动力学性质系统分析6 2 号规则中 的存在的滑翔机及其相互作用，包括演化过程中出现的基础滑翔机，滑翔机之间 的碰撞以及滑翔枪而这些现象之前都被认为仅存在于w o l f r a m 的复杂娄规则 5 4 和ll o 号规则中另外。类似规则9 6 ，严格证明了6 2 号规则同样定义了一个复 杂的子系统，且该子系统不仅拓扑混合还拥有正的拓扑熵最后一章是对全文的 总结，并进一步提出未来研究方向的展望 9 2 周期1 规则一一9 6 号规则的符号动力学性质 如前所述，w o l f r a m 将细胞自动机分为四类，即固定值型、周期型、混沌型 以及复杂型同时，c h u a 将2 5 6 个基本细胞自动机规则分为六类具体为：周期1 规则、周期2 规则、周期为t ( t = 3 6 ) 规则、b e r n o u l l i 西一移位规则、复杂 b e r n o u l l i 移位规则以及超b e r n o u l l i 移位规则利用两个同胚映射1 2 6 】，1 4 1 1 4 1 ，又可将 2 5 6 个局部规则映射分成8 8 个拓扑共轭等价类，每一类均具有相同的动力学性 质 圈 图2 12 5 6 个规则分为6 类的情况图2 28 8 个等价类分为6 类的情况 接着又从鲁棒性角度进一步将8 8 类规则中的7 0 类细分为：2 6 个鲁棒周期一l 规 则、1 3 个鲁棒周期2 规则、1 个鲁棒周期3 规则及3 0 个鲁棒b e m o u l l i c r ，移位 规则【2 7 对于w o l f r a m 的第二类规则，或是c h u a 的周期类规则，之前许多文献 大都认为这类规则的动力学性质相对简单事实上c h u a 的周期一l 类规则中p 勺 若干规则蕴含丰富而且复杂的动力学性质1 2 & ，这给我们的研究带给许多惊喜 对于周期1 规则，文【2 9 】中绐出了详细的证明：不管在有限长度还是双边无 穷的情况下，该类规则具有鲁棒性，即对任意给定的初始状态，在该类规则的作用 下，最终状态大都趋于周期l 的吸引子然而，对于这类规则，除了鲁棒性的周期 1 吸引子外，是否还具有非鲁棒的其它类型的吸引子? 文【2 8 】从符号动力学的角 度证明了规则4 0 、1 7 2 以及1 6 8 均具有非鲁棒b e r n o u l l i 移位特征因为这3 个 规则分别属于不同的伞局等价类，而在同一全局等价类中的不同规则具有相同的 动力学性质故由基本细胞自动机的全局等价分类理论知，在鲁棒周期1 规则 中，共有1 2 个非鲁棒b e r n o u l l i 仃，一移位规则本章将以鲁棒周期1 规则| | 1 的规 则9 6 为例讨论该规则的复杂动力学性质 1 0 一， 一 2 周期1 规则一一9 6 号规则的符号动力学性质 2 19 6 号规则的b e r n o u l l i 移位性质 本节将利用规则9 6 的树图以及f o r w a r dt i m e 7 映射来证明该规则具有非鲁 棒b e r n o u l l i 移位性质，求解决定其b e r n o u l l i 移位吸引子的参数 2 1 19 6 号规则的树图 树图事实上是借用了图论中的概念，但在c a 背景下提出的树图意义于图论 中的树图有所区别在c a 背景下考虑长度为l 的序列2 工种不同状态组合，将 每一个二元序列从左到右转化为十进制数表示：钉= e i 矧- 1 ，2 ( z q 一) 并将这十进 制数作为树图中的结点例如，长度为4 的序列( 0 1 0 1 ) 转化为十进制数表示即 为：2 3 0 + 2 2 1 + 2 1x0 + 2 0 1 = 3 在树图中用叫表示考虑周期边界条 件( p e r i o d i cb o u n d a r yc o n d i t i o n ) ，在规则的作用下，树图展示了长度为工的所 有2 l 种不同状态组合间的演化关系 在有限长度的符号序列空间中，规则人t 的树图可以反映该规则轨道的渐近 性质，即使序列长度比较短，只要仔细观察分析，也能从规则人_ 的树图中发现该 规则的一些定性性质在规则n 的树图中，若存在一个吸引域为周期礼的轨道， 即没有点收敛到这个轨道则称这个轨道为规则n 的周期嘲的伊甸园孤岛( i s l e o fe d e n ) 1 2 3 1 ，1 2 r 为了判断不同吸引子和不同伊甸园孤岛的鲁棒性，文【2 9 】给出了鲁棒性系 数p m 简单的计算公式，对于长度为l 的宁列其所有不同状态组合总数为2 2 p m = ( 吸引子m 或伊甸园孤岛m 中包含的结点的个数) 2 工对于所有鲁棒周期 1 规则来说，鲁棒周期1 吸引子或鲁棒周期1 的伊甸园孤岛的鲁棒性系数均运 远大于其它假设也存在的周期t ( t 1 ) 的吸引子或伊甸的孤岛这在反映鲁棒 周期1 的规则均具有鲁棒性的同时，也给寻找鲁棒周期1 规则的非鲁格：j 、毛：二 提出了挑战 通过对三的不同取值的大量计算机模拟。发现9 6 号规则具有非鲁棒的 b e r n o u l l i 移位性质，虽然其吸引域相对较小决定其b e r n o u l l i 移位吸引子的参数 为：p = 2 ，仃= - 1 ，丁= 1 ，且与细胞个数l 无关以长度l = 6 ，7 ，8 、9 ，1 0 为例， 表2 1 表2 5 分别展示了取l = 6 ，7 ，8 ，9 ，1 0 时，对应树图的结构 2 周期l 规则一一9 6 号舰则的符号动力学性质 _ 一 一、 一一一一 ( a ) 只有一个周期2 的伊甸园孤岛；( b ) 具有b e r n o u l l i 移位特征，参数为p = 2 盯= 一1 7 - = 1 ： ( c ) 这个周期- 2 伊甸园孤岛的鲁棒系数为p = 委= 0 0 3 1 2 5 、 一 ”一 “ ，一 ， ， j ， ? 1 、j f r a ) 只有一个周期3 的伊甸因孤岛：0 ) 具有b e r n o u l l i 移位特征，参数为3 = 2 1 口= 一1 - = ： f c ) 这个周期3 伊甸囤孤岛的鲁棒系数为p = 未= 0 0 4 6 8 7 5 表2 1 ：l = 6 时，规则9 6 不同类型的动力学性质 1 2 ， 彳 j - 2 网期1 规则一一9 6 号规则的符号动力学性质 一- - r一h _ _ 一_ _ 一 ，- 。一， 、 、l i - 一n f a ) 只有一个用期7 的伊甸因孤岛；c o ) 具有b e m o u u i 移位特征，参教为p = 2 仃= - 1 7 = 1 ： ( c ) 这个周期7 伊甸因孤岛的鲁棒系数为_ p = 丢= 0 0 5 4 6 8 7 5 表2 2 ：l = 7 时，规则9 6 不同类型的动力学性质 、 2 周期l 规则一一9 6 号规则的符号动力学性质 ，一一一一一卜、一 i 一一一一一4 一 c a ) 只有一个周期2 的伊甸园孤岛：( b ) 具有b e r n o u l l i 移位特征，参数为3 = 2 1 盯= 一1 7 = 1 ： ( c ) 这个周期一2 伊甸园孤岛的鲁棒系数为p = 而2 = 0 0 0 7 8 1 2 5 一一 一i r i ，一o 一 一 f a ) 只有一个周期8 的伊甸园孤岛：f b ) 具有b e r n o u l l i 移位特征参数为3 = 2 1 e l = 一1 一= 1 ： ( c ) 这个周期一8 伊甸园孤岛的鲁棒系数为p = 叁= 0 0