（基础数学专业论文）二维符号动力学与细胞自动机.pdf

二维符号动力学与细胞自动机 摘要 j o h nv o l ln e u m a n n 在1 9 5 0 年代提出的细胞自动机是一种时白j 、空间与状态 都离散的数学模型在型态表现上每个细胞自动机都是一个离散型的动力系统 通过设计不同的局部规则，细胞自动机可以展现无限的多样性和复杂性，产生复 杂的动态交互和自我复制现象即使是最简单的初等细胞自动机，不仅具有丰富 的动力学行为，又具有适合超大规模集成电路上实现的并行信息处理结构细胞 自动机自产生以来，就被广泛运用于社会学、经济学、军事学和科学等不同领域 的研究特别地，它为动力学系统理论中有关秩序、紊动、混沌、非对称、分形 等系统整体行为与复杂现象的研究提供了一个有效的模型工具 符号动力学是研究动力系统动力学行为的一个重要工具近些年来，在生物 学、化学、工程和物理学等研究领域提出的众多实际模型中，人们发现在刻画其 复杂性时往往要涉及高维符号动力系统的理论与方法，特别是二维的对于同一 符号空间下不同的连续映射，如果能找到同胚映射使其能建立拓扑共扼关系则可 实现这些映射的拓扑共扼分类属于同一类下的不同映射具有相同的动力学性 质，可以看作是同一个系统 本文首先证明了二维符号空间上定义的8 种移位映射是拓扑共轭的，进一步 得到了二维符号动力系统与一维符号动力系统的拓扑半共轭关系由此，第3 章考 虑了具有n c u 脚邻域和状态集为 o ，1 ) 的二维细胞自动机的拓扑共轭分类本 章将二维细胞自动机与二维符号空间建立联系，定义t 2 2 5 = 4 2 9 4 9 6 7 2 9 6 个全局 i 摘要 映射，并利用四个同胚映射实现了所有全局映射的拓扑共轭分类，同时把此分类 过程进行了程序化设计本文认为上述分类所得的共轭类数目是最小的第4 章则 讨论了全局映射的动力学性质本章首先从符号动力学的角度分析了初等细胞自 动机规贝l j l 8 和5 6 的复杂行为随后，建立了二维细胞自动机与初等细胞自动机之 间的拓扑半共轭关系：并通过两个半共轭映射得到了2 4 个二维普适细胞自动机规 则同时，给出了它们的数字模拟结果，发现其演化情况与著名的“生命游戏”大不 相同本文的最后一章对全文作了总结，展望进一步研究前景 关键词：细胞自动机；二维符号动力学；普适性；拓扑共轭；n l 黜邻域：全局 映射 t w o d i m e n s i o n a ls y m b o l i cd y n a m i c sa n d c e l l u l a r a u t o m a t a 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 ) ，i n t r o d u c e db yj o h nv o nn e u m a n ni n1 9 5 0 s ，缸em a t h c - n m d c a m o d e l si nw h i c ht i l r m s p a c ea n ds t a t e 缸cd i s c r e t e i nt h er e p r e s e n t a t i o no f p a t t e r n s ，c e l l u l a ra u t o m a t aa r cd i s c r e t ed y n a m i c a ls y s t e m s 。t r o u g hd i f f e r e n tl o c a lm l e s d e s i g n e d ，c e l l u l a ra u t o m a t ae x h i b i ta l lk i n d so fv 跹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 e c o m p l i c a t e dv h e n o , 撒n o fd y 埘l i 【l 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 nd e m e n t a r y c e l l u l a ra u t o m a t a ( e c a ) w i t hv e r ys i m p l el o c a lr u l e sh a v er i c hd y n a l n i c a lb e h a v i o r s a n dh a v ep a r a l l e li n f o r m a t i o np r o c e s ss t r u c t u r e st h a ta r es u i t a b l et ob e i n gr e a l i z e di n v l s i s i n c ec e l l u l a ra u t o m a t ac a l l q ci n t ob e i n g ，1 h 呵h a v eb e e nw i d e l ya p p l i e di nt h e r e s e a r c ho fs o c i o l o g y ，e c o n o l n i c s ，s t r a t e g i e s ，s c i e n c e ，c t c e s p e c i a l l y ：c e l l u l a ra u t o m a t a p r o v i d ea l le f f e c t i v em o d e lf o rs t u d y i n gt h eg l o b a lb e h a v i o r sa n dc o m p l e xp h e n o m e n a i nt h et h e o r yo fd y n a m i c a ls y s t e m , m c ha so r d e r i n g ，t u r b u l e n c e ，c h a o s ，a s y n a n c t r y , f r a c t a l i t y ，e l c s y m b o l i cd y n a m i c si sa ni m p o r t a n tt o o lf o rm a t h e n m t i c a la n a l y s i s i nr e c e n t d e c a d e s ，a l li n v e s t i g a t i o no ft h ec o m p l e x i t yo ft h em o d d s ，e g ，t h o s ep r o p o s e di nt h e r e s e a r c ho fb i o l o g y ，c h c m o l o g y ，e n g i n e e r i n g ，p h y s i c s ，h a sa l w a y sr e l a t e dt ot h et h e o r y a n dm e t h o d so fh i g hd i m e n s i o n a ls y m b o l i cd y n m n i c s p a r t i c u l a r l yt w o - d i m e n s i o n a l f o rd i f f e r e n tc o n t i n u o u sn m p su n d e rt h es a l n cs y n 蔺b o i i cs p a c e ，i ft h eh o m o m o r p h i s m s c a nb e e nf o u n dt oe s t a b l i s ht h er e l a t i o n s h i po ft o p o l o g i c a lc o n j u g a c y ，t h e nt h e s ec o n - h i a b s t r a c t t i n u o u sn m p sc a nb e e nc l a s s i f i e d d i f f e r e n tl i m p sb e l o n g i n gt ot h es a i n ee q u i v a l e n c e c l a s sh a v eq u a l i t a t i v e l yt h es a r l 2 9d y n a m i c sa n dc a nb ev i e w e da so n e s y s t e n x f i r s t l y ，t h i sp a p e rr i g o r o u 如p r o v e s t h a t8s h i f tm o p sd e f i n e do nt h et w o - d i m e n s i o n a l s d n b o l i cs p a c ea r et o p o l o g i e a l l yc o n j u g a t e i na d d i t i o n i ti ss h o w nt h a to n e d i m e n s i o n a l s y m b o l i cd y n a m i c sa n dt w o d i m e n s i o n a ls y m b o l i cd y n a m i c sa f es e m i - t o p o l o g i c a l l y c o n j u g a t e b a s e do nt h i sw o r k ，c h a p t e r3s p a d i e st h et o p o l o g i c a lc o n j u g a c yc l a s s i f i c a - t i o no fg l o b a lm a p so ft w o - d i m e n s i o n a lb i n a r yc e l l u l a ra u t o m a t a ( 2 1 3c a ) w i t hn e u m a n n n e i g h b o r h o o d i l lt h i sc h a p t e r , 2 2 5 = 4 2 9 4 9 6 7 2 9 69 1 0 b a lm a p sc o r r e s p o n d i n gt o l o c a lr u l e so ft w o d i m e n s i o n a lb i n a r yc e l l u l a ra u t o m a t aa f cd e f i n e di nt w o d h n e n s i o n a l s y m b o l i cs p a c e b ye l n p l o y i n gf o u rh o m e o m o r p h i s m s ，a l lg l o b a lm a p sa r ec l a s s i f i e d w i t ht h ep e r s p e c t i v eo ft o p o l o g i c a le o n j u g a c y 。m e a n w h i l e 。a na l g o r i t h mi sd e v e l o p e d t oi m p l e m e n tt h i sc l a s s i f i c a t i o n ，a n di ti sp o i n t e dt h a tt h en u m b e ro f e q u i v a l e n c ec l a s s e s o b t a i n e di nt h i sp a p e ri sm i n i n m l c h a p t e r4d i s c u s s e st h ed y - m l i c so fs l 曲a ln m p s o fc e l l u l a ra u t o m a t a i 】1t h i sc h a p t e r , t h ec o m p l e xd y n m n i c a lb e h a v i o r so fe l e m e n t a r y c e l l u l a ra u t o m a t ar u l e s18a n d5 6a r ec h a r a c t e r i z 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 e s p a c e t h e n ，t h es e n l l t o p o l o g i c a lc o n j u g a c yb e t w e e nt h et w o - d i m e n s i o n a lb i n a r yc d - l u l a ra u t o l l l a t aa n de l e m e n t a r yc e l l u l a ra u t o m a t ai se s t a b l i s h e d ，a n d2 4u n i v e r s a lt w o d i m e n s i o n a lb i n a r yc e l l u l a ra u t o n m t al o c a lr u l e sa r ef o u n dv i at h i sr e l a t i o n s h i p f u r - t h e r m o r e s o l n en u m e r i c a ls i m u l a t i o n so fu n i v e r s a ll o c a lr u l e sa r cg i v e n w h i c ha r c d i f f e r e n tf r o mt h o s eo ft h e w e l l k n o w n “g a m eo fl i f e ”f i n a l l y , c h a p t e r5m a k e sab r i e f s u n m a r yo nt h i st h e s i s 。a n dp r o s p e c t sf o rf u t u r es t u d i e s k e yw o r d s ：c e l l u l a r a u t o n m t a ( c a ) ；t w o - d i m e n s i o n a ls y m b o l i cd y n m n i c s ； u n i v e r s a l i t y ；t o p o l o g i c a lc o n j u g a e y ；n e u m a n nn e i g h b o r h o o d ；g l o b a lm a p 浙江师范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。本人完全意识到本声明的法律结果由本人 承担。 储签名：曼讳垮 日期：砑年。岁月夕 日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关机关或机构送交论文的复印件和电子文档，允许论文被查阅和 借阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大 学可以用不同方式在不同媒体上发表、传播论文的全部或部分内容。 保密的学位论文在解密后遵守此协议。 名：参哟新潞防坛吼矽 月 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例。我的学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明并详细列出有关文献的名称、作者、年份、 刊物名称和出版文献的出版机构、出版地和版次等内容。论文中 未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ： 指导教师： 互讳锑 泐占亏 1 绪论 1 1 符号动力学的研究背景 1 1 1 符号动力学发展的简要回顾 符号动力学是研究符号动力系统的学科这种系统的状态均可表示为有限个 符号组成的无穷序列，而由任一状态点引出的运动轨道可由表示该状态的无穷序 列通过简单的移位规则来确定许多复杂动态系统均可经过变换等价于这种系 统，从而可通过对比较简单的符号动力系统的分析来研究一般动力系统的行为 这种方法在计算机科学、物理学、密码学、通讯等领域有着广泛应用，特别在混 沌等复杂行为研究中占有重要地位 符号动力学起源于动力系统的抽象拓扑理论研究早在1 8 9 8 年，h a d a n m r d 就 将符号动力学技巧用于负曲率曲面上的测地线的研究1 1 9 2 1 年，m o r s e 首先注意 到符号动力学在动力系统研究中的重要性【2 j 1 9 2 7 - 1 9 3 5 年，b i r l d l o 趼始应用符 号动力学方法研究动力系统f 3 】1 9 3 8 年，m o r s e 和h e d l u n d 发表了研究动力系统拓 扑理论的论文，题目就称为符号动力学【4 】，这代表了符号动力学作为一个独 立学科的诞生。而后，l c v i n s o n 用符号动力学方法和思想研究了受迫v a n d c r p o l 振 动方程，以致后来促使s n m l e 获得了构造马蹄映射的灵感【5 】5 1 9 6 0 年代至u 1 9 7 0 年 代，s m a l c ，b o w e n ，r u l l c ；s i n a i 等人在微分动力系统和遍历理论方面发展了符号 动力学理论同时，m e t r o p l i c ，m s t e i n 和p s t c i n 等人开始将符号动力学实用化【6 】 然而，在一些实际模型( 如细胞自动机和细胞神经网络) 的深入研究中发现由一 维无穷序列构成的符号空间有着局限性于是，符号动力系统的研究进一步 向高维延伸与发展。此间。b c r g c r , k a s t e l y n 和r m r o b i n s o n 等人探讨了有关高维 符号动力系统的几个问题，尤其是有限型子移位拓扑熵的可计算性【8 - 1 0 】随后， m i l n o r 和t h u r s t o n 于1 9 7 7 年完成了讨论一维映射符号动力学的长篇预印本揉捏 理论，但过了十多年才正式发表【1 1 1 另外，o u c k e n h c i n z e r ，c o l l e t ，e c k n m u n 等也 着重从数学方面详尽地讨论了一维映射的符号动力学 在1 9 8 0 年代，由于混沌理论热潮的兴起。使符号动力学有了用武之地，同时 也使其得到了迅速发展1 9 8 1 年，j f o r d 为一篇关于符号动力学的纯数学综述文 章写了序言【1 2 】1 2 ，强调了符号动力学方法对物理学基础研究的重要意义随后， s i l n i k o v 等人用符号动力学方法讨论了著名的l o r e n z 方程【1 3 j 同样，国内外众多数 学、物理学家在符号动力系统的理论、应用和表示等多个领域作了富有成效的 研究和探索取得了一系列重要的成果【1 4 - - 1 7 例如，对于有限基数的一维符号空 1 1 绪论 间上的有限型子移位的研究已有很大进展，有的学者把有限基数扩大到无穷基 数，并讨论了无穷基数的一维符号空间上的有限型子移位的混沌性状与此同时， 随着越来越多来自生物学、化学、工程和物理学等领域的数学模型的出现，人们 发现在分析它们的动力学行为时往往要涉及高维符号动力系统的理论与方法，这 极大地促使着高维符号动力学自身理论的不断发展与完善【1 8 - - 2 1 】总之。由于符号 动力系统在混沌理论研究和各种数学模型复杂性分析中的重要作用和特殊地位， 在作为研究工具的同时，符号动力学自身的理论和方法也得到不断的丰富和发 展 1 1 2 二维符号动力学的研究现状 一维符号动力学的相关概念可以非常自然地拓展到高维符号动力学，当然首 先是二维的在二维符号动力系统中，符号空间中的元素为双边无穷的矩阵j 而 非双边无穷的序列，这种系统更接近于铺砖式分片系统( t i l i n gs y s t e m s ) 和统计力 学( s t a t i s t i c a lm e c h a n i c s ) 22 1 近些年来j 在研究众多数学模型中，人们发现在讨论 其复杂性时经常要借助于符号动力系统的有限型子移位的思想与方法在一维 符号动力系统中，有限型子移位得到了较系统的研究，有着完整的结果和广泛的 应用【1 5 2 3 - 2 引例如：强和弱拓扑混合性是一致的；拓扑熵等于其转移方阵的谱半 径；拓扑混合性蕴涵着正拓扑熵和混沌等等然而，上述问题在高维的情况下变 得异常困难，远比一维符号动力系统的情况要复杂与艰难例如在二维符号动力 系统中，由两个转移方阵决定的有限型子移位是否为空集的问题都是不可确定 的( u n d c c i d a b l c ) 2 1 | ， 从1 9 9 0 年代以来j 众多学者在二维符号动力系统的理论和应用等多个领域 作了富有成效的研究和探索，取得了一系列重要的成果 2 p2 9 】在大量的研究中， 一个基本的问题是如何计算或估计有限型子移位的拓扑熵首先，文 1 0 】拓展了 拓扑熵的概念，将二维有限型子移位的拓扑熵定义为e n t ( x ) = l i m l o g r b n ( x ) j ， 其中l 鼠( x ) l 为子移位x 的他阶方阵的基数。并证明了此拓扑熵也为拓扑共轭不 变量然而对任意二维有限型子移位，要计算其拓扑熵非常困难在众多由实际 模型产生的二维有限型子移位中，文【3 0 】得到了精确的冰模型( i c em o d e l ) 的拓扑 熵。2 0 0 5 年文 2 7 1 在二维有限型子移位上引进了系统结构( s y s t c m a t i cs c h e m e ) 。即 两个第1 1 次转移方阵a 。和b 。，这使得拓扑熵的计算转化为计算a 。或b 。最大特征 值的增长率同时还有许多关于拓扑熵计算和估计的研究1 1 8 2 0 ，3 1 3 3 1 尽管如 此，依然有许多有限型子移位的拓扑熵没有得到解决例如当两个转移方阵都 11、 为f 1 1 l 时，其决定的有限型子移位的拓扑熵到目前还没解决另外，文【3 4 证 l 0 2 l 绪论 明了二维有限型子移位的最大拓扑熵的测度不唯一由此，人们引入了各种统计 测度用以描述有限型子移位的动态复杂性这种统计测度包括强、弱最小排除系 统熵( 或增长率) 【删、几乎最大熵【2 6 j 、投射熵( p r o j e c t i o n a le n t r o p y ) 3 6 等等 除了拓扑熵外，混合性也是一个用来研究系统复杂性的工具我们知道 在一维情况下，混合性蕴涵着正拓扑熵，但是这个结论在高维情况下就不再 成立嘲在高维中，拓扑混合性是一个比较弱的性质例如，在二维中，存在 拓扑混合的有限型子移位使得其拓扑熵为零【鲫正拓扑熵往往可通过加更强 的混合性而得到关于混合性的研究，已有一些确凿的结论删例如，混合性 等价于两个第n 次转移方阵厶和玩m 2 ) 是原始的( p r i m i t i v e ) 但在实际问题 中，要应用此结论却困难重重为此，文 3 9 】提供了一种可验证方案( c h e c k a b l e s c h e m e ) ，使得对a n 和风m 2 ) 是否为原始的( p r i m i t i v e ) 的验证转化为只要验 证a 和鼠( 七3 ) 是否为原始的( p r i m i t i v e ) ，由此来得到二维有限型子移位是否具 有混合性另外，文【2 6 】研究了弱混合性与几乎最大熵之间的关系同时，在上述 研究中，人们往往还借助遍历论的理论、思想与方法讨论子移位的动力学性质 值得注意的是，到目前为止，人们对在二维符号动力系统中有限型子移位的研究 还远不充分，所获结果也显得零星当然，在一维符号动力系统中，目前也仍面临 大量有待解决的问题，尤其是一般性子移位的动力学性状的分析 1 2 细胞自动机的定义及其基本理论 1 2 1 细胞自动机的研究与发展 细胞自动机( c e l l u l a ra u t o m a t a ，简称c a ) 是一类特殊的有限状态机，是与连 续c a n t o r 映射动力学系统相对应的离散动力学系统，具有时间、空间和状态的离 散性，细胞自动机是由j o h n v 衄n e u m a n n 在1 9 5 0 年代提出的1 9 4 8 年，n e u m a n n 在 研究什么逻辑组织结构的自动机具有图灵机一样的自我复制特性【4 1 】”的问题时， 在s t a n i s l a w u l a m 的建议下，他在具有2 9 个状态的二维细胞空间上建立了一个具 有自我复制特性和普适计算能力的细胞自动机继n e u m a n n 之后，a w b u r k s 开始 了细胞自动机的理论研究嘲，但他提出的细胞自动机的结构过于复杂，这极大地 限制了细胞自动机的应用因此，从那以后关于细胞自动机的研究陷入了一个很 长的休眠期但在1 9 7 0 年代，随着计算机的普及，以c 0 n w a y 的“生命游戏”【鹳】( g a m e o fl i f e ，一种能够进行普适计算的结构简单的2 个状态8 个邻居的细胞自动机) 为代 表。细胞自动机的研究再度兴起细胞自动机的拓扑动力学研究始于h e d l u n d 4 4 1 9 6 9 年，h e d l u n d 从符号动力学的角度把一维细胞自动机看作是符号空间上移位 映射的自同态，并刻画了所有满的和开的细胞自动机的动力学行为1 9 8 0 年代， 3 l 绪论 s t e p h e nw o l f r a m 号召对细胞自动机进行简化，建议细胞自动机应具有简单规则 性、局部连接性及高度并行性，并且提出了状态数为2 邻域半径为1 的初等细胞自 动机( 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 ) 4 s 简化后的细胞自动机不仅具有适合 超大规模集成电路( v l s i ) 层次的简单规则结构和信息并行处理的局部互连结构， 而且具有复杂的动力学特性豳一5 3 l 。s t e p h e nw o l f r a m 对初等细胞自动机的性质进 行了深入的研究，提出了初等细胞自动机的规则及运用条件；并在大量的计算机 实验的基础上，通过观察特定规则产生的行为将初等细胞自动机按行为模式分为 如下四类 s 4 ，5 5 1 ： ( i ) 最终趋于一个空间平稳的状态，这里空间平稳是指每一个细胞处于相同的状 态( 如图1 1 所示) ； ( ) 状态最终演化进入简单的周期状态( 如图1 2 所示) ； ( l r ) 具有复杂的动力学行为，状态演化进入混沌状态模式( i n 图1 3 所示) ； ( ) 状态演化为更加复杂的模式，出现复杂的局部结构，或者说是局部性的混沌， 其中有些会不规则的传播( 如图1 4 所示) 图1 1e c a 规则1 3 6 的演化图 图1 2e c a 规n 5 6 的演化图 图1 3e c a 栅i 1 9 0 的演化图 圈1 4e c a ：规则1 1 0 的演化图 4 l 绪论 w o l f r a m 对细胞自动机的简化极大地推动了细胞自动机理论及应用的发 展，引起了包括数学家在内众多学者的关注当细胞自动机在计算机上模拟 的时候，几乎可以复制出类似于自然界当中实际发生的动力系统运作，这使 得细胞自动机成为了研究复杂系统行为的最初理论框架因而c l a n g t o n 提 出了“人工生命”( a r t i f i c i a ll i f e ) 这个名词，细胞自动机便是人工生命的第一 个雏形【5 6 】。并且变成复杂性科学，或者说是复杂适应性系统的其中一支同 时，n p a c k a r d 和c l a n g t o n 在对细胞自动机深入研究的基础上提出了“混沌的边 缘”( t h ee d g eo fc h a o s ) 这个概念m ，这是当前复杂性科学研究的一个重要成果另 一方面，细胞自动机的数学理论研究在各方面得到了发展，成果比较丰富，例如， 加性细胞自动机、等度连续的细胞自动机以及正扩张的细胞自动机的符号动力 学性质有着比较完善的研究m ，5 0 ，5 3 ，黯一删特别值得一提的是，2 0 0 2 年在大量的 计算机模拟和经验观察的基础上，w o l f r a m 仓l j 造性地称初等细胞自动机为一种新 科学( an e wk i n do fs c i e n c e ) 6 而后，l 0 c h u a 教授等人结合他们的细胞神经网 络的研究成果用非线性动力学的思想对w b l f r a m 的计算机模拟结果给予了一系列 数学上的刻画【6 2 6 7 】，极大地推动了人们在理论上进一步对初等细胞自动机的研 究 细胞自动机自产生以来，被广泛地应用于社会学、生物学、生态学、信息 科学、计算机科学、数学、物理学、化学、地理学、军事学等各个领域例如： 在物理学中，除了格子气细胞自动机在流体力学上的成功应用外，细胞自动机还 应用于磁场、电场等场的模拟，以及热扩散、热传导和机械波的模拟以及用来 模拟雪花等结晶的形成在计算机科学中，细胞自动机可以被看作是并行计算 机而用于并行计算的研究另外，它还应用于计算机图形学的研究中尤其在数 学中，细胞自动机为动力学系统理论中有关秩序( o r d e r i n g ) 、扰动( t u r b u l e n c e ) 、混 沌( c h a o s ) 、分形( f r a c t a l i t y ) 等系统整体行为与复杂现象的研究提供了一个有效的 模型工具因此，一方面细胞自动机的发展得益于相关理论的研究，如逻辑数学、 离散数学、计算机中的自动机理论，图灵机思想等；另一方面，细胞自动机的发展 也促进了一些相关学科和理论( 如人工智能、非线性科学、复杂性科学) 的发展， 甚至还直接导致了人工生命科学的产生另外，在表现上，细胞自动机模型还与一 些理论方法存在着较大的相似性或相对性 1 。2 。2 细胞自动机的基本概念 细胞自动机是一种时间和空间都离散的数学模型，即其时间、空间变量乃 至描述组成系统的单元细胞的状态变量都是分立的散布在规则网格中的每 个细胞取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更 5 1 绪论 新因此，构成细胞自动机有四个基本要素，分别是：细胞( 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 ) 【6 8 | 最简单情况下细胞可以取o 和l 两个状态网格 是指细胞活动的空间由此，细胞自动机可以是一维的，二维的，三维的，或更高维 度邻域一般指某个细胞自身及其直接相邻的细胞，常见的邻域有n e u m a n n c g 域 和m o o r e 邻域( 见图i 5 ) f 6 规则刚规定了细胞之间以何种方式相互作用 + 1 ) 歹 i黪戮阑 lr 黼 歪嘞 l 飞( 歹- 1 ) i 稚1 ) 歹 n e u m a n n 邻域 曲 x o + o ： + 1 ) 1 ) 黟缳 ( 舯 毛 瓢砌一1 )一1 ) j妇1 ) m o o r e 邻域 图1 5 二维细胞自动机常见的两种邻域 本文选择了具有n e u m a m a 邻域以及只有两个状态数的二维细胞自动机作为 研究对象如果用黑色方格代表状态“l ”，白色方格代表状态盯，贝j j n e u m a n n 邻 域中5 个细胞的所有状态组合共有3 2 种假设当前考虑的细胞为c 0 。在某 个时刻的状态为。移，其n e u m a 础邻域中四个邻居的状态分别为z ( 件l b ，u 1 ) ， 叶1 ) 和z ( i 一1 h 则在下一时刻该细胞的状态可用函数表示为 3 秘= ( z ( t + 1 ) j ，。i u 一1 ) ，。巧，j 艮u + 1 ) ，z o 一1 b ) ， 其中 o ，1 】，v ( i ，j ) z 2 易见，上述过程可由一个布尔函数真值表表 示，见表1 1 由此，局部规则编号可定义为= 3 ；：1 d 岛，其中危s 。 i = 0 ，1 ，3 1 显然，这样的局部规则共有2 2 5 = 4 2 9 4 9 6 7 2 9 6 个同时，由于每个 布尔函数真值表可转化为布尔表达式，因此局部规则也可由布尔表达式所表示， 且表示不唯一 1 3 论文的主要内容与结构 我们知道细胞神经网络( c n n ) 复杂性的分析往往需要借助于符号动力学的 理论、思想和方法文【7 运用二维符号动力系统的思想与方法研究了无穷多个变 6 1 绪论 表1 1 二维细胞自动机规则的布尔函数毒值袁 x ( i + i ) jo i ( j 一1 ) z 妇z i ( j + 1 ) x i - 1 ) j蜥x ( i + i ) jx i 0 - - 1 ) z 巧x i j + 1 ) x ( i - 1 ) 3聊 00 00 0 3 0 l 0 000 卢1 6 00o01 口l 1 0001 历7 0 0 01 0 伤 l 0 0 l 0 胁8 00011 风 1 0011 f 1 1 9 oo l0 0 反 】 0 l00砌 00101 风 l0101 屁1 0011o 风 1 o 1 l 0勉 001ll 岛 l0111助 0lo00 风 l10o0 勉 olo0l 伪 l10ol 3 2 5 o lo 1 0 3 1 0 l 1 ol0 岛6 01o11 3 1 1 l1 0 ll 庞7 01100 风2 lll00 统8 o ll01 3 1 3 1 1 。10l肠 011l0 岛4 ll110 触 0l王ll 尻5 l 1 1ll 尻1 量的c n n 系统，从符号动力学的角度刻画了q 小系统的二值输入一输出映射的 动力学性质，特别是讨论了某些移位映射在全空间上的动力学性质由此，本文首 先进一步讨论二维符号空间上移位映射的性质，详细地研究了其动力学性质，尤 其是证明了其拓扑熵为+ o 。由此，本文将具有n e u m a n n 令 域和状态集 0 ，1 ) 的二 维细胞自动机作为研究对象。我们将二维细胞自动机与二维符号空间建立联系 定义了2 2 6 = 4 2 9 4 9 6 7 2 9 6 个全局映射随后，我们根据n e u m a n n 邻域的平面结构和 细胞自动机的特点，构造了四个同胚映射亍，r d ，t “和t 口，通过它们实现了所有 全局映射的拓扑共轭分类进一步，我们认为上述分类所得的共轭类数目是最小 的由于本文讨论的全局映射数目较大，用人工地进行分类其所需的计算量相当 之大因此，我们把上述共轭分类进行了程序化设计，从而大大地提高了分类的效 摩 另一方面，本文建立了二维细胞自动机全局映射与初等细胞自动机全局映射 之间的拓扑半共轭关系，从符号动力学角度证明了初等细胞自动机规则1 8 和5 6 拥 有混沌的动力学性状虽然拓扑半共轭的两个紧致系统，其动力学行为可以大相 径庭，但在拓扑半共轭的条件下也同样可以保持系统的某些拓扑不变性，尤其是 扩充的拓扑熵不小于因子的通过拓扑半共轭关系和已知的初等细胞自动机全局 映射的动力学性质，本文粗略地估计了二维细胞自动机全局映射的动力学性质， 特别是拓扑熵的估计同时，文 6 9 】证明了初等细胞自动机规则1 1 0 是具有普适性 的借助上述拓扑半共轭映射，我们获得了2 4 个二维普适细胞自动机规则我们 知道生命游戏用了几条简单的规则，却产生了类似于生命演化过程中无比复杂 7 l 绪论 的现象其中，最著名的是“闪光灯”( b l i n k e r ) 现象和“滑翔机”( g l i d e r ) 现象，前者是 一种细胞群在周期其状态( 性状) 的结构，而后者是一种除了会周期循环其状态( 形 状) 之外，还会稳定地移动的结构这些是c o n w a y i 正明生命游戏具有普适性的关 键现象，也是细胞自动机具有讯号储存与讯号传递功能的重要特征但是，在对本 文得到的普适细胞自动机规则进行数字模拟时，我们发现它们几乎没有滑翔机和 闪光灯现象 本文的结构安排如下：第2 章建立了二维符号空间上定义的8 种移位映射之 间的拓扑共轭关系以及二维符号动力系统与一维符号动力系统之同的拓扑半共 轭关系，并证明了二维移位映射的拓扑熵为+ 借助上述思想与方法，第3 章通 过构造4 种同胚映射实现了二维细胞自动机全局映射的拓扑共轭分类，并把此分 类过程进行了程序化设计第4 章从符号动力学的角度分析了初等细胞自动机规 则1 8 和5 6 的复杂动力学行为，进而通过构造2 个半共轭映射建立了二维细胞自动 机全局映射与初等细胞自动机之间的拓扑半共轭关系通过这2 个半共轭映射，本 章得到了2 4 个二维普适细胞自动机规则，并对这些普适规则进行了数字模拟，最 后章则对全文作一扼要总结和进一步研究作一展望 8 2 二维符号动力学 2 1 一维符号动力学的若干内容 任取k ( k 2 ) 个不同的符号，不妨设为o ，1 ，k 一1 ，记s = o ，l ，k 一1 我们考虑所有z 到s 的映射组成的集合，记为 s z = z = ( z ) iz t s ，iez ) ， 其中z 为全体整数的集合对于每伦= ( 戤) s z ，以记号木表示第0 个符号所在 的位置，即z = ( ，z l ，壹o ，茁l ，) ，戤s ，v i z 在s z 中定义距离为。 出，y ) = 学 三南而k 玑) ( 2 1 ) 显然上述定义是合理的从而，度量空间( s z ，力是紧致的、完全的、完全不连通 的h a u s d o r f f 空间，并称s z 为一维k 符号序列空间，简称一维符号空间设a = ( a a ，一1 ) 是s 上一个长度为p21 的有限序列，简称长度为p 的字设z s z ， i = 瞄，歹】是一个整数区间，则记z 【i 棚= ( 筑，x j ) $ n x t i ，j ) = ( 戤，巧一1 ) ，如 果存在m z ，使得z m ，。却一l 】= a ，则说“有限序n a 出现在x 内”或“z 含有a ”， 记作a z ；否则说“有限序列a 没有出现在z 内”，记作a 必z 对于人胪， 若存在z a ，使得a 0 又设( 仇，t t , ) 矛，记 【叫| = 【a 町】嘲肛i = z s z 2 iz o + m ) u + 住) = a 吣，i i i ，u i ) 叫作s 上二维有限矩阵( ) 睢n ，i 引5 的柱形显然柱形是既开又闭的集合，且全体 柱形构成了s z 2 的一组可数拓扑基，即舻2 的每个开集可以写成柱形的并因此， s z 2 满足第二可数性公设