（基础数学专业论文）可数群上元胞自动机的一些动力性质.pdf

河北师范大学硕士学位论文 可数群上元胞自动机的一些动力性质 中文摘要 本文研究了可数群上元胞自动机的一些动力性质， 主要结论如下，( 1 ) 拓扑传递的元胞自动机或是敏感依赖 的，或是一单个周期轨；( 2 ) 借用吸引子的拓扑形式给出 了元胞自动机的分类；( 3 ) 有限剩余群上元胞自动机的最 终周期点集合稠密；( 4 ) 对来自物理模型的一类元胞自动 机证明了它与可数群上一元胞自动机是拓扑共轭的，借 此将上述三个结果进一步推进到了这类系统 关键词。可数群，元胞自动机，拓扑传递性，敏感 依赖性，吸引子，拟吸引予 河北师范大学硕士学位论文 s o m ed y n a m i c a lp r o p e r t i e so fac e l l u l a ra u t o m a t ao na c o u n t a b l eg r o u p a b s t r a c t i nt h i sp a p e r ，w es t u d ys o m ed y n a 删p r o p e r t i e so fa c e h u l a ra u t o m a t ao nac o u n t a b l eg r o u p t h em a i nr e s u l t sa r e 勰 f o l l o w s ：( 1 ) i fa c e l l u l a ra u t o m a t ao nac o u n t a b l eg r o u pi st r a n s i - t i v e ，t h e ni ti se i t h e rs e n s i t i v e0 1 c o n s i s to fas i n g l ep e r i o d i co r b i t ；( 2 ) b yu s i n go ft h ef o r m so fa t t r a c t o r ，w eg i v et h ec l a s s i f i c a t i o n o ft h ec e l l u l a ra u t o m a t ao nac o u n t a b l eg r o u p ；( 3 ) t h es e to f e v e n t u a l l yp e r i o d i cp o i n t so fa c e h u l a ra u t o m a t ao nac o u n t a b l e r 档i d u a l l yf i n i t eg r o u pi sd e n s e ；( 4 ) f o ran e wk i n do fc e n u l a r a u t o m a t aw h i c hc o m e 8f i o mp h y s i c a lm o d e l ，w ep r o v et h a ti tc o n - j u g a t e st oa c e l l u l a ra u t o m a t ao nac o u n t a b l eg r o u p ，a n dt h e n t h et h r e er e s u l t sm e n t i o n e da b o v eh o l di nt h i su e wk i n do fc e l l u l a r a u t o m a t a k e yw o r d s ：c o u n t a b l eg r o u p ，c e l l u l a ra u t o m a t a ，t o p o - l o g i c a lt r a n s i t i v i t y ，s e n s i t i v i t y ，a t t r a c t o r ，q u a s i - a t t r a c t o r 学位论文原创性声明 本人所提交的学位论文可数群上元胞自动机的一些动力性质， 是在导师的指导下，独立进行研究工作所取得的原创性成果。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均 已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：壶旃茨 硼年莎月侈日 学位论文原创性确认书 学生孟祥英所提交的学位论文可数群上元胞自动机的一些动力 性质，是在本人的指导下，由其独立进行研究工作所取得的原创性 成果。除文中已经注明引用的内容外，该论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。 指导教师( 签名) ： 。呐每奸l 归 河北师范大学硕士学位论文 1 引言 元胞自动机( c e l l u l a r a u t o m a t a ，简称c a ，也有人译为细胞自动 机，点格自动机，分子自动机或单元自动机) 是由数学家j o n hv o l l n e u m a n 和s t a n i s l a w u l a m 在2 0 世纪4 0 年代引入的( 【1 】) 后来，它被 用作自复制和万能计算的模型一个众所周知的元胞自动机的例子 是生命游戏( g a m eo f l i f e ) 元胞自动机的深刻的数学理论则是由 h e d l u n d 发展起来的( 【2 】) 经过6 0 多年的发展。现在元胞自动机已被 广泛地应用到自然科学，社会科学和工程技术的各个领域例如 在计算机科学中，元胞自动机可被看作是并行计算机而用于并行计 算的研究，同时也被用于计算机图形学的研究；在化学中，元胞自 动机可用来通过模拟微观粒子在化学反应中的相互作用研究化学反 应的过程等特别地，作为动力系统，元胞自动机具有丰富和多样的 动力性质，且因此，它为动力系统理论中有关秩序、混沌、非对称、 分形等系统的整体行为和复杂现象提供了一个有效的模型工具 元胞自动机是一时间和空间都离散的动力系统散布在规则格 网( l a t t i c eg r i d ) 中的每一元胞( c e n ) 取有限的离散状态，遵循同样 的作用规则，依据确定的局部规则作同步更新大量元胞通过简单 的相互作用而构成动态系统的演化不同于一般的动力学模型，元 胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模 型构造的规则构成凡是满足这些规则的模型都可以算作是元胞自 动机模型因此，元胞自动机是一类模型的总称，或者说是一个方 法框架其特点是时间，空间、状态都离散，每个变量只取有限多个 状态。且其状态改变的规则在时间和空间上都是局部的从动力系 】 河北师范大学硕士学位论文 统理论来说，元胞自动机是定义在一个具有离散，有限状态的元胞 组成的元胞空间上，并按照一定局部规则，在离散的时问上演化的 动力系统用数学的语言来说可以这样描述t 设a 是有限集合( 它 通常表示的是元胞可取的状态集合) ，z 4 是d 维整数集合，n 表示时 间，那么整个元胞空间则是在d 维空间一整数集合z d 上的分布，记 为a 掣元胞自动机的动态演化是在时同上状态组合的变化，它可 记为 f ：矿_ 这个动态演化又是由各个元胞的局部演化规则，所决定的通 常这个局部演化规则，又称为局部函数设r 表示元胞的邻域半径， 元胞及其邻域可以表示为矿“，则局部函数可记为： ，：p + 1 - + a 粗略地诡元胞自动机是按照事先指定的规则排列的一族元胞。 而每个元胞都取有限状态中的一个状态这些元胞的状态将随时间 的变化而变化，并且它在第n + 1 时刻的状态是由其在第n 时刻的状 态和它的半径为r 的邻域中的元胞在第n 时刻的状态所决定 有关元胞自动机的拓扑动力学性质的研究成果很多，其中论文 【1 】和【2 】将2 0 0 0 年前的主要研究成果给出了一个综述在【1 】1 中作者对 一维元胞自动机的满性，周期性、拓扑传递性等度连续性，吸引子 和链传递等动力性质给出了详细说明近年来，随着元胞自动机研 究的发展，并基于理论和应用的嚣要，人们将元胞的生存环境抽象 成群后对群上的元胞自动机赋予了关注倒如，文献 4 】给出了可数 群上的元胞自动机的定义，并证明了可数的a m e n a b l e 群上的元胞自 动机是满射的充分必要条件为它是前单射的本文试图对可数群上 2 河北师范大学硕士学位论文 的元胞自动机的一些动力性质进行讨论在2 中，我们给出了与本 文相关的一些定义在3 中我们用吸引子的类型给出了可数群上元 胞自动机的一个分类在4 中，我们讨论了元胞自动机的拓扑传递 性，敏感依赖性和周期点性态在这两节中所获得的全部结果可视为 是文【1 】1 对应结论的推广在5 中，我们对来自物理学模型的一类元 胞自动机( 【3 】) 论证了它与一可数群上的元胞自动机是拓扑共轭的 据此可将在3 和4 中所获得的结论全部推进到这类新的元胞自动机 2 有关定义 设g 是一个可数群( 在本文中恒设群g 的元素个数是无限的) ，a 表示一有限集合( 通常称a 为状态集) 记= 扛：g _ + a 是一映 射 现对任意g g ，定义映射 蚕：a g - + z 一雪( ) 垒扩， 其中映射护：g - + a 定义为。 护( ，) = z 0 矿) ，v 矿g ， 我们把映射垂称为是由g 所诱导的a g 上的左平移作用 设肘是g 的有限子集，记a f = 兀g 矗f 山( 这里a g = a ) 定义2 1 若映射f ：俨_ + 满足如下条件存在有限子集 mcg 及映射，：a - + a ，使得对任意z 俨及任意g g 有 f ( z ) ( 9 ) = ，( 矽i m ) ( 其中护i j i f 表示映射护：g - + a 在m 上的限制) 那 么我们就称f 是俨上的元胞自动机，并称其中的m 为，的作用域， 且映射，为f 的局部函数 3 河北师范大学硕士学位论文 注记2 1 由定义可见，对任意g g ，有f o 垂= 雪o f 设状态集a 具有离散拓扑，且a g 有乘积拓扑易知a g 为紧致 的乃空同，并且是可度量化的根据a g 的乘积拓扑及f 的定义，可 以验证f ：a o - + a g 为连续映射 由于g 是可数的，故存在从自然数集到g 的1 1 到上的 对应设盯：n - + g 是这样的一个对应，并且对任意n n ，记 如= 盯于是g 可记为g = 跏，肌，g n ， 现在a g 上定义度 量d ：a a a g _ + 【o ，1 1 为： d 掣) = 去，毛可， 其中k 满足x ( g k ) 玑鲰) ，且z 慨) = l ，慨) ，0 s 七一1 不难验证， 1 由度量d 诱导的拓扑与俨的乘积拓扑相一致 2 若以：n _ + c ( i = 1 ，2 ) 是1 1 到上的对应，函是由以决定的 如上所述的a g 上的度量，刚前与磁是a g 上的等价度量 据以上分析，为了行文方便，在下文中恒设从到g 的1 1 到 上的对应仃：n 寸g 是确定不变的，并记g = 卯，g z ，鲰， 定义2 2 设y 是a g 的子集。若对任意g g 有= y ，则称y 是g - - 不变的 定义2 3 设g 是一个群如果对每个不是单位元的g g ，存在 有限群e 和同态h ：g 一+ e ，使得| 1 1 0 ) 不为e 的单位元，则称g 为有 限剩余群 易验证，对任意自然效m ，z ”均为有限剩余群 定义2 4 设x 是拓扑空间，f ：x - + x 是连续映射若对任意非 空开集以v c x ，存在，l 0 ，使得p ( u ) n 矿口，则称f 是拓扑传递 的 4 河北师范大学硕士学位论文 众所周知。整数加群z 的元素1 所诱导的a z 上的左平移作用 ( 或说符号动力系统) 是拓扑传递的 定义2 5 设x 为度量空问，d 为x 上的度量。f ：x - 9x 是 连续映射若存在g 0 ，使得对任意茁x 及任意6 0 ，存在 f 岛扛) = i v x i d ( 茁，咖 o p ( y ) ，则 称y 是f 的吸引子。并称y 是吸引子y 的一个吸引域i 若闭子集 y x 可表示为f 的可数个吸引子的交，且y 又不是吸引子，则称 l ，是f 的拟吸引子；若y 是f 的一个( 拟) 吸引子，并且y 的任意 闭子集都不是f 的( 拟) 吸引子，则称y 是f 的极小( 拟) 吸引子； 若z x 是f 的一周期点，且f 过z 的轨道是f 的一吸引子，则称 z 为f 的吸引周期点 3 元胞自动机的吸引子类型 自元胞自动机产生以来，对于元胞自动机的分类研究一直是元 胞自动机的一个重要的研究课题和核心理论基于不同的出发点， 对元胞自动机可有多种分类，其中最具影响力的当属s w o l f r a m 在 舳年代做的基于动力学行为的元胞自动机分类，他将一维元胞自动 机归纳为平稳型，周期型，混沌型和复杂型四大类其中前三类分 别对应于不动点吸引子，周期轨吸引子和混沌吸引子在【1 】中作者 利用元胞自动机的吸引子类型将其分成三类本节的主要目的是将 【1 】1 中的结果推进到可数群上的元胞自动机上 定理a 设a 为状态集合，g 是可数群。f ：a g a g 是一元胞自 5 河北师范大学硕士学位论文 动机，则f 有下列形式之一 1 存在两个互不相交的吸引子，且因此它的全体拟吸引子所 构成的集合的基数是r 2 存在唯一极小吸引子y 。它是g 一不变的( 即对任意g g 有 雪( y ) = y ) ，且y 含于任意其它吸引子之中 3 存在唯一极小拟吸引子，且它含于任意其它吸引子之中 定理a 的证明将通过如下两个弓i 理予以实现 引理3 1 设x 是紧致拓扑空问，f ：x o x 是连续映射，y x 是f 的一个吸引子，则存在l ，的一个吸引域y ，使得矿是由拓扑基 中有限个成员的并所构成 证明t 由定义，存在l ，的邻域u ，使得f ( - ) u ，r y = n 痧o p ( 功 若f ( _ ) = 矿，则u 是既开且闭的，由此可知，结论成立若f c u ) 是u 的真子集，由于f ( _ ) 是x 的紧致子集，故可在x 的拓扑基中 选取有限个成员k ，m ，使得ycf ( _ ) cv 皇u ：lkcu ，从而 f ( _ ) c f 而c v ，且y = n o p ( y ) b 推论3 1 在定理a 的条件下有，f 的互不相同的吸引子个数至 多为可数个 证明，由于在俨中。形如 姥。j = 矗a a ：z ( ) = ，现g ，a 歹= 1 ，l ( 称为a g 中的一个柱集) 的集合构成a g 的拓扑基。因此俨具有 可数基，于是据引理3 1 知，推论成立n 引理3 2 设a 是状态集，g 是可数群，f ：a g - + a g 为一元胞自 动机若f 有两个互不相交的吸引子，则每个吸引子中含有两个互 不相交的吸引子，进而得到f 的全体拟吸引子所构成的集合的基数 6 河北师范大学硕士学位论文 为n 证明，据引理3 1 。可设巩“= 1 ，2 ) a a 是k 的一个吸引域，且 酝是由有限个柱集的并所构成，因而可设 阢= 噬：恚：溉= 伽e a aiz ) 如，如ca ，= i 川2 ，k d ( i = 1 ，2 ) 往证仉n 阮= 够利用反证法若矾n 砚毋，由于 f 吼n ) f ( 玩n - 2 ) f ( - 1 ) n f ( _ 2 ) s 巩n 巩， 从而 y = np 帆n 阮) ( np ) ) n ( np ( 巩) ) = m n k 毋， n on on 抄 矛盾于是仉n 巩= o 现对f 的任意一个吸弓f 子z ，要证。z 中含有 f 的两个互不相交的吸引子事实上，设u 是z 的一个吸引域，并 且据引理3 1 ，可设，是由有限个柱集的并所构成，因而可设 ，= 唆教。；c ：l = p ix ( ) 如，a 町c a ，j = l ，1 ) 取g e 使得 g 聋 鲴。程im = 1 ，l ，歹= 1 ，i = 1 ，2 ， 我们说由geg 所诱导的a g 上的左平移作用雪：a g _ + a g 将导致 n v 0 0 = l ，2 ) 事实上，只须证明阢中存在元素甄，使得雪瓴) 姒n ，选取a s ( m = 1 ，z ) ，叼如u = 1 ，i = l ，2 ) 和 a ，由于鲴岳( i i = 1 ，2 ，毛，i = 1 ，2 ，从而我们可以构造盈， 满足x i ( g g s r a ) = 口s 。，戤( 奶) = 叼，j 三1 ，k 且对任意 盈g ，m = 1 ，n u 靳，歹= 1 ，墨，i = 1 ，2 ， 7 河北师范大学硕士学位论文 毛) = n ( i = 1 ，2 ) 易见黾阢o = 1 ，2 ) ，且雪亿) ( 炳。) = x i ( g g s , n ) = 幻。a 矗m ( m = 1 ，l ， = 1 ，2 ) ，从而雪( 戤) u ，所以0 u n u 织i = 1 ，2 由于f o 雪= 雪o f ，且f ( 阢) 冬矾o = 1 ，2 ) ，f ( u ) cu ，因而有 f o 雪( 阢) = 雪o f ( 阢) 垂巩 f o 蚕( u ) = 雪o f ( u ) 雪u ( 注意到雪：a g - + a g 为同胚映射，故鸯阢与雪u 都是的开集) 令 k = 参阢nc 厂o = 1 ，2 ) ，则k 为的开集，且由巩n 巩= 毋及雪为同胚 知 k n k = 口 f 陬) c f 。雪霞) n f ( _ ) = 争。f 陬) n f 回姒n u = k 令k = n 忭 o p ( k ) g = 1 ，2 ) 若磁织则它是f 的闭不变集，因而k 是f 的吸引子，且k c z o = 1 ，2 ) 下证k 谚由于a g 为紧致度量 空同，从而据有限交性质知，闭集族 p ( 玩) ，n = 0 ，1 ，2 ，) 讧1 ，2 有非 空的交，即，n n o p ( 玩) 毋，从而k 瓯i = l ，2 最后证t 由f 的全体拟吸引子所构成的集合的基数为n 设y o = n ，i o p ( a g ) ，那么k 是f 的一吸引子另外由条件知，设 与k 1 是f 的两个互不相交的吸引子，则y o o 与k l 必为k 的真子集， 即y o ，k l y o ；进而在与碥l 中分别存在两个吸引子y o e o ，l s 碥及y o t o ，y o n k l y o 归纳地有，若，i l ，妃“0 与 ，n ，$ n - 1 ，1 国= 0 或1 ，j = 0 ，1 ，f i 一1 ) 是，1 ，k 一1 中两个 互不相交的吸引子，进而在k o ， l ，“一l ，l = o 或1 ) 中又有两个互 不相交的吸引子现对s = ，i l ，k ，) ( 白= o 或1 ，j = 0 ，1 ，) 令 y s = 帷o k o ，i l ，如，易见b 是f 的闭不变集往证蚝不是f 的吸 引子事实上，若不然，设巩是b 的一个吸引域，则有f ( _ 8 ) c 玩，且 n ：苫p ( ) = 然而，由于，i 。，“c ，i 。，“一。( v n 1 ) ， 8 河北师范大学硕士学位论文 故当n 充分大时，有，i 1 ，kc 这表明将是，i l ，k 的一吸引域因而有，i 1 ，k = n 。o p ( 玩) = y s 但蚝含于 ，i 1 ，k 的真子集，i 。，i 。，讧。中，故产生矛盾矛盾说明k 是f 的一个拟吸引子 现将区间【o ，1 ) 上的实数用二进制表示对于任意o 【o ，1 ) ，令 n = 0 i o i l k ，于是令盯( a ) = y s = 帷o y i o i l k 易见盯是从1 0 ，1 ) 到f 的拟吸引子所形成的集合上的1 1 到上的对应由此得到f 的全体拟吸引子所构成的集合的基数为杖n 引理3 3 设a 为状态集合，g 是一可数群，f ：a o + 是一个 元胞自动机若f 有一极小吸引子y 则对于f 的任意一个吸引子 互有y z ，并且对任意g g ，有参( y ) = y 证明t 首先指出y n z 毋，因为若y n z = o ，则由引理3 2 知。y 内将包含两个互不相交的吸引子，这与y 的极小性相矛盾，因此 y n z o 往证ty z 设和阮分别为y 和z 的一个吸引域，于是 有巩n 沈= 以满足tf ( _ ) f ( 巩) n f ( 巩) 巩n 睨= u 因此 n d o f “( y n z 是一吸引子，由y 的极小性可知y z 设u 是y 的一个吸引域，因而有f ( _ ) 阢且y = n 庐o p ( u ) 对任意g g ，由于雪：叶a g 为同胚，且fo 雪= 雪of ，故有 f o 雪- 1 ( _ ) = 扩1o f ( 两多一1 ( 因而有雪- 1 ( y ) = n 心。f ” 一1 u ) 是f 的一个吸引子由上面的证明可知y 雪y ，即y ，同理可证 l ，s ，从而有霸y = y d 定理a 的证明t 若f 不存在互不相交的两个吸引子，则对f 的 任意两个吸引子y 和z ，就必然有y n z 口由于f 的吸引子个数 至多为可数个，且两个非空的吸引子的交仍非空。故若f 有极小吸 9 河北师范大学硕士学位论文 引子，那么由引理3 3 知，该吸引子必为唯一。并且是g 一不变的。 同时它还要含于f 的任意吸引子之中进而，若f 不存在极小吸弓l 子，则f 含有极小拟吸引子，并且这个拟吸引子是唯一的，同时也 要含于f 的任意吸引子之中 口 4 周期性和敏感依籁性 周期性和敏感依赖性分剔刻画的是系统运动的规律性和不可预 测性就科学研究和工程技术的应用来说，人们总希望事物的发展 变化规律具有周期性的动力特征，以此来实现对系统发展变化规律 的认识，进而实现对系统的有效控制，因此，长期以来寻找系统的 周期性运动就成为人们所期望的主要目标之一然而，近3 0 年来的 研究发现，大量的事物运动完全可以是毫无任何规律的复杂运动， 其运动的未来状态是完全不可预测的，用数学语言来描述就是( 对 初值) 敏感依赖本节将对元胞自动机讨论它的周期性及( 对初值 的) 敏感依赖性具体说来。我们试图证明如下两个定理- 定理b 设a 为状态集，g 是一可数群，f ：- 俨是元胞自动 机，l ，俨是f 的闭不变子集，若f 在y 上的限制f i y 是拓扑传递 的，则fi y 或是敏感依赖的，或y 是由f 的一周期轨组成的 定理c 设a 是状态集。g 是一有限剩余的可数群，f ：a g + a g 是元胞自动机，则f 的最终周期点的集合在a g 中稠密 引理4 1 ( 【5 】) 设x 是紧致度量空问，f ：x - + x 是连续映射，若 f 为拓扑传递的，则f 或者是敏感依赖的，或者是几乎等度连续的 定理b 的证明：若f i y 不是敏感依赖的。则由引理4 1 知，f i ， 是几乎等度连续的又因为每个传递的几乎等度连续系统为一致刚 性的q 6 ) ，所以fi l ，是一致刚性的，即存在数列 嘞 ，使得对任意 1 0 河北师范大学硕士学位论文 善y ，有d ( 一( z ) ，$ ) 叶0o - 9 ) 于是，对任意z y ，存在唧。使 得d ( 胛0 ) ，功 n 0 ，使得p ( 暑，) = p ( y ) ，即! ，为f 的最终周期点 最后要证f ( a a 日) n 魄恐 g 诹i k 西 由于p ：一a g ，日在q = 钕。，鳓，鲰，上的限树p k 为单射。 】2 河北师范大学硕士学位论文 所以 】：歹= 1 ，七 是，日中的互不相同的等价类组成的集合 于是取定a 中的一个固定元素n a ，我们可以构造孟a g 脾，使得 孟( 】) = 吩u = l ，七) ，且对任意 m g h 】，s = 1 ，七 ， 有i ( b 1 ) = 口令z = 矿( 孟) ，易见 $ c g 。i 1 , g 叼i 2 。* g 毗i h ，且z f ( a g 置) 情形2 。当n 畲有g 的单位元时，由于g 含有无限多个元素。故 存在g g ，使得9 q = 娩，s = 1 ，七) 不含单位元从而根据情形1 可得，存在 叠d 眢1 9 n 2 9 i 2 ? ：蟹= 扛a gjz ( g m ) 一m ，3 = 1 ，硌 为f 的最终周期点，即存在m o ，p 0 ，使得p 咖p ) = p ) 由于 雪：a g - + 为同胚，且f o o = 雪0 f ，所以有 参( 面) 溉) = x ( 9 9 i ) = d - 8 = 1 ，七， j ”h ，o 蚤( 孟) = o of ”h 乍( 孟) = 雪o f p ( 孟) = = p ( 雪( 孟) ) 从而令y = 鸯 ) ，有 嗜智：= 扣a oiz ( ) = ，8 = 1 ，七 ， 且掣为f 的最终周期点 d 注记4 1 前面对元胞自动机的吸引子及周期性进行了论述，其 中一个自然的问题是，若元胞自动机有吸引周期点时，其特征为何 昵? 下面对自由群g 的情形我们给出了一种刻画 1 3 河北师范大学项士学位论文 若a 为有限状态集，g 为一可数自由群，f ：a g + 俨为一元胞 自动机，且卫为f 的吸引的周期点，刚对任意g g ，由g 诱导的俨 上的左平移作用多：_ 有垂) = z 证明- 由于对任意n 1 ，p ：a g o a a 也是一个元胞自动机，所 以我们不妨设f 的这个吸引的周期点是吸引的不动点由引理3 1 知，存在z 的一个吸引域u ，使得矿是由有限柱集的并所构成，因 而可设 ，= c 置翌? ? 。鼍= iz 瓯) 如，如c a , j = 1 ，2 ，s ， 由于g 是可数自由群，所以每个不是单位元的元素都是无限阶的这 样一来，对任意g g ，若g 是单位元，显然有( 蕾) = 霉；若g 不是单位元， 厨必存在充分大的k ，使得g 与扩1 都不在集合 瓯虻1 ，七，i = 1 ，8 中于是，可取如u 一1 ，8 ) 和n a ，并构造i ，a g ，使得 玑) = u = 1 ，8 ) 由于矿茌 吼。，皿 0 = l ，8 ) ，所以 我们可令暂( 纸) = ，且对于任意的 g g t ，歹= 1 ，s u 矿，j = 1 ，3 ) ) ， 令幼= 岛显然 秒唆袈。复，且扩( 耖) ( ) = l ，( 矿) = ，j = 1 ，s 从而暑矿口n u 谚同理可证矿+ 1 u n u 9 由于垂：- + 俨为 同胚，z 为吸弓l 的不动点，且雪o f = f o 雪，所以扩( z ) ，矿+ 1 ( z ) 也为吸 引不动点，且吸引域分别为矿c 厂和矿+ 1 厂于是对于! ，矿u n u 和 名矿+ 1 u n u ，我们有 矿( z ) = l i mf “白) = $ = l i r af “( z ) = 蚕1 ( z ) ， n _ + n - + 从而矿+ 1 p ) = 矿( $ ) 再由多为同胚可得垂( 茹) = 茁 1 4 河北师范大学硕士学位论文 5 来自物理模型的一类元胞自动机 设a 和d 分别为有限集，g 为一可数群，赋予a 离散拓扑，且 俨c 有乘积拓扑，那么a d x g 是紧致乃空间对g g ，定义 耍：a d 。g + a d 。疗 茹卜+ 如；护， 其中妒：d g + a 定义为 z e ( d , g ) = $ ( d ，g g ) 我们称蚕为由g 所诱导的a d g 上的左平移作用 定义5 1 着映射f ：胪坩- + a d x g 满足以下条件t 存在有限 集mcg 及映射，：d a d x m + a ，使得对任意石a d 。g 及任意 geg ，d d ，有f ( z ) ( d ，g ) = f ( d ，m ) ( 这里x f l m = ( 如) l d x f ) ，则称f 是 一元胞自动机，并称，是f 的局部函数，m 是，的作用域 为了与前面的述语。元胞自动机。相区别，我们将这里的f 称 为时间演化函数 从物理学的意义来说，a 通常表示的是粒子本身所具有的状态 或颜色。而d 通常表示诸如粒子的运动速度等物理量 从a d g 具有乘积拓扑来看，形如 一( d r ，g z ) ( 如，9 1 ) ( d t ，弧) ( ，g k ) 。口l l 8 m l n l 女 = z a d 。giz ( 墙，毋) = ，i = 1 ，m ，j = 1 ，七) 的柱集构成了a d x g 的拓扑蓦其中m 是d 中元素的个数设口是从 自然数集n 到g 的1 一l 到上的对应，并令盯( 呐= 鲰，于是g 可表示 为 卯，g z ，鲰， 在a d x 口上定义度量d 为： 1 d o ，y ) = 云甘$ ( 函，船) = 霉( d i ，毋) o = l ，m ，j = 1 ，七) ， 且存在1 i m ，使得z 他，鳜+ i ) z ，似，g k + 1 ) 1 5 河北师范大学硕士学位论文 同样可以证明对于上述不同的盯所定义出的不同的度量是相互 等价的 引理5 1 设f ：a d 。g _ a d 。g 是时问演化函数，则对任意g g ， 有亘o f = f o 雪 证明直接由定义验证即可 记s = n l 口2 ：以a ，= 1 ，m ，即s 是由a 中的成员组 成的长度为m 的词所构成的集合令d = d l ，d 2 ，d ，i 现定义映射 t ：a d x a _ 沓 zh r p ) ， 其中r ( z ) ：g _ + s 定义为： r ( z ) ( 9 ) = $ ( d l ，g ) 霉( 西。，g ) 引理5 2 上面定义的映射r ：a d 。g - 4 萨是同胚 证明t 易证r 是既单且满的映射由于a 以g 与舻都是紧致的， 所以只须证r 是连续的即可事实上，对z a d 。g 及s 0 ，取七 0 ， 使得 e 令6 = ，于是当掣鼠o ) = z a d 。g ld ( x ，力 田，即 妒阻，毋) = z ( 噍，缈) ，i = 1 ，m ，歹= l ，七时，我们有 r ( z ) ( 毋) = $ ( d 1 ，g j ) x ( d 2 ，毋) 茁( 厶。9 j ) = y ( d l ，g j ) y ( d 口，彩) ! ，( ，g j ) = r ( f ) 渤) ，j = 1 ，后 于是d p o ) ，r ( 可) ) 丢 0 ，使得d 0 ，) 2 4 时，有d ( f ( x ) ，f ( 们) 1 ，即 x ( g j ) = ( 毋) o = 0 ，1 ，七) 时，有 f ( z ) ( 跏) = f ( y ) ( g o ) ( 蠢) 令n = g o ，g l ，船 ，且m = 酊1 q 定义映射 1 ：a 咎_ a u 卜+ ，) ， 其中，( ，) 满足t 对u a m ，选取z 俨，使得zi 材= 埘，令，) = f 0 ) ( 1 g ) ( 这里1 g 为g 的单位元) 往证若一a p ，且一i m - - - = u ，则 f ( x 0 ( 1 a ) = f ( x ) ( 1 a ) 由于i m = i m ，所以 翕- 1 x ( g j ) = $ ( 酊1 彩) = 一( 酊1 毋) = 酊1 ( ) ( 毋) ，歹= o ，1 ，七 由( 睾) 知 f ( 酊1 z ) ( 9 0 ) = f ( 鼯1 一) ( g o ) 又因对任意g g 有f 0 雪= 雪o f ，故 茹1 ( f ( z ) ) ( 卯) = 酊1 ( f ( 一) ) ( 册) ， 从而 f ( z ) ( 酊1 9 0 ) = f ( 一) ( 酊1 9 0 ) ，即f ( x ) ( 1 0 ) = f ( 一) ( 1 g ) 】7 河北师范大学硕士学位论文 这就表明，) 的定义与z 的选取无关，即，和) 的定义是合理的 对任意g g 和任意z a a ，由于f 0 蚕= 垂o f ， f p ) 0 ) = 参o f ( x ) ( 1 a ) = f o 蚕0 ) ( 1 g ) = ，( 缸l m ) 于是据元胞自动机的定义知f ：a g _ a g 是一元胞自动机，为f 的 局部函数，m 为其作用域 定理d 设a 和d 为有限集，g 为一可数群，f ：a d 。g - - 3 a d 。g 为一时间演化函数，则f 拓扑共轭于萨上的一元胞自动机( 其中 s 是由a 中成员组成的词长为m 的诃所构成的集合，仇是d 中元素 个数) 证明：在萨上定义一个连续映射h ：酽一萨如下t 设r ： 。g 一酽，霉t - - - ) 1 - ( x ) 的定义如引理5 1 后所述由引理5 2 ，对任意 z 萨，我们有t - 1 ( ) a d “于是，对任意g g ，有 日( z ) ( 9 ) = f ot - 1 ( z ) ( d l ，g ) fo y - - i ( z ) ( 如，9 ) f0y - i ( z ) ( 6 k ，g ) = t o f o t _ 1 0 ) ( g ) ， 即h = r o f o r 一1 下面证明h ：s g _ + s a 为一元胞自动机 对任意g g ，由于f o 耍= 雪o f ，且7 o f = 日o f ，并结合引理5 3 知， 日。雪= r o f o r 一1 0 雪= r o f o # o r 一1 = r o 亘o f o r 一1 = 雪o t o f o r 一1 = 鸯o i i 于是据引理5 4 知，( 铲，日) 为一元胞自动机 口 由定理d 及定理a ，b ，c ，我们得到- 定理设( a d g ，f ) 为一时间演化函数，则f 总有下列形式之 一l 】8 河北师范大学硕士学位论文 1 存在两个互不相交的吸引子，且因此它的拟吸引子所构成 的集合的基数是拽 2 存在唯一极小吸引子y ，它是g 一不变的，即对任意g g ， 有蚕( y ) = y ，且y 含于任意其它吸引子之中 3 存在唯一极小拟吸引子，且它含于任意其它吸引子之中 定理矽设a ，d 为有限集，g 为一可数群，f ：a d g + a d 。g 是 元胞自动机，y 俨。口是f 的闭不变子集，若f 在y 上的限制fl ， 是拓扑传递的，则fh ，或是敏感依赖的。或y 是由f 的一周期轨组 成 定理：设a ，d 为有限集，g 为一有限剩余的可数群。f ：a 。d 坩甘 a d g 为元胞自动机，则f 的最终周期点组成的集合在a d 。g 中稠密 河北师范大学硕士学位论文 参考文献 【1 】p e t rk u r k a ，t o p o l o g i c a ld y n a m i c so fc e l l u l a ra u w m a t a ，p r e p r i n t f 2 】j - p a l l o u c h e ，m c o u r b a g e ，g s k o r d e v ，n o t e so i lc e l l u l a ra u t o m a t a ，c u b o ， m a t e m a t i c ae d u c a t i o n a l ，3 ( 2 0 0 1 ) ，2 1 3 2 4 4 【3 】t o s h i on i w a ，o nt h el a wo fe n t r o p yi n c r e a s eo fs o m ec e l l u l a ra u t o m a t a o n 泓，j o u r n a lo fs t a t i s t i c a lp h y s i c s ，8 9 ：3 - 4 ( 1 9 9 7 ) ，8 0 1 8 1 6 【4 】卫t l l l i oc e c c h e r i n i - s i l b e r s t e i n ，m i c h e lc o o r n a e r ，t h eg a r d e no fe d e nt h e o - r e u lf o rl i n e a rc e l l u l a ra u t o m a t a , e r g o d t h & d y n a m s y s ，2 6 ( 2 0 0 6 ) ，5 3 - 6 8 【5 】e a k i n ，j a u s l a n d e r ，k b e r g ，v q h e ni sat r a n s i t i v em a pc h a o t i c ? c o n v e r g e n c ei ne r g o d i ct h e o r ya n dp r o b a b i l i t y , w a l t e rd eg r u y t e r & c o ， b e r l i n ，1 9 9 6 ，2 5 - 4 0 【6 】e g l a n e r ，b w e i s s ，s e n s i t i v ed e p a n do n 雠谳c o n