（应用数学专业论文）初等元胞自动机时间序列的非周期性.pdf

初等元胞自动机时间序列的非周期性 中文摘要 初等元胞自动机时间序列的非周期性 摘要 自然界存在着许许多多的复杂系统，这些系统的每一部分结构可以非常简单，但 由于各部分之间存在着一定的关联( 耦合) ，最后表现出的整体性态可以极其复杂 元胞自动机就是研究复杂系统的理想化的一种数学模型，它最早是由v o nn e u m a n n 在研究生命系统的自我复制现象时提出的，后来被广泛地用于模拟多种自然现象和生 命现象 9 0 号初等元胞自动机时间序列的非周期性已经清楚了 1 6 ，本文通过用1 2 6 号和1 2 2 号初等元胞自动机模拟9 0 号初等元胞自动机，来研究1 2 6 号和1 2 2 号初等元胞自动机 任意初始条件下的时间序列的性质证明了。 ( 1 ) 1 2 6 号初等元胞自动机下任意有限初始条件迭代产生的时间序列是非周期的 ( 2 ) 1 2 2 号初等元胞自动机规则下一类有限初始条件， s o = 0 0 1 0 2 七1 1 1 0 2 七2 1 1 0 2 k s 一1 1 0 2 k 一1 1 0 0 产生的时间序列是周期的其中和n ( i = 1 ，2 ，n ) 是任意正整数除此类型以外 的有限初始条件产生的时间序列是非周期的 关键词s非周期性；元胞自动机；不规则块；位置函数 作者：孙克文 指导教师：王益 a p e r i o d i c i t yi nt h ee l e m e n t a r yc e l l u l a ra u t o m a t o n a b s t r a c t a p e r i o d i c i t yi nt h ee l e m e n t a r yc e l l u l a ra u t o m a t o n a b s t r a c t t h e r ea r em a n yc o m p l e xs y s t e m si nn a t u r e ，t h es t u r c t u r e so ft h e i rc o m p o n e n t sm a yb e q u i t es i m p l e ，h o w e v e r ，t h e yc a l ld i s p l a yv e r yr i c ha n dc o m p l e xg l o b a lb e h a v i o r ss i n c et h e r e a r el o c a li n t e r a c t i o n sa m o n gt h ec o m p o n e n t s c e l l u l a ra u t o m a t aa r ei d e a lm a t h e m a t i c a lm o d e l 8i ns t u d y i n go fc o m p l e xs y s t e m s h i s - t o r i c a n y , t h ef i r s tc e l l u l a ra u t o m a t o nw a sp r o p o s e db yv o nn e u m a n nt os i m u l a t et h es e l f - r e p r o d u c t i v ep h e n o m e n a i nl i v i n gs y s t e m s s i n c et h e nt h e yh a v eb e e nu s e dw i d e l yt os i m u l a t e v a r i o u sn a t u r a la n dl i f ep h e n o m e n a t h ea p e r i o d i c i t yo fa l lt e m p o r a ls e q u e n c e sg e n e r a t e db y r u l e9 0a r ea l r e a d yc l e a r 。a n da sh a sb e e nn o t e dr u l e s1 2 6a n d1 2 2c a ns i m u l a t er u l e9 0i nt h a t t h e i rb e h a v i o r sc o i n c i d ew h e nr e s t i c t e dt oc e r t a i ns p a t i a ls u b s e q u e n c e s t h i sp a p e rp r o v e d t h a t ： ( 1 ) e v e r yt e m p o r a ls e q u e n c eg e n a r a t e db yr u l e1 2 6w i t ha r b i t r a r yf i n i t e i n i t a lc o n d i t i o n s o na ni n f i n i t el a t t i c ei sa p e r i o d i c ( 2 ) w i t ht h ee x c e p t i o no ft h ec a s et h a tt h et e m p o r a ls e q u e n c e sg e n a r a t e db yt h ef i n i t e i n i t i a lc o n d i t i o n so f s 0 ：0 0 1 0 2 h 一1 1 0 2 b 一1 1 0 2 b 一1 1 0 2 k 1 1 0 0 a r ep e r i o d i c ，e v e r yt e m p o r a ls e q u e n c eg e n a r a t e db yr u l e1 2 2w i t ha r b i t r a r yf i n i t ei n i t a lc o n - d i t i o n so na l li n f i n i t el a t t i c ei sa p e r i o d i c k e y w o r d s ：a p e r i o d i c ，c e l l u l a ra u t o m a t a ，i r r e g u l a rb l o c k ，p o s i t i o nm a p p i n g w r i t t e nb ys u nk e w e n s u p e r v i s e db yp r o f w a n gy i i i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明本人承 担本声明的法律责任 研究生签名：趸丛! 直l 童日期； 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸质论文的内容相一 致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容论文的公布( 包括刊登) 授权苏州大学学位办办理 研究生签名：列：莹塞日期：兰! ! 丛幺i 正 导师签名；至蚕芷日期：丛垒星，坠l 丫导师签名；尘鱼芷日期：丛垒星，坠l 丫 初等元胞自动机时间序列的非周期性 第一章元胞自动机简介 1 1 引言 第一章元胞自动机简介 自然界存在着许许多多的复杂系统，这些系统由大量的分支组成，每个分支的结 构和性质可以非常简单，但由于各分支之间存在着一定的关联( 相互作用) ，最后表现 出的整体性态却可以极其复杂【1 ，2 】处理这样的( 非线性) 复杂系统，用传统的方法 是不合适的，需要新的思想和方法元胞自动机便是研究复杂系统的理想化的一种数 学模型，同时，元胞自动机也可以看成是一个并行计算机而用于并行计算的研究，它 具有通用图灵机的计算能力因此，元胞自动机的研究对于复杂系统的研究、对于并 行计算理论和大型的并行计算模型的研究以及实际应用有着非常重要的意义元胞自 动机也可用来研究很多一般现象其中包括通信、信息传递、城市规划、计算、构造、 竞争、复制、生长与进化现象等同时它为动力学系统理论中有关秩序、紊动、混 沌、非对称、分形等系统整体行为与复杂现象的研究提供了一个有效的模型工具 元胞自动机可以看成为一类无穷维动力系统，其特点是空间、时间和状态都离散， 同时每个变量只取有限个状态它最早是由v o nn e u m a n n 在5 0 年代研究生命的自我 复制问题时提出来的一种数学模型f 3 ，4 1 二十世纪六十年代h e d l u n d 开始建立元胞自 动机的数学理论，他在论文中对元胞自动机作了较为全面的研究，得到了许多深刻的 结论七十年代c o n w e y 提出了著名的生命游戏( g a m eo fl i f e ) ，它事实上只是一个二 维的元胞自动机，却能模拟出生命活动中的生存、灭绝、竞争和繁衍等现象，引起了广 泛的关注到了八九十年代，随着计算机的逐渐普及，元胞自动机的研究迎来了又一 个高潮，w o l f r a m 是其中的领军人物之一，他对元胞自动机的研究作出了很大贡献， 如第一次用元胞自动机来研究复杂系统，创造性地应用理论计算机科学中的工具来进 行元胞自动机的研究，提出了著名的二十个关于元胞自动机的理论问题 5 1 等 w o l f r a m 的二十个关于元胞自动机的问题对后来的影响深远，其中很多问题至今没 得以解决比如最基本的分类问题它在w o l f r a m 提出的元胞自动机的二十个理论问 题中位居第一元胞自动机构成方式繁杂，变种很多，行为复杂故其分类难度也较 大，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要 的研究课题和核心理论，在基于不同的出发点，元胞自动机可有多种分类，其中，最 具影响力的当属w o l f r a m 做的基于动力学行为的元胞自动机分类，而基于维数的元胞 自动机分类也是最简单和最常用的划分后来许多学者为了完善这个分类，从各种不 同的角度给出了许多不同的分类【6 ，7 ，8 1 下面就上述的前两种分类作进一步的介绍 w o l f r a m 通过大量的计算机实验，按照在计算机上所观察到的动力学行为将所有元 胞自动机分成以下四类【9 1 9 。 初等元胞自动机时间序列的非周期性第一章元胞自动机简介 ( 1 ) 趋于个空间平稳构形，即每个元胞处于相同状态； ( 2 ) 趋于一系列简单的稳定结构或周期结构； ( 3 ) 表现出混沌的非周期行为； ( 4 ) 出现复杂的局部结构，或者说是局部混沌，其中有些会不规则的传播 前三类相当于低维动力系统中常见的不动点、周期轨和混沌，第四类则被认为是可 以与生命系统等复杂系统相比拟的自组织行为这是第一次对元胞自动机进行分类， 而且比较直观但这种分类是现象学分类，并不严格 理论上，元胞自动机可以是任意维数的那么，按元胞空间的维数分类，元胞自动 机通常可以分为： ( 1 ) 一维元胞自动机；元胞按等间隔方式分布在一条向两侧无限延伸的直线上，每 个元胞具有有限个状态，设状态集合s = ( s 1 ，8 2 ，一七 ，定义邻域半径r ，元胞及其左右 两侧的2 r 个元胞作为其邻域集合，定义在离散时间维上的转换函数f ：s 2 r + 1 s 可以记为：s t “= ，( s ：州，s ：- l s ：，s t + 。，s i + r ) s i 为第t 个元胞在t 时刻的状态 称上述a = sn ，) 三元组为一维元胞自动机 对一维元胞自动机的系统研究最早，相对来讲，其状态、规则等较为简单，往往其 所有可能的规则可以一一列出，易于处理，研究也最为深入目前，对于元胞自动机 的理论研究多集中在一维元胞自动机上w o l f r a m 对元胞自动机的动力学分类也是基 于对一维初等元胞自动机的分析研究得出的它的最大的一个特征在于容易实现元胞 自动机动态演化的可视化：二维显示中，一维显示其空间构形，空间维；另外一维显 示其发展演化过程，时间维 2 ) 二维元胞自动机：元胞分布在二维欧几里德平面上规则戈分的网格点上，通常为 方格划分以j h c o n w a y 的”生命游戏”为代表，应用最为广泛由于，世界上很多 现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上， 所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维元胞自动机模型 ( 3 ) 三维元胞自动机：目前，b a y s 等人在这方面做了若干试验性工作，包括在三维 空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论 ( 4 ) 高维元胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少l e e m e e k e r 在他的硕士论文中，进行了对四维元胞自动机的探索 另一方面，自从1 9 8 4 年w o l f r a m 引进形式语言来对元胞自动机复杂性方面进行研 究( 参见【1 0 d 讨论的多数工作是研究元胞自动机的极限集和演化序列的复杂性这方 面有很多成功的例子见【1 1 ，1 2 ，1 3 ，1 4 ，1 5 1 1 9 9 0 年j e n 证明了9 0 号初等元胞自动机在单个位置上的演化序列平凡情况外都是 2 初等元胞自动机时间序列的非周期性第一章元胞自动机简介 非周期的，以及相关的一些非线性元胞自动机的非周期性 1 6 】这种利用已知线性自动 机的性质去推测和证明与之相关的一些非线性元胞自动机性质的新的研究方法，之后 获得了广泛的关注f i o 本文就是在学习这种方法的基础上，证明了1 2 6 号和1 2 2 号初 等元胞自动机时间序列的非周期性其中第一章简要介绍了元胞自动机的发展历史和 基本定义；第二章讨论了1 2 6 号初等元胞自动机时间序列的非周期性；第三章对1 2 2 号初等元胞自动机时间序列的非周期性进行了分析；最后一章给出了结论和展望下 节先给出元胞自动机的定义 1 2元胞自动机的定义 本文只给出一维元胞自动机的定义，同时每个元胞只取两个状态 考虑在双侧无穷直线上有无限多个分布在整数格点上的元胞，每个元胞有两个状 态，用符号0 和1 表示 令a = o ，1 ) 代表每个元胞的状态集合双向无穷二元序列 z = z i x o x l ，z i a 称为元胞自动机的个构形，所有构形的集合称为构形空间，记为a z 我们假定时间是离散的，对一个构形来说，每一个元胞都同时发生变化 记为元胞自动机在t 时刻的构形，则时刻t + 1 的构形z t + 1 完全由决定：时 刻t + 1 的第i 个元胞的状态是由时刻t 的第i 个元胞以及相邻距离不超过r 的2 r 个 元胞的状态所决定的，用公式写出来即 “= ，( z ：- ，z ：_ l ，霹，z ：+ 1 ，z t + ，) 其中，与i , t 无关事实上，是a 2 r + 1 到a 的一个映射利用，可诱导出映射 f ：a z _ a z ，满足 f ( z ) t = ，( z i r ，盈一i ，z ，x i + l ，z i + r ) 为了规范化，我们把上面的叙述写成如下定义： 定义1 1 映射f ：a z a z 称为个元胞自动机，若存在， 0 及f ：a 2 r + 1 一a 使 得对任意的构形z = 。一i x o x l ，满足 f ( z ) i = ( z i r ，戤一i ，z i ，x i + i ，x i + r ) ，称为元胞自动机的局部规则， ，称为邻域半径，f 称为元胞自动机的全局规则 3 初等元胞自动机时间序列的非周期性第一章元胞自动机简介 从上面的定义可以看出元胞自动机的一般特征： ( 1 ) 空间离散、齐性：即元胞的分布方式相同； ( 2 ) 时间离散； ( 3 ) 状态离散、有限； ( 4 ) 同步计算：即计算的并行性； ( 5 ) 局部性：即每个元胞的当前状态只对半径的领域中的元胞在下一时刻的状态可 能发生影响； ( 6 ) 维数高：即变量个数很多 定义1 2 元胞自动机f ：a z _ a z 称为初等元胞自动机，若其邻域半径为r = 1 本文主要讨论初等元胞自动机，即状态数为2 而邻域半径为1 的一维元胞自动机 初等元胞自动机的局部规则事实上是映射，：a 3 一a ，满足 z t i + 1 = ，( z ：一1 ，z ：，z ：+ 1 ) ，vi z 全局规则f 满足f ( z ) i - ，( 翰一1 ，瓤，毛+ 1 ) ，i z 在a z 上定义移位算子口为盯( z ) i = x i + i ，t z 定义连续映射f ：a z 胪若f 与盯可交换，即对任意的z a z ，有f ( 盯( z ) ) = 仃( f ( z ) ) ，则称f 为元胞自动机 此定义与定义1 1 等价，即对于与盯可交换的连续映射f ，必存在r o 和局部映 射f ：a 2 r + 1 _ a ，使得对每个构形z = z l x 0 ：e i ，i z ，有 f ( z ) i = f ( x i r ，z i 一1 ，x i ，x i + l ，z + r ) 同样地，f 是元胞自动机的全局映射 4 初等元胞自动机时间序列的非周期性g ：- 章1 2 6 号初等元胞自动机时间序列的非周期性 第二章1 2 6 号初等元胞自动机时间序列的非周期性 9 0 号初等元胞自动机时间序列的非周期性已经清楚了【1 6 l ，本章通过1 2 6 号初等元 胞自动机模拟9 0 号初等元胞自动机，以一个位置函数咖为纽带，来研究1 2 6 号初等元 胞自动机任意初始条件下的时间序列的性质主要结论如下： 定理2 11 2 6 号初等元胞自动机下任意有限初始条件迭代产生的时间序列是非周期 的 2 1 基本概念和结果 记双侧无穷序列= z 一2 z l z o z z z ，表示t 时刻的构形，则下一时刻演化 为z t + 1 ，其中每个元胞的状态z t + 1 由如下法则决定： z t + 1 = ，( z ：一1 z i t 击i t + 1 ) ， 这里，表示元胞自动机的局部规则对构形而言，就有全局规则f ，使得f ( ) = z t + l ， 即 f ( x ) i = ，( z ：一l z ：$ 0 1 ) 设= z ：，一o 。 i o o ，称为时间t 下的空间序列 设暇= z 毛t = 0 ，1 ，2 ，称为位置t 处的时间序列 定义2 1 若对于空间序列= z ：，一o o i ，存在整数m ，满足：当 n 时，z ? = 0 ，且z = z = 1 ，称此空间序列为有限初始条件其长度定义为 一m + 1 定义2 2 对于时间序列眠= z l ，t = 0 ，l ，2 ，若存在时间0 t o o 和整数0 p t 时，有z ：却= z ：，则称此时间序列的周期为尸 命题2 19 0 号初等元胞自动机任意有限初始条件迭代生成的时间序列，除了平凡的情 况，都是非周期的平凡是指：设初始条件为s o ，其长度为奇数，s o 是个中心对称 的空间序列，中心串叫。有限步后会全为o ( 见文献【1 6 】) 本文研究1 2 6 号初等元胞自动机时间序列的非周期性，其局部规则 2 6 为： 1 1 1 ，0 0 0 0 ；1 1 0 ，1 0 1 ，1 0 0 ，0 1 1 ，0 1 0 ，0 0 1 1 9 0 号初等元胞自动机的局部规则f 9 0 为： 1 1 1 ，0 0 0 ，1 0 1 ，0 1 0 叫0 ；1 1 0 ，1 0 0 ，0 1 1 ，0 0 1 1 5 初等元胞自动机时间序列的非周期l i第二章1 2 6 号初等元胞自动机时间序列的非周期性 2 21 2 6 号初等元胞自动机规则下的非周期性 为了后面的证明方便我们加以下几个定义； 定义2 3 在1 2 6 号初等元胞自动机下，称空间序列中的串0 1 2 n , - - i 0 和1 0 2 n - 1 1 为不规则 块，串0 1 2 n o 和1 0 2 n 1 称为规则块 注：空间序列正好由不规则块和规则块组成不规则块的定义来源于1 2 6 号初等元胞 自动机和9 0 号初等元胞自动机规则的差别易知1 2 6 号初等元胞自动机规则对规则块 的作用，主要用了 1 1 1 ，0 0 0 0 ；1 1 0 ，1 0 0 ，0 1 1 ，0 0 1 叫1 而且往下迭代并不会出现用到1 0 1 ，0 1 0 1 的情况即此时与9 0 号初等元胞自动 机规则作用效果一样由此想到若把不规则块变成规则块，则1 2 6 号初等元胞自动机 可“模拟”9 0 号初等元胞自动机去除不规则快的方法为t 在串0 1 2 n - 1 0 中加1 ，在串 1 0 2 n 一1 1 中加0 记空间序列岛中去除不规则快后，新的空间序列为g ( 岛) 在任意空间序列中不规则块的个数用龟表示0 1 2 n - 1 0 的左边界为0 ，其长度定 为：l e n ( 0 1 2 n 一1 0 ) = 2 n 一1 1 0 2 铲1 1 的左边界为1 ，其长度定为；l e n ( 1 0 2 n - 1 1 ) = 2 n 一1 规则块的左边界类似定义下面的命题说明不规则块随时间是不增的 命题2 21 5 6 号初等元胞自动机规则下，任意有限初始条件8 0 ，c 4 关于时间t 是非增的 函数 证明：分两种情况看t 如果s t 中存在不规则块1 0 2 n - 1 1 ，则；s 高( 1 0 2 n - - 1 1 ) = 1 0 2 n + 1 l 或0 1 2 n + l o ，两者均是 不规则块，说明c t 非增 如果s t 中存在不规则块0 1 2 n - 1 0 ，则t ( 反证) 首先危：( o l o ) = d ，若5 1 ( 0 1 2 n + 1 0 ) 中无不规则块，则s 当j h 为奇数时， f i l ( 0 1 2 n + 1 ) = 0 0 0 ( 1 1 0 0 ) 孚 1 1 0 或1 1 1 ( 0 0 1 1 ) t n - io q l ，但此时易知 危：( 0 1 2 n + 1 0 ) = d 当n 为偶数时，f 而1 ( 0 1 2 n + 1 ) = 0 0 0 ( 1 1 0 0 ) 量1 或1 1 1 ( 0 0 1 1 ) 詈0 ，但此时f 五l ( 0 1 2 n + 1 0 ) = 口 所以f i 嘉( 0 1 2 叶10 ) = 谚或含有不规贝块 而0 0 0 1 ( 0 0 1 1 ) t 1 - 0 0 0 ( n 为奇数) 在f 五l ( 0 1 2 n + 1 0 ) 中说明1 5 ：( 0 1 2 n + 1 0 ) 非空 下面位置函数的定义是用来跟踪不规则块左边界的位置在1 2 6 号初等元胞自动机 规则下的变化情况 6 ，碧曼慨) = x _ _ 2 x _ _ i x o x l l 9 2 中第i 个规则块为i f , 其左边界的位置记为甄下面 给出位置函数的定义： 定义2 4 函数 例如：串 西( ) = + 1 ， + 1 ， 岛一k ， 一詹， 一忌。 膀一 z h2l ，2 h + l2z h + 2 = z + 3 = o ； z 商2u ，o h + 1 = z + 22 z + 3 。1 ； z 版。o ，z h j = 0 ，i = l ，4 ，5 ，七一1 ，七，忌+ 1 。 z b o = 1 ，歹= 一2 ，一1 ，2 ，3 ，6 ，7 ，七一3 ，七一2 ， z 一3 = 0 ，z h + 3 = o ； z 20 ，z 岛一j = 0 ，歹= 1 ，4 ，5 ，七一3 ，忌一2 o 一，= 1 ，j = 一2 ，一1 ，2 ，3 ，6 ，7 ，后一1 ，克，七+ 1 ， 。一3 = 1 ，z 十3 = 0 ； o 2l ，o 一歹= 1 ，i = l ，4 ，5 ，七一1 ，而，七+ 1 o h j = 0 ，j = 一2 ，- 1 ，2 ，3 ，6 ，7 ，七一3 ，后一2 。 茁殷一3 = 1 ，z h + 3 = 1 ； 。 孤2l ，z 一j = 1 ，j = 1 ，4 ，5 ，七一3 ，七一2 ， z o = 0 ，歹= 一2 ，一1 ，2 ，3 ，6 ，7 ，七一1 ，k + l ， o h 一3 = 0 ，z h + 3 。1 ； 0 0 0 1 1 0 0 1 1 0 0 1 1 0 ， 曼，的譬置孕规则块0 1 1 0 的左边界，记为缸，则；( 乜) = q - 5 把串0 0 0 1 1 0 _ 0 1 1 0 0 1 1 0 迭 代一次后得剑旱 0 1 1 1 1 1 1 1 1 1 1 1 ， 新的串的左边界的位置正好在一5 注：从这个例子也能看出迭代下相邻的块与块长度小于3 会合并成新的块 引理2 1 设乳是个任意有限的空间序列，包含一个不规则块畦，它的左边界位置为 竺，且s t 中不存在满足( 赶) = ( 磅) 的不规则块哆，其中幻是不规则块巧左边界的莅 置则：6 ：+ 1 也是不规则块，且其左边界的位置是：咖( 恕) 。 证明：只证不规则块6 i 的左边界为1 的情况供似可证左边界为o ) 若1 e n ( b 9 3 ，即磷= 1 0 2 n + 1 1 ，6 i + 1 = 1 0 2 1 1 ，矿1 是不规则块，左边界为+ 1 ：砂仇) 若l e n ( 6 ：) = 1 则其形式为下面这四种类型中的一种： 0 0 0 1 1 0 0 1 1 0 _ 1 1 0 0 1 1 0 0 0 ， 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 ， 0 0 0 1 1 0 0 1 1 0 _ ! 1 0 0 1 1 0 0 1 1 1 ， 7 初等元胞自动机时间序列的非周期性第二章1 2 6 号初等元胞自动机时间序列的非周期性 1 1 1 0 0 1 1 0 0 1 1 0 _ _ 1 1 0 0 1 1 0 0 1 1 1 ， 其中上虹表示6 ：，无论那种形式往下迭代矿1 是不规则块，左边界为一k = ( ) 推论2 1 设s o 中第i 个块为b o ，其左边界的位置记为，c t 表示咖的t 次迭代，则； ( 乜) 乜+ t , v t 0 推论2 2 空间序列8 0 中恰好有两个不规则块b i ，b ，左边界分别为乜，b 如果( ) 扩( b ) ，v t 0 ，则：任意s t 中c t = 2 不变 如果3 t ，s t ：c t ( k ) = c t ( k j ) ，则：两个不规则块在t4 - 1 次迭代下结合成一个规则块 命题2 31 2 6 号初等元胞自动机规则下，任意有限初始条件s o ，如果满足在任意时间 m ，乃+ 卅内，c t 关于时间t 是保守的( 不变) 则存在以下关系： g ( 片2 6 f s 而】) = 盔【g ( s 乃) 】，0 t t 证明：由c t 保守和命题2 2 及其推论知s t 中任意两个不规则块醒和碡，左边界的 位置分别记为，磅，在1 2 6 号初等元胞自动机规则下满足；( 6 ：) 砂( 碡) 矿1 也是不规 则块 对s 而中任意不规则块印，有： 如果印= 1 0 2 1 1 ，则：印“= 1 0 2 n - - 1 1 ，g ( 1 2 6 1 0 2 卅1 1 】) = g ( 1 0 2 俨1 1 ) = 1 0 2 n i ，而 f 9 0 g ( 1 0 2 n + 1 1 ) 】= f 9 0 ( 1 0 2 卅2 1 ) = 1 0 孙1 ，此时满足g ( f 1 2 6 1 1 0 2 n + l l 】) = 1 9 0 g ( 1 0 2 n + 1 1 ) 】 如果铲= 0 1 2 叶1 0 ，则。印“= 1 0 2 n 一1 1 ，类似可知，满足： g ( 2 6 0 1 2 n + 1 0 】) = f 联) g ( 0 1 2 n + lo ) 】 如果译= 1 0 1 ，类似有印+ 1 的形式为0 1 2 七+ 1 0 ，其中七的值由母左右两边长度为2 的规则块的数量决定此时也满足，g ( f 1 2 6 0 1 2 n + 1o 】) = f g o g ( ) 1 2 1o ) 】 如果中= 0 1 0 ，则：铲+ 1 的形式为0 1 2 知+ 1 0 ，其中后的值由铲左右两边长度为2 的 规则块的数量决定此时也满足：g ( f 1 2 6 0 1 2 r * + l o ) = f 9 0 g ( 0 1 2 n + 1 0 ) 】 再由交换关系得： g ( 片2 6 i s r o ) = 【g ( s ) 】，0 t t 下面一个引理是9 0 号初等元胞自动机的一个性质： 引理2 2 在9 0 号初等元胞自动机规则下的任何有限初始条件s o 满足：当i n 时，x 0 = 0 ，且x o = x o = l ，长度l = n m + 1 则：当时间t = 2 七厶时， s t = s 0 0 2 + 1 一i ，s 0 8 初等元胞自动机时间序列的非周期性第二章1 2 6 号初等元胞自动机时间序列的非周期性 证明：因为9 0 号初等元胞自动机规则可写成： t “= 瓤t 一1 丰z o l ， 其中 表示模2 加法 容易推出 吃2 = 吒0 埘丰z o + 2 当0 j l 一1 时，歹。k ，。_ m 2 k 一2 钾= x m 0 一2 z + j = z 0 m 钾，o 当0 歹 i ，c t = c o ，耽o ，则。由命题2 3 和引理2 2 知，当时间t = 2 厶，可 写成三部分，中间为长为2 件1 一l 的0 串，左边部分记为s r ，右边部分记为s ，满 足g ( s f ) = g ( s ，) = c ( s o ) 记8 t 中的块, b o ，1 6 昌，5 歹中的块，b o ，r 喝，中间的0 串为昭定义局部函数妒t 用来联系初始块与s t 中，受初始块影响而产生的块即设 3 q l ，q 2 e z ，1 q l q 2 q ，使得：块6 0 ，b o l ，映入5 尹中的块的子集中，块嘬+ l ，6 墨， 映入当中的0 串中，块屹+ 。，6 易映入s 中的块的子集中 例如：有限初始条件；0 1 1 0 1 1 0 ，初始块为：b l = 1 1 ，6 2 = 0 ，6 3 = 1 1 ( 写法去掉 了左右边界) 迭代如下， 0 1 1 q 1 1 0 0 1 l ! ! ! ! l o 0 1 1 幽盟q 1 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 9 初等元胞自动机时间序列的非周期性第二章1 2 6 号初等元胞自动机时间序列的非周期性 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 。 o i ! l ! ! ! ! ! ! ! ! l l ! 1 0 0 11 q q q q q q q q q q q q q11 0 0 1 11 1 q q q q q q q q q q q1 11 1 0 0 1 1 0 0 1 1 q q q q q q q q q l l 0 0 1 1 0 块的下划线表示受初始块影响产生的新的块，在t = 8 时，正好是中间的0 块，即此 时，把b l ，b 2 ，b 3 均映入了中间0 串 易知当t 取2 t ，3 t ，4 t 时，受培影响的新块就是中间的0 串 定义整体函数矿表示所有上面所定义的局部函数，的集合( t = 2 2 三) 设不规 则块b o 满足：矿( b o ) = ，d t 5 ，t = 2 ，下证：当，= 2 t + 1 时，由于c t 保持不变，只 可能圣r ( ，b t ) - ， 不难证明当，= 2 件1 时，一仍然可以类似分解成三部分，中间为长为2 t + 2 一三的 0 串，左边部分记为s ，右边部分记为宰，满足g ( 占，) = g ( ) = 0 ( 8 0 ) 如果矿( r 醪) 在中间的0 串中，由引理2 1 知圣t ( r 巧) 也是不规则块由于中间0 串的长度固定，中为2 七十1 一厶若三为奇数，中间块为不规则块，西t ( 曙) 在s 一中 间的0 串中而s 一中间的0 串也是不规则块，这与推论2 2 矛盾；若l 为偶数，中 间块为规则块，与龟保持不变矛盾 如果矿( r b 歹) - t ，显然除非不规则块之间产生碰撞，这与c t 保持不变矛盾 根据从时间t = 2 。到，= 2 2 + 1 ，中间0 串的右边界位置从z 罨+ 2 t l + l 变化到 z 罨榭+ 。一工+ l i 恰好平均每步向右边平移了单位位置由推论2 1 知，不规则块左边界的 位置每步迭代最多向右移动一位向右移动时不规则块的形式为：1 0 2 n + 11 或0 1 2 n + 1 0 ， 有限步后成为1 0 1 或0 1 0 后，在往下迭代不规则块左边界的位置必然向左移了而l 是有限长，t = 2 。l ，当时间t 足够大，圣t ( r b ) 肯定会进入中间串从而和c t 保持 不变矛盾 由此再结合命题2 2 ，c t 随时间收敛到0 或1 再根据l 的奇偶性，l e n ( s 2 ) = l + 2 t ， 可得出：如果长度为奇数，则：当z 足够大后，c t 保持为1 如果长度为偶数，则；当 t 足够大后，q 为0 推论2 3 在1 2 6 号初等元胞自动机规则下的任何有限初始条件s o ，设其长度为厶如果 长度为奇数，则：当t 足够大后，倪保持为1 ，且t = 2 七时刻不规则块就是中间得0 串 1 0 初等元胞自动机时间序列的非周期性第二章1 2 6 号初等元胞自动机时间序列的非周期性 定理2 11 2 6 号初等元胞自动机下任意有限初始条件迭代产生的时间序列是非周期 的 证明：设有限初始条件为s o ，长度为厶由命题2 4 知：只要证s o 中有个或没有 不规则块这两种情况 情况l ：s o 中没有不规则块，此时8 0 在1 2 6 号初等元胞自动机规则下迭代和与在9 0 号初等元胞自动机规则下迭代完全一样且8 0 长度为偶数，由命题2 1 知：s o 产生的 时间序列是非周期的 情况2 ：s o 中有一个不规则块，此时l 为奇数由命题2 3 和引理2 2 知，当时间 t = 2 t l ，8 t 还可写成三部分，中间为长为2 t + 1 一l 的0 串，左边部分记为s ，右边 部分记为s ，满足g ( s 尹) = g ( s ，) = g ( s o ) 由推论2 3 ，中间的0 串是不规则块 ( 反 证) 若存在周期的时间序列瞰，周期为p ，则：只要时间t = 2 2 足够大，即s t 中间的0 串足够长，记为昭可使眠中有长度为p 的段序列包含在曙迭代的倒三角0 中， 则：只能为全零串如图：旦处的时间串在职中 1 0 0 q 0 0 0 0 0 0 1 1 0 q 0 0 0 0 0 l 1 0 1 而能变成全0 串的只有序列 t o o ，但1 0 1 专1 所以不可能出现全0 串定理得证 初等元胞自动机时间序列的非周期性第三章1 2 2 号初等元胞自动机时间序列的非周期性 第三章1 2 2 号初等元胞自动机时间序列的非周期性 本章来研究1 2 2 号元胞自动机时间序列的非周期性它和1 2 6 号元胞自动机有很多 相关性 1 2 2 号的局部规则如下。 主要结果如下t 1 1 1 ，0 0 0 ，0 1 0 0 ，0 0 1 ，1 0 0 ，1 1 0 ，0 1 1 ，1 0 1 - 1 定理3 11 2 2 号初等元胞自动机规则下一类有限初始条件： s 0 ：0 0 1 0 2 k l 1 1 0 2 k 2 1 1 0 2 电一1 1 0 2 岛一1 1 0 0 产生的时间序列是周期的其中，t = 1 ，2 ，佗是任意正整数除此类型以外的有限 初始条件产生的时间序列是非周期的 先给出以下基本事实： ( 1 ) f n ( 0 1 2 n 0 ) = f ( 1 0 2 n 1 ) = 1 1 ， ( 2 ) ，n ( 0 1 2 n + 1 0 ) = ，n ( 1 0 2 n + 1 1 ) = 1 0 1 ， ( 3 ) ，( ( 1 1 + o o ) + ) ( 1 1 + o o ) 下面分六种情况来证明定理 证明：( 1 ) 先看有限初始条件s 0 = 0 0 1 0 2 七1 1 1 0 2 k 2 - 1 1 0 2 知3 1 1 0 2 k 1 0 0 易知，s o 有限步迭代后会生成0 0 1 0 1 0 1 0 1 0 0 ，不妨记为s t = 0 0 ( 1 0 ) n 1 0 0 ， 由于：0 1 0 0 ，1 0 1 _ 1 ，知s 升1 = o o i ( o i ) n 0 1 0 0 ，s t + 2 = o o l o ( i o ) n 1 0 1 0 0 ， 如图： 竺笪 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 l o 1 0 1 0 1 0 1 0 1 0 0 其中咖= 0 1 0 1 0 1 是周期串由图和1 2 2 号的局部规则，产生的时间序列是周期 的即8 0 产生的时间序列是周期的 初等元胞自动机时间序列的非周期性第三章1 2 2 号初等元胞自动机时间序列的非周期性 注：由上面的迭代过程可知，若定义 ( s ) = f ( o l s ) ，s 表示有限串，若有 ( s ) = s ， 称s 在 下为左斜周期类似定义厶( s ) = f ( s l o ) = s 称s 在厶下是右斜周期的 则：串0 1 0 1 0 1 0 1 0 是左斜周期的，同时也是右斜周期的 ( 2 ) 考虑初始条件s o ：o o ( 1 0 ) n 1 1 0 0 ，由于f ( o 0 0 1 ) = f ( 0 1 0 1 ) = 0 1 ，串( 1 0 ) n 是左斜周期的，再由f ( 0 1 0 1 1 0 ) = f ( o o o l l o ) = 0 1 1 1 1 和( 1 ) 知：考虑初始条件s o ： 0 0 ( 1 0 ) n 1 1 0 0 生成的时间序列的性质，只要考虑串0 0 1 1 0 0 生成的时间序列的 性质如图： 。0 0 1 0 1 0 1 0 1 0 1 1 0 0 - 由广1 ( 0 1 0 ) = 0 0 0 1 0 或0 1 0 0 0 或0 1 0 1 0 知：串0 0 1 1 0 0 向下迭代与在1 2 6 号元 胞自动机规则下作用完全一样就是不规则块为零的情况所以知其产生的时间序列 是非周期的 类似可知初始条件s o = 0 0 1 0 2 七1 一1 1 0 2 七2 1 1 0 2 b 1 0 2 k 一1 1 1 0 0 有限步迭代后， 生成串0 0 1 0 1 0 1 0 1 0 1 1 s + 0 0 ，其中s + 表示( 1 1 + 0 0 ) + 的子串其生成的时间序列 也是非周期的 ( 3 ) 考虑初始条件5 0 = 0 0 1 1 0 2 l 一1 1 0 2 七2 1 1 0 2 k a 1 0 2 k 1 0 0 ，此情况和( 2 ) 类 似，只要看串0 0 1 1 0 0 生成的时间序列的性质其是非周期的 ( 4 ) 考虑8 0 = 0 0 1 0 t m 一1 1 0 2 b 一1 1 0 2 k t 一1 i i 0 1 1 0 2 k + l 一1 i 0 2 k , n + 2 1 1 0 2 岛件m 一1 1 0 0 ， 由( 2