（基础数学专业论文）若干一维细胞自动机动力学行为的复杂性研究.pdf

若干一维细胞自动机动力学行为的复杂性研究 摘要 j o h ny o nn e u m a n n 在1 9 5 0 年代提出的细胞自动机是一种时间、空间与状态 都离散的数学模型。在型态表现上，每个细胞自动机都是一个离散型的动力系 统。通过设计不同的局部规则，细胞自动机可以展现无限的多样性和复杂性， 产生复杂的动态交互和自我复制现象。即使是规则最简单的基本细胞自动机， 不仅具有丰富的动力学行为，又具有适合超大规模集成电路( v l s i ) 上实现的并 行信息处理结构。细胞自动机自产生以来，就被运用于社会学、经济学、军事 学和科学等不同领域。特别地，它为动力学系统理论中有关秩序、紊动、混 沌、非对称、分形等系统整体行为与复杂现象的研究提供了一个有效的模型工 具。 自从s t e p h e nw o l f r a m 号召对细胞自动机进行简化并提出了基本细胞自动机 以后，众多学者在一维细胞自动机的理论和应用等多个领域作了富有成效的研 究和探索，取得了一系列重要的成果。特别地，2 0 0 2 年w o l f r a m 在大量的计算 机模拟和经验观察的基础上创造性地称基本细胞自动机及其研究方法为一类新 科学。随后，l 0 c h u a 教授等人借助树 蛩( b a s i nt r e ed i a g r a m ) 矛d 细胞自动机特征 函数等重要概念，结合他们的细胞神经网络的研究成果用非线性动力学的思想 对w o l f r a m 的计算机模拟结果给予了一系列数学上的刻画。 细胞自动机研究的困难在于“有关细胞自动机的任何一个非平凡命题都是不 可判定问题”，这已经由计算理论所证明。因此必须对细胞自动机及其动力学 i 摘要 行为分门别类进行研究。本文用符号动力学观点研究几类基本细胞自动机的动 力学行为。首先，第二章在双边符号空间上提出了一种新的拟移位映射和拟子 转移，并讨论了拟移位映射的动力学性质以及拟子转移与传统子转移的关系。 进而，本章刻画了非加性细胞自动机规n i l 的符号动力学性质。即规则1 1 在其 定义的两个子系统上是拓扑强混合的，且具有正拓扑熵。因而，规n i l 在其子 系统上具有l i y o r k e 意义下和d e v a n e y 意义下的混沌。第三章则借助于树图和细 胞自动机特征函数分析了鲁棒周期1 规贝j j l 7 2 、1 6 8 、4 0 以及鲁棒周期一2 规则3 7 的 定性性质，发现它们也展现了非鲁棒b e m o u l l i 移位特征。利用符号动力学的理 论与方法，本章严格证明了这些规则都拥有混沌的子系统。本文的最后一章对 全文作了总结和进一步研究的展望。 关键词：细胞自动机；符号动力学；拟子转移；拓扑强混合；拓扑熵；混沌 t h er e s e a r c ho ft h ec o m p l e x i t yo f d y n a m i c a l b e h a v i o r so fs o m e o n e d i m e n s i o n a lc e l l u l a ra u t o m a _ r 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 ，a r em a t h e m a t i c a lm o d e l si nw h i c ht i m e ，s p a c ea n ds t a t ea r ed i s c r e t e i nt h er e p r e s e n t a t i o no fp a t - t o m s ，c e l l u l a ra u t o m a t aa r ed i s c r e t ed y n a m i c a ls y s t e m s t h r o u g hd i f f e r e n tl o c a lr u 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 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 e c o m p l i c a t e dp h e n o m e n ao fd 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 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 m 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 m ei n t ob e i n g ，t h e yh 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 m i c s ，s t r a t e g i e s ，s c i e n c e ，e 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 ，s u 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 m m e t r y , f r a c t a l i t y , e t c s i n c es t e p h e nw o l f r a mm a d eac a l lf o rt h es i m p l i f i c a t i o no fc e l l u l a ra u t o m a t a a n dp u tf o r w a r de c a ，m a n ys c h o l a r sh a v em a d eaf r u i t f u lr e s e a r c ha n de x p l o r a t i o ni n m a n yf i e l d so fo n e d i m e n s i o n a lc e l l u l a ra u t o m a t a ，s u c ha st h e o r y , a p p l i c a t i o n ，e t c ，a n d g o tas e r i e so fi m p o r t a n tr e s u l t s s p e c i a l l y ，i n2 0 0 2b a s e do na ne x t e n s i v ec o m p u t e r s i m u l a t i o na n de m p i r i c a lo b s e r v a t i o n sw o l f r a mc r e a t i v e l yc a l l e dc e l l u l a ra u t o m a t aa n d a b s ，h i a c t t h e i rr e s e a r c hm e t h o d san e w 尉耐o fs c i e n c e s u b s e q u e n t l y , p r o f e s s o rl o c h u ae t a i p r o v i d e dan o n l i n e a rd y n a m i c sp e r s p e c t i v et ow o l f r a m se m p i r i c a lo b s e r v a t i o n sb y u s i n gs o m ei m p o r t a n tc o n c e p t sl i k eb a s i nt r e ed i a g r a m ，c e l l u l a ra u t o m a t ac h a r a c t e r i s t i c f u n c t i o n s ，e t c b a s e do nt h et h e o r yo fc o m p u t a t i o n ，i th a sb e e np r o v e dt h a tt h er e s e a r c ho fc a i sd i f f i c u l tb e c a u s ea n yn o n t r i v i a lp r o p o s i t i o na b o u tc ai su n d e c i d a b l e h e n c e ，i fo n e f o c u s e so np a r t i c u l a rs u b c l a s s e so fc a ，t h e nt h ed y n a m i c a lb e h a v i o r so fc ab e c o m e t r a c t a b l e t h i sp a p e rs t u d i e st h ed y n a m i c a lb e h a v i o r so fs o m ee l e m e n t a r yc e l l u l a ra u - t o m a t au n d e rt h es t a n d p o i n t so fs y m b o l i cd y n a m i c s 。f i r s t l y ，c h a p t e r2e s t a b l i s h e sa n e wq u a s i s h i f tm a pa n dq u a s i s u b s h i f li nt h eb i i n f u l i t es e q u e n c es p a c e ，a n a l y z e st h e d y n a m i c so fq u a s i s h i f tm a p ，a n dd i s c u s s e st h er e l a t i o n s h i pb e t w e e nt h eq u a s i s u b s h i f l a n dc l a s s i c a ls u b s h i f f f u r t h e r m o r e ，t h i sc h a p t e rc h a r a c t e r i z e st h es y m b o l i cd y n a m i c s o f c e l l u l a ra u t o m a t ar u l e1 1 t h a ti s ，r u l e1 1d e f i n e st w os u b s y s t e m so nw h i c hr u l e1 1i s t o p o l o g i c a l l ym i x i n ga n dp o s s e s s e st h ep o s i t i v et o p o l o g i c a le n t r o p y t h e r e f o r e ，r u l e1 1 i sc h a o t i cb o t hi nt h es e n s eo fl i y o r k ea n dd e v a n e yo ni t ss u b s y s t e m s b ye x p l o i t i n g t h ec o n c e p t so fb a s i nt r e ed i a g r a ma n dc e l l u l a ra u t o m a t ac h a r a c t e r i s t i cf u n c t i o n s ，c h a p - t e r3e x p l o r e st h eq u a l i t a t i v ep r o p e r t i e so fr o b u s tp e r i o d 一1r u l e s1 7 2 ，1 6 8 ，4 0a n dr o b u s t p e r i o d 一2r u l e3 7 w h i c hr e v e a lt h e i rn 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 s t i c s b a s e d o nt h et h e o r ya n dm e t h o d so fs y m b o l i cd y n a m i c s ，t h i sc h a p t e rr i g o r o u s l yp r o v e st h a t a l lt h e s er u l e sp o s s e s sc h a o t i cs u b s y s t e m s f i n a l l y ，c h a p t e r4m a k e sab r i e fs u m m a r y o 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 ra u t o m a t a ；s y m b o l i cd y n a m i c s ；q u a s i - s u b s h i f t ；t o p o l o g i c a l l ym i x i n g ；t o p o l o g i c a le n t r o p y ；c h a o s i v 浙江师范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。本人完全意识到本声明的法律结果由本人 承担。 作者签名： 日期：蛔降j 月；1 日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关机关或机构送交论文的复印件和电子文档，允许论文被查阅和 借阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大 学可以用不同方式在不同媒体上发表、传播论文的全部或部分内容。 保密的学位论文在解密后遵守此协议。 作者签名：际啉 新虢海撇嗍。卜月；f 日 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例。我的学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明并详细列出有关文献的名称、作者、年份、 刊物名称和出版文献的出版机构、出版地和版次等内容口论文中 未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 1 1 细胞自动机的研究背景 1 绪论 细胞自动机( c e l l u l a ra u t o m a t a ，简称c a ) 是一种特殊的有限状态机，是与连 续c a n t o r 映射动力学系统相对应的离散动力学系统，具有时间、空间和状态的 离散性【1 0 1细胞自动机是由j o h ny o nn e u m a n n 在1 9 5 0 年代提出的。1 9 4 8 年，n e u 。 m a n n 在研究“什么逻辑组织结构的自动机具有图灵机一样的自我复制特，| 生1 2 , a 1 ”的 问题时，在s t a n i s l a wu l a m 的建议下，他在具有2 9 个状态的二维细胞空间上建 立了一个具有自我复制特性和普适计算能力的细胞自动机。继n e u m a n n 之后， 经过许多人的改进，最后由a wb u r k s 完成和扩展了n e u m a n n 的研究，物理实 现了具有自我复制特性和普适计算功能的细胞自动机模型。由于n e u m a n n 当 初提出的细胞自动机的结构比较复杂，因而限制了其应用。因此从那时后 关于细胞自动机的研究陷入了一个很长的休眠期。但从2 0 世纪7 0 年代开始， 随着计算机的普及，以c o n w a y 的生命游戏( g a m eo fl i f e ，一种能够进行普适 计算的结构简单的2 个状态8 个邻居的细胞自动机) 为代表，细胞自动机的研究 再度兴起。一方面，细胞自动机的理论研究有了新的进展；另一方面，细 胞自动机的应用研究也得到了较快的发展。细胞自动机的拓扑动力学研究始 于h e d l u n d l 4 1 。1 9 6 9 年，h e d l u n d 从符号动力学角度把一维细胞自动机看作是移 位动力系统的自同态，刻画了所有满的和开的细胞自动机的动力学行为。2 0 世 纪8 0 年代，s t e p h e n w o l f r a m 号召对细胞自动机进行简化，建议细胞自动机应具 有简单规则性、局部连接性及高度并行性，并且提出了状态数为2 邻域半径 为l 的基本细胞自动机( 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 ) n 。简化后的细胞自 动机不仅具有适合v l s i 层次的简单规则结构和信息并行处理的局部互连结构， 而且具有复杂的动力学特性【6 - - 1 3 】。w o l f r a m 对基本细胞自动机的性质进行了深 入的研究，提出了基本细胞自动机的规则及运用条件；并在大量的计算机实验 的基础上，通过观察特定规则产生的行为将基本细胞自动机按行为模式分为如 下四类【1 ，1 4 1 ： i 最终趋于一个空间平稳的状态，这里空间平稳是指每一个细胞处于相同 的状态( 如图1 1 所示) ； 状态最终转移进入简单的周期状态( 如图1 2 所示) ； 具有复杂的动力学行为，状态转移进入混沌状态模式( 如图1 3 所示) ； 状态演化为更加复杂的模式，出现复杂的局部结构，或者说是局部性的 1 绪论 混沌，其中有些会下规则的传播( 如图l4 所示 m mm 图1 1e c a 规剧1 3 6 的时空腐化囤 囤1 2b c a 规刷2 3 2 的时空演化瞳 囤1 3e c a 规刖1 8 的时空演化固囤1 4e c a 规则1 1 0 的时空演化圈 w o f r a r a 对细胞自动机的简化和对基本细胞自动机的深人研究极丈地推动了 细胞自动机理论及应用同时也引起了包括数学家在内众多学者对细胞自动 机的关注，其数学理论也得到了发展。例如，对加性细胞自动机、满的细胞 自动机、等度连续的细胞自动机、正扩张的细胞自动机以及= 甬! 换细胞自动机的 刻画相对比较完整 6 , 1 0 , 1 a , 1 5 , 1 6 , 1 7 1 。然而，由于计算理论已经证明有关细胞自动 机的任何一个非平凡命题都是不可判定的也就是说不存在一个算法，它关于 任何一个细胞自动机的有关性质和结论都能给出“是”与“否”的回答。因此必 须对细胞自动机分门别类进行研究，需要细致刻画具有代表性的一些细胞自动 机规则的动力学性质。如拓扑熵、初值敏感依赖性以及拓扑混合性等等i l s , z 9 】。 w o l f r a m 于2 0 0 2 年在大量的计算机模拟和经验耻察的基础上创造性地称基本细胞 1 绪论 自动机为一类新科学( an e wk i n do fs c i e n c e ) 2 0 1 。随后，著名学者l o c h u a 教授 等人结合他们的细胞神经网络的研究成果用非线性动力学的思想对w o l f r a m 的计 算机模拟结果给予了系列数学上的刻画【2 1 - m ，这也极大地推动了人们进一 步对基本细胞自动机的理论研究。 细胞自动机作为一种动态模型，其应用几乎涉及社会和自然科学的各个领 域。现己被广泛地应用于社会学、生物学、物理学、化学、数学、计算机科 学、军事学等众多领域。细胞自动机与相关理论和方法的发展有着密不可分的 联系，方面，细胞自动机的发展得益于相关理论的研究，如逻辑数学、离散 数学、计算机中的自动机理论，图灵机思想；另一方面，细胞自动机的发展也 促进了一些相关学科和理论( 如人工智能、非线性科学、复杂性科学) 的发展。 1 2 细胞自动机和符号动力系统 细胞自动机的时间、空间以及状态均是离散的，因此它是布尔( b o o l e a n ) 化 的。既然细胞自动机是一种布尔化的离散动力学系统，那么自然可以用符号动 力系统作为研究工具来考虑细胞自动机的动力学行为及复杂性。下面先扼要的 介绍有关符号动力系统和细胞自动机的基本概念。 令s = 0 ，1 ，2 ，：佗一1 ) ，其中礼2 ，然后以s 为状态空间作拓扑积。= s z = z = ( ，z 一1 ，未o ，z l ，) iz i s ，z 。特别地，当n = 2 时记s z = o ，1 z 全2 。s z 上的距离定义如下：对任意的z ， y c s z ， 讹= 。曼击 其中s 上的距离也( ，) ，耽z 定义如下 也( 兢，互t ) 再面瓦可 d i ( x i , 牙i ，= r 嚣豢 n 2 ， 显然，( s z ，d ) 是紧致的、完备的、完全不连通的度量空间，s z 是一个 c a n t o r 集1 2 7 , 2 s 。设a = ( a o 一1 ) 是s 上一个长度为p 1 的有限序列，简称矿序 列。设z s z ，如果存在m z ，使得z m + k = a 七，k = 0 ，1 ，p 一1 ，则 说“有限序列a 出现在z 内”或“z 含有a ”，记作a o 使得( 吒l y ) ”( 【，) nv o ，v n n 。因 为吼k 拓扑强混合，所以对非空开集u ，ycy ，存在n o 使得( 吼l y ) n ( u ) n v 仍，v n n 7 。又因为亍是同胚，故- ( 矿) 也是y 的非空开子集。那么根 据吼l y 是拓扑强混合的就有，对开集亍( v ) ，存在” o 使得( 妒l l y ) 乱( u ) n t ( v ) 仍，v n n ”，则有亍一1 ( ( 妒l l y ) n ( 矿) n 亍( v ) ) 仍，v n n ”。 r n = m a x n 7 ，n “) ，那么v n 有 ( i ) 如果7 7 = 2 k ，k z + ，那么 ( 盯l i y ) ”( u ) ny = 铲8 ( ( 盯l l y ) 2 k ( ) ) nv = ( 铲8 。( 气i y ) 2 ) ( u ) ny = ( to 盯。i yo 。to 口li y ) ( 【厂) nv 、- 。、，。一 n = 2 k = ( t 0c r l l y ) “( u ) nv = ( 妒l y ) 住( 汐) n v 0 ； ( i i ) 如果讫= 2 k + 17k z + ，那么 ( o l i y ) “( u ) nv = 亍一1o 亍( ( 盯工i y ) n ( u ) ny ) = 一t - 1 ( ( 萝o ( 盯l l y ) ”) ( 汐) n t ( v ) ) l o 2 一类非加性细胞自动机的动力学行为 = 一t 1 ( ( 妒l l y ) n ( u ) n 亍( y ) ) 0 。 因此，对任何非空开集以vcy ，存在n = m a x ，n “) 0 ，使得 ( 吒i y ) n ( u ) nv 仍，v n n ，即仃l i y 拓扑强混合。 ( 必要性) 假设吒i y 拓扑强混合，要证明妒l l y = 一t o a 。i y 拓扑强混合，则需要 证明对任何非空开集阢vcy ，存在n o 使得( 吼i y ) ”( u ) nv 仍，v n n 。 由吒i y 拓扑强混合知，对非空开集 ，vcy ，存在m 0 使得( 吼j y ) n ( u ) n v ( ) ，v n 1 。又因为亍是同胚，所以于( r ，) 仍是) ，的非空开子集，于是对开 集亍( u ) ：v ，存在2 o 使得( 吒i y ) ”( 亍( u ) ) f lv _ - ( ) ，v n 2 。 取n = m a x n 1 ，2 ) ，则v n n 有 ( i ) 女口果钆= 2 k ，k z + ，男b 么( 妒二l y ) n ( u ) nv = ( 亍。盯l l y ) n ( u ) nv = ( 吒l y ) n ( u ) nv 仍； ( i i ) 如果凡= 2 k + 1 ，k z + ，那么( 妒工l y ) n ( u ) nv = ( t0 仃l i y ) n ( u ) nv = 亍o ( o r l i y ) n ( u ) nv = ( 仃l l y ) ”( 亍( u ) ) nv 仍。 因此，对任何非空开集以vcy ，存在n = m a x n 1 ，n 2 ) 0 ，使得 ( 吮i y ) n ( u ) nv 仍，v n n ，即垆厶i y = 一to 吒l y 拓扑强混合。 ( d ) 由( a ) 可得 ( l i y ) 2 = ( 亍。口l i y ) 2 = ( 亍) 2o ( 仃l l y ) 2 = ( 口l l y ) 2 。 因此，e n t ( 妒l i y ) = e n t ( a l l y ) 。证毕。 2 2 规则1 1 的动力学行为 本节将详细刻画b e r n o u l l i 盯，移位规贝j j l l 的动力学行为，类似地，可以刻画 与规则l l 具有相同参数的规则的动力学行为。子系统在动力系统研究中扮演着 重要角色，一个系统的子系统可以在某种程度上反映该系统的动力学特性。因 此，下面我们从符号动力学角度通过刻画规则1 1 的两个子系统来讨论该规则的 动力学特性。 2 2 1 规则1 l 的两个子系统 在双边符号空目j 2 中，根据b e m 。u l l i 仃，一移位规则1 1 的两组参数( p = 一去 盯= 一l ，7 = 1 和p = 2 ，矿= 1 ，7 - = 1 ) 分别可以确定两个子集合，记为天1 1 ( 1 ) 和 a 1 l ( 2 ) 。即 天1 1 ( 1 ) = z 2 i ( ，( z ) t = * t i - - 1 , v i z ) 2 一类非加性细胞自动机的动力学行为 和 a 1 1 ( 2 ) = 【a e 2 i 【 ，( 。) t = x i + l ，v i z 。 而b e r n o u l l i0 ，- - 移位规贝 j l l 的输入一输出布尔函数真值表以及布尔函数分别为 表2 1b e r n o u l l i “移位规则1 1 的输入一输出布尔函数真值表 x i lz iz i + 1【厂，( o ) l i o0ol 00ll olo0 ulll l0o0 l010 1 l 0 0 lll0 【 l ( z ) t = 窑t l z t + lo 觑一l 牙i 2 i + 1 ，vze 2 ，i z 。( 2 2 ) 由式( 2 2 ) ，下面从符号动力学角度严格刻画子集合a l l 和人1 1 ( 2 ) ，并通过这 两个子集合找至l j b e m o u l l i 7 r 移位规则1 1 的两个子系统。 命题4 对任意的z e 2 ，i 么，z a n ( 1 ) 当且仅当下述两个事实同时成 立： ( a ) 如果z = 1 ，那么z t l = 0 ，z t + 1 = 1 ；或者蔬一1 = 1 ，z l + 1 = 0 ；或 者z 一l = 1 ，z t + 1 = 1 ； ( b ) 女口果z t = 0 ，习b 么z 一1 = 0 ，z + 1 = 0 ；或者z t l = 0 ，z t + 1 = l ；或 者z i 一1 = l ，z t + 1 = 0 ；或者z 一l21 ，z t + l = 1 。 证明： ( 必要性) 假设z a i i ( 1 ) ，现在证明( a ) 和( b ) 是成立的。由zea l 易 知 ，( z ) 】t = 磊一1 = x i lol ，v i z 。则v i z ，由式( 2 2 ) 可得如果x i = 1 ， 那么lo 鼢一l = ( 1o x i 1 ) z 冲1 ，即( 1ox i 1 ) ( 1ox i + 1 ) = 0 。所以就有x i l = 0 ，z t + 1 = 1 ；粤窀者z t 一1 = 1 ，z i + 120 ；茑e 者z 一l = 1 ，z i + 1 = 1 。 同理可证，( b ) 也是成立的。 ( 充分性) 假设( a ) 和( b ) 均成立，证明z a n ( i ) ，即证明 厂1 ，( z ) k = 锄一l = 筑一1el ，v j z 。凶为对任意的i z ，觑的取值只有两种可能，即= l 或 者勋= 0 ，凶此下面分两种情况证明。 ( i ) 如果戤= 0 ，那么根据( b ) 就有z t 一1 = 0 ，o t + l = 0 ；或者翰一l = 0 ，2 7 t + l i 1 ；或者魏一l = 1 ，z 件1 = 0 ；或者一1 = 1 ，z t + 1 = l 。现在把甄= o 代入 式( 2 2 ) 便得到 【厶l ( z ) t = ( 1o z t 一1 ) z l + 1e ( 1o z 一1 ) ( 1o z t + 1 ) 。 ( 2 3 ) 1 2 2 一类非加性细胞自动机的动力学行为 再把勋一l ，x i + l 的四组取值分别代入式( 2 3 ) 便有 f l ，( z ) 】 = 磊一1 = 勋一1o l 。 ( i i ) 如果翰= 1 ，那么根据( a ) 就有鼢一1 = 0 ，x i 4 - 1 = 1 ；或者z t l = 1 ，z 件l = o ：或者x t l = 1 ，z 件1 = l 。在把= 1 代入式( 2 2 ) 便得到 ，( z ) 】l = ( 1o x i - - 1 ) z + 1 。 ( 2 4 ) 类似地再把毛一l ，z 件1 的三组取值分别代入式( 2 4 ) l 莆j 样能得到【 ，( z ) 】i = 磊一1 = 兢一1o l 。 综上所述，【 。( z ) k = 5 ： - 1 = z t 1ol ，即z a 1 1 ( 1 ) 。证毕。 显然，天1 l ( 1 ) 是2 的一个闭子集，但不是对厶：强不变的。但从命题4 可以得 到一个对厶，强不变的闭子集，记作人1 1 ( 1 ) 。 命题5 对任意的z 2 ，i z ，z a 1 1 ( 1 ) ca l l ( 1 ) 当且仅当下述两个事 实同时成立： ( a ) 如果i = l ，那么z l 一1 = 0 ，z 件1 = l ；或者一l = 1 ，z t + 1 = o ；或 者z t 一121 ，z i + 15l ； ( b ) 如果= 0 ，那么o 一l = 0 ，z t + 1 = 0 ；或者兢一1 = 0 ，z 件1 = 1 ；或 者z f 一1 = 1 ，2 f + 1 = 0 。 证明与命题4 类似，略。 命题6 人1 1 ( 1 ) = z 2 l a z ! v a _ ( ( 0 1 0 ) ，( 1 0 1 ) ) ) ，并且( 人1 1 ( 1 ) ， ，i ，( 1 ) ) 是( z 2 ， 。) 的子系统。 证明： 根据命题5 即可得a 1 1 ( i ) = z 2 1 月z ，v a ( 0 1 0 ) ：( 1 0 1 ) ，) 。显 然，五，( a 1 1 ( 1 ) ) = a n ( u 。又因为2 一a 1 1 ( 1 ) = z 2 i 存在a ( 0 1 0 ) ，( 1 0 1 ) 使 得a _ z ) = 。 0 1 0 】u 。【1 0 1 ，而可数个柱集的并是一个开集，所以人l l ( 1 ) 是一 个2 的闭子集。因此，( , 4 - 1 1 ( i ) ，l 。i ，。( 1 ) ) 是( 2 ，厶- ) 的子系统。证毕。 命题7 对任意的e 2 ，z z ，z a 1 1 ( 2 l 当且仅当下述两个事实同时成 立； ( a ) 如果翰= 1 ，那么z 一1 = 0 ，+ 1 = o ；或者毛一l = 0 ，z 件1 = 1 ：或 者z l 一1 = 1 ，z + 1 = o ： ( b ) 如果。 = 0 ，男b 么z i l = 0 ，z t + l = l ；或者z 一l = 1 ，z + 1 = 0 。 证明与命题4 类似，略。 命题8 ( a l l ( 2 ) ， 。l 1 1 ) 是( 2 ，f l ，) 的子系统。 证明与命题6 类似，略。 虽然命题5 和命题7 是在双边符号空间2 中刻画了b e r n o u l l i 靠移位规1 ) i j 1 1 的 1 3 2 一类非加性细胞自动机的动力学行为 两个子系统，然而在有限长度的符号序列空间中这两个命题仍然可以作为刻画 该规则的两个具有b e r n o u l l i 移位特征的子系统的准则。为了形象地说明b e r n o u l l i 即移位规则1 1 的b e m o u u i 移位特征，首先任意取两个分别满足命题5 和命题7 的且同时满足周期边界条件的有限序列作为初始条件，图2 1 和图22 则分别 是b e r n o u l l id ，一移位规则1 1 在这两个选定的初始条件下的时空演化图。注意，用 于模拟的初始条件只能是有限长度的符号序列。 图22b e r n o u l l i f i e - 耪位规则儿的时空渍化囤二 2 2 2f ，的动力学行为 1 ( 1 ) 是对 ，强不变的闭子集，因此 t 儿。是一个右拟子转移。那么， 就可叭利片j 右子转移和右拟子转移之间的关系，通过右子转移i u “) 刻 画 t 在a 1 1 ( 1 ) 上的复杂的动力学行为- 首先，证明l 。是一个有限型子转 移；然后t 建立 k 。和k 。之间的关系；最后，借助一个与k 拓 1 4 2 一类非加性细胞自动机的动力学行为 扑共轭的2 阶有限型子转移证明了 ，i 1 1 , 1 , 是拓扑强混合的，并准确计算出 t f , 。i 的拓扑熵。 11,1, 设是s 上有限序列的一个集合，令人= z 铲i a z ，v a 】。 引理i 2 8 对任意s 上有限序列的集合，人都是一个s z 的对仃l 强不变的 闭子集。 引理l 说明，给定s 上一个有限序列的集合，就决定了一个子转移 吒i ：a 一人， 叫作人或子转移口l l 一的排除系统。 引理2 2 8 设a 是一个s z 的对盯，强不变的闭子集，则存在s 上有限序列的集 合，使a = 人。 由引理2 知，任何一个子转移都可以由其排除系统来决定。不过，子转移的 排除系统却不是唯一的。 定义6 1 2 8 设人是一个s z 的对盯，强不变的闭子集，如果a 有一个有限的 排除系统，则称人或盯：i ：a a 是有限型的。并称这个排除系统所含有 限序列的最大长度为其阶数。所有排除系统阶数的下确界，称为人或子转 移仃，i a ：人一a 的阶数