（应用数学专业论文）元胞自动机生成的时间序列的复杂性研究.pdf

元胞自动机生成的时间序列的复杂性研究 摘要 摘要 元胞自动机是自然界许多复杂系统的理想化数学模型，它可以模拟许多自然现象 与生命现象，大量未解决的问题为这个困难而有趣的领域展现了广阔的前景 自v o nn e u m a n n 首次提出元胞自动机的思想至今已有半个世纪，学者们对元胞 自动机进行了大量的研究，然而现在对元胞自动机仍然缺少有效的数学方法，严格的 数学结果也很少本文探求一种新的研究元胞自动机的方法，使用禁止字理论、计算 机搜索和符号动力学的方法对于2 5 6 个初等元艟自动机生成的时间序列f 只观察一 个位点上的演化所得到的序列) 进行复杂性分析借助时间序列所具有的特性通过 研究它的禁止字来研究演化语言( 本文所指的演化语言如无特别标注都是指宽度为 1 的时间序列所组成的语言) ，确定了大多数初等元胞自动机生成的时间序列所处的 c h o m s k y 层次以及严格的数学表达式 在对初等元胞自动机时间序列的禁止字分析之后，按照它们演化语言的复杂程度 分为以下四类：第1 类为满射，第1 i 类为有限补正规语言，第1 i i 类为无限补正规语 言，第1 v 类很有可能是非正规语言 第1 类情况中的初等元胞自动机没有禁止宇，其宽度l 的演化语言为最大可能 的正规语言，并且这一类中部分元胞自动机的任意宽度演化语言都是正规的 第1 i 类情况中的初等元胞自动机只有有限多个禁止字，因此其宽度1 的演化语 言为有限补正规语言 第1 i i 类情况中的初等元胞自动机有无限多个禁止字，但禁止字集是正规语言， 经过理论分析知道其演化语言为无限补正规语言此类情况中一个代表性的例子是 2 7 号初等元胞自动机 第1 v 类情况中的初等元胞自动机也有无限多个禁止字，但是它们的演化语言很 有可能不是正规语言，这类情况比前三种情况复杂的多，对这一类初等元胞自动机的 讨论尚未全部完成本文给出了其中5 6 号初等元胞自动机的宽度为1 的演化语言是 上下文无关语言的详细证明，并给出了严格的数学表达式 关键词：初等元胞自动机，时间序列，禁止字，形式语言，演化语言，c h o m s k y 层次 作者：秦大康 指导教师：谢惠民 元照皂动糗生戒熬时阀殍列的复聚性蛩 突 a b s 筝敷a g t a b s t r a c t 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 so fc o m p l e xs y s t e m si nn a t u r e ， t h e yc a ne m u l a t el o t so fp h e n o m e n o ni nn a t u r ea n dl i f ep h e n o m e n a m a n yu n s o l v e d q u e s t i o n si nt h i sd i f f i c u l ta n di n t e r e s t i n gf i e l ds h o wg r e a tp r o s p e c ti nt h ef u t u r e i th a sp a s s e dh a l fac e n t u r ys i n c ey o nn e u m a n nf i r s tp r o p o s e dt h ei d e ao fc e u u l a r a u t o m a t a ，s c h o l a r sh a v em a d el o r so fr e s e a r c ht oc e l l u l a ra u t o m a t a ，h o w e v e rt h e r ea r e f e we f f i c i e n tm e t h o d st os t u d yc e h u l a ra u t o m a t a ，a n dt h es t r i c tm a t h e m a t i c a lr e s u l t s a r ea l s of e w 。t h i sa r t i c l ee x p l o r e s8 艄w 妊n do fm e t h o dt os t u d yc e l l u l a ra u t o m a t a ，i n w h i c hb yu s i n gd i s t i n c te x c l u d e db l o c k st h e o r y , c o m p u t e rs e a r c ha n ds y m b o l i cd y n a m - i c st os t u d yt h et i m es e r i e s ( t h es e r i e sg e n e r a t e da to n es i t ei nt h ec o u r s eo fe v o l u t i o n ) g e n e r a t e db y2 5 6e l e m e n t a r yc e u u l a ra u t o m a t a u s i n gt h ec h a r a c t e ro ft i m es e r i e s ，w e c a ns t u d yt h e i re v o l u t i o nl a n g u a g e ( i nt h i sa r t i c l ew | t h o u ts p e c i a lr e m a r kt h ee v o l u - t i o nl a n g u a g e sw i d t hi sa l w a y s1 ) b ys t u d yt h e i rd i s t i n c te x c l u d e db l o c k s ，a n dp i n p o i n t t h e i rc h o m s k yl e v e la n ds t r i c tm a t h e m a t i c a le x p r e s s i o no ft h et i m es e r i e sg e n e r a t e d b ym o s te l e m e n t a r yc e l l u l a ra u t o m a t a a f t e rs t u d y i n gt h et i m es e r i e sg e n e r a t e db ye l e m e n t a r yc e l l l l l a ra u t o m a t a ，a c c o r d - i n gt ot h ec o m p l e x i t yo ft h e i re v o l u t i o nl a n g u a g ew ec a i lc l a s s i f yt h e mi n t of o u rc l a s s e s ： ic l a s so fs u r j e c t i v e ，i ic l a s so ff i n i t ec o m p l e m e n tr e g u l a rl a n g u a g e s ，i i ic l a s so fi n f i n i t e c o m p l e m e n tr e g u l a rl a n g u a g e s ，a n di vc l a s sw h i c ha r ep r o b a b l yu n r e g u l a rl a n g u a g e s 。 c 1 a s si ：t h ec e l l u l a ra u t o m a t ai nt h i sc l a s sh a v en od i s t i n c te x c l u d e db l o c k s ，t h e i r e v o l u t i o nl a n g u a g e sa r et h el a r g e s tr e g u l a rl a n g u a g e s ，a n df o rs o m eo ft h e mt h ee v o - l u t i o nl a n g u a g e sw i t ha n yw i d t ha r ea l s or e g u l a r c l a s si i ：t h ec e l l u l a ra u t o m a t ai nt h i sc o n d i t i o nh a v e 鑫越t ed i s t i n c te x c l u d e d b l o c k s ，a n dw ec a nk n o wt h e i re v o l u t i o nl a n g u a g e sa r ef i n i t ec o m p l e m e n tr e g u l a r c l a s si i i ：t h ec e l l u l a ra u t o m a t ai n t h i sc o n d i t i o nh a v ei n f i n i t ed i s t i n c te x c l u d e d b l o c k s ，a f t e rt h e o r e t i c a la n a l y s i sw ec a ns h o wt h a tt h e i re v o l u t i o nl a n g u a g e sa r e r e g u l a r a ne x a m p l ei sr u l e2 7e c a c l a s si v ：t h ec e l l u l a ra u t o m a t ai nt h i sc o n d i t i o na l s oh a v ei n f i n i t ed i s t i n c te x c l u d e db l o c k s ，a n dt h e i re v o l u t i o nl a n g u a g e sa r ep r o b a b l yn o tr e g u l a rl a n g u a g e s ，t h i s c l a s si sm u c hm o r ec o m p l e xt h a no t h e rc l a s s e s ，t h ed i s c u s s i o nf o r t h i sc l a s si sn o t c o m p l e t e dy e t i nt h i sa r t i c l ew ep r o v et h a tt h ee v o l u t i o nl a n g u a g eo fr u l e5 6e c a 嫩藏蠡动辘缀成鹣薅闯彦删熬鬟撩性研究矗b s t r a 秽 w i t hw i d t h1i sc o n t e x t - f r e el a n g d a g e ，魏n do b t a i nt h ee v o l u t i o nl a n g n a g 潞 ss t r i c tm a t h - e m a t i c a le x p r e s s i o n k e 滞o r d s ：i l e m e a t a r yc e l l u l a ra u t o m a t o n ，t i m e , 嚣e 照糕，d i s t i n c te x c l u d e db l o d c s ， f o r m a ll a n g u a g e ，e v o l u t i o nl a n g u a g e , c h o m s k yh i e r a r c h y w r i t t e nb yd a k a n gq i u s u p e r v i s e d 酶h u i m i nx i e 元胞自动机生成的时间序列的复杂性研究 第一章元胞自动机简介 第一章元胞自动机简介 1 1 引言 自然界中存在着许多复杂系统，这些系统的每一部分的结构可以非 常简单，但是由于各部分之间存在着一定的关联，最后表现出的整体性态 却可以极其复杂 1 ，2 ，元胞自动机就是这种复杂系统的一种理想化的数 学模型元胞自动机可以看成是无穷维动力系统中的一类，特点是空间、 时间和状态都离散，同时每一个元胞只取有限多个状态 元胞自动机是v o nn e u m a n n 于5 0 年代最早提出来的，用于模拟生 命系统所具有的自复制功能( 参见f 3 ，4 ，5 1 ) 为此，y o nn e u m a n n 设计了 一个有2 0 0 0 0 0 个元胞的二维元胞自动机，每个元胞有2 9 个状态，并证明 了这种元胞自动机具有自复制功能在这以后许多学者对元胞自动机作 了进一步的发展，例如【6 ，7 ，趴对v o nn e u m a n n 的工作的延续分成两个 方面，一方面是构造具有自复制功能的元胞自动机，另一方面通过用数学 方法研究元胞自动机的性质来研究自复制行为的本质在此过程中，大量 结构相对简单的具有自复制功能的元胞自动机被发现，并且得到了一些 关于元胞自动机产生自复制行为的简单性质到了5 0 年代末，元胞自动 机被发现可以看成是一个并行计算机，它可以和图灵机具有相同的计算 能力在6 0 年代末人们开始试图把元胞自动机和动力系统的研究联系起 来，这个过程中1 9 6 9 年在h e d l u n d 的经典的论文中【9 1 ，对序列移位动力 系统的研究其实也就是对元胞自动机的研究1 9 7 0 年c o n w a y 的生命游 戏( t h eg a m eo fl i f e ) 只用了一个二维的元胞自动机就模拟出了生命中 生存、灭绝、竞争等等复杂现象，这只是元胞自动机广阔应用背景的一个 方面到了8 0 年代中期，w o l f r a m 等人通过大量的计算机实验模拟元胞 自动机的动力学行为，并且采用了动力系统、代数、统计、混沌、非线性 等方法对元胞自动机进行了系统的研究，大部分结果都收集在他的论文 集f 1 1 1 中，这才掀起了人们对元胞自动机研究的热潮虽然前人对元胞自动 机已经做了大量的研究，但是至今还没有有效的数学方法，严格的数学结 觉胞自动机生成的时间序列的复杂性研究第一章元胞自动机简介 祭也不是稷多，本文黪主要目的就怒要搽索一种霹潋严格确定元麓富动 机复杂性程度的数学方法，主要工县是禁止字理论、计算机搜索和形式语 言理论，并在初等元胞自动机生成的时间序列研究中得到了较好的结果 1 2 元胞自动机的定义 首先介绍一维元胞自动机的定义，高维元胞自动机的定义可由一维 元缝自动竣i 鹚定义推广褥弼， 假设在条直线上按等间隔方式分布着一系列元胞姆一个元胞的 状态只有有限多个对于只有两个状态的情况，我们用符号0 和1 来表永 它粕 假设上述蛊线在两个方向上都没有限制，因此就有无限多个元胞所 有元胞的状态全体可以羽双侧无限的符号序列表示出来我们称每一个 这样的序列为元脆蹇动枧憋一令掬澎为了确定怒见，可以将努蠢在直线 上的元臆位鬣与整数全体对应趋寒特嗣是将与整数0 对藏静位置称冀 熬点如记构形为a ，则可以表示成 a 一( 8 2 a l a o a l a 2 ) ， 其中b o 是在基点的元胞状态，其余依次类推 每个元胞的状态看成是一个变麓，它只能取有限个值，即有限个状 态。于是上述蠢脆鑫动攒i 露是套无限多令变萋的蓉统。 假设时间也是离散化的用t 表示时间，它取整数值称t = 0 为扔 始时刻，它的下一时刻为t = 1 ， 赝有元藏熬状态是弱对发生交织戆。记在爵剡t 熬麴形炎，那么在 时瓤t + l 的构形n 蚌1 究全由决定同l l 重，在时刻t + 1 的第i 个元胞 的状态是由时刻t 的第i 个元胞以及相邻的距辩不超过r 的2 r 个元胞 嬲状态所决定的，用公式譬出来即是 o i t + 1 = ，( n i r ，8 ；一l ，嚷t ，a 。t + 1 ，n ：+ r ) 熊中的映射，与i 和t 都无关，我们称r 为邻域半径，称，为元胞自动 礁瓣晨黎姨瓣或爱蘸魏烈，霜时逸霹袭暴元戆自动提戆垒羯蠛鬟| 3 ， 2 托胞自动机生成的时间序列的凝杂性研究 第一章元胞自动机摘介 记凳有限状态袋宙、r 秘，藏完全确定了一个露戆童动撬， 是从知+ 1 映入的函数，同时也w 以看成是从e z 映入e 髫的函数 对一个构形作用次规则，就得到了一个新的构形设a o 为初始 橡影，扶迭代公式叠+ 1 一岁( ) 裁霹叛褥到歪拳鞔 毋 。 以下介绍结构最简单的初等元胞自动机 设e 一 o ，1 ) ，r 一1 ，这时局部映射为 瓤t + 1 = ，( 噬t l ，8 i t ，遽+ 1 ) 。( 1 1 ) 幽定义可知，初等元胞自动机的局部规则事实上飓如下映射： f ：3 _ 。 容易看出自变量只有2 3 8 种可能，只要给定了，对应于避八个自变凝 的值，就瞧一确定了。融此可见，只有2 5 6 种可能。设，盼规则为 1 1 1 _ a 7 ，1 1 0 _ a 6 ，1 0 1 - 弼，1 0 0 ”啦 0 1 1 _ a 3 ，0 1 0 _ 髓2 ，0 0 l _ a l ，0 0 0 。如 我们将二迸露l 羧a t a 6 a s a 4 a 4 a 3 a 2 a l a o 转纯为卡避潮数强戴隧，麝筏袭 的元胞自动机我们就称作礼号初等凭胞自动枫 1 。3 嚣艟自动飙魏分类阍戆 元胞自动机可以糟作是自然界许多复杂现象的离散亿的数学模裂 其在时间、空间和状态上都是离散的， 元魏鑫动辍俸秀一令离教诧戆簸杂系统謇提出后静一个蓄要豹理论 问题便是对它进行分类w o l f r a m 酋先对它作了详细的研究，它通过大麓 的计算机实验，按照在计算机上所观察到的动力学行为将所有元胞自动 穰| 分为班下勰类 ： w 1 ) 越子空间一个平稳构型； w 2 ) 越于一个或多个周期轨道； w 3 ) 产蹩渥沌麓扛溺期行袁； 3 元胞自动机生成的时间序列的复杂性研究 第一章元胞自动机简介 w 4 ) 生成许多复杂结构，某些会不规则地传播 大致来说，前三类相当于低维动力系统中常见的不动点，周期轨和混 沌，而第四类则被认为是可以与生命系统等复杂系统相比拟的自组织行 为这是第一次对元胞自动机进行分类，通过计算机模拟比较直观，但是 这种分类只是现象学分类，并不是严格的数学定义，而且对于同一个元胞 自动机来说，不同的初始构形有可能产生不同的动力学行为 在此之后，许多学者企图完善这种分类，他们根据元胞自动机不同的 性质作出了形形色色的分类 1 9 8 8 年，c u l i k 和y u 基于w o l f r a m 的分类，按照元胞自动机关于有 限构形的演化给出了一个有确切定义的分类他们将元胞自动机分成有 层次的四类，其中每一类都是后一类的子类【1 0 1 c y l ) 所有的有限构形都趋于一个静态构形； c y 2 1 所有的有限构形都是终极周期的； c y 3 ) 对任意有限构形a 和p ，能够判定是否能从有限构形a 演化 到p 的那些元胞自动机； c y 4 ) 所有元胞自动机 但已经证明了，前三类的m e m b e r s h i p 问题都是不可判定的 1 9 8 7 年，g i l m a n 按照等度连续性和弘一可扩张等性质将元胞自动机 分为以下三类【1 1 】： g 1 ) f 在某些点等度连续； g 2 ) ，在某些点。a z 是卢一等度连续，但所有点都不等度连续； g 3 1 为“一可扩张的 这个分类虽然有严格的数学定义，但这种分类依赖于某个特定的测 度，即对同一个元胞自动机，在不同的测度下可能属于不同的类别1 9 9 7 年k f i r k a 对此作了一些修改，他给出了元胞自动机的一个纯拓扑分类 1 2 ： k 1 ) ，等度连续( 即在所有的点都等度连续) ； k 2 ) f 在某些点等度连续，但，不等度连续： k 3 ) f 不是正向可扩的，但，对初值敏感； 4 元臆蠡动撬生成憋时阀j 葶到鹣复杂性磺褒第一章元魏爨动巍楚套 k 4 ) ，正向可扩+ 1 9 9 0 年，h u r l e y 研究了元胞自动机的吸引子和拟吸引子等性质，并 按照元憨鑫动撬吸萼l 予秘掇吸霉 子懿个数终凄了懿下分类 l 辣 h 1 ) 有两个不相交的吸引子，此时，有不可数多个拟吸引子； h 2 ) 有唯一的最小拟吸引子： 珏3 ) 毒礁一豹最夺啜零l 子c ，c 与甜f ，) 不司； h 4 ) 有唯一的吸弓i 子“( ，) a z ； h 5 ) a z 是唯一的吸引子 k f r k a 还放语富攀愆焦囊( 演纯语言) 黠元麓自动概遴行分类，豫将 元脆自动机分戒如下三类f 1 2 1 ： l 1 ) ，是有界周期的； l 2 ) ，是正规的但不是有赛髑期鲍； l 3 ) f 是菲正规酶。 以上的分类都很有意义，但对于给定的一个元胞自动机，如何去确定 它属予哪一类却很困难。嚣为这魑分类或是太粗，将有意义赡全放在一 起，或蔻缺少可行经麟究。 当然，还有其他分类1 9 9 0 举，g u t o w i t z 依据平均场的估计进行分类 1 ；1 9 9 7 年，c a t t a n e o 等人定义了所谓规则熵，对2 5 6 个初等元胞自动 撬迸行分黉【l 琵魏终2 0 0 2 年，c a t t a n e o 等入还获耘拎学静麓点对2 5 6 个初等式胞自动机进行了完整的分类 16 】男外的分类述可参考f 1 5 ，1 7 】) 高维元胞自动机的分搽问题可参考f 1 8 1 1 。4 元胞自动飙的极限语富和演化语裔 1 9 8 4 年，w o l f r a m 首先弓l 进形式语言与赶动机理论来对元胞自动机 送行研究融1 驮嚣野始了黯元戆自动瓿语塞复杂缝方蒸戆磷究，有关形 式语言与自动机理论的简介可参考附录a ，系统的介绍可参考【1 9 j 元胞自动机的极限集可以表示为 o o a n ，i ( e z ) i = 0 5 元胞自动机生成的时间序列的复杂性研究第一章元胞自动机简介 其中z 表示全体构形所组成的集合，又称为构形空间元胞自动机的极 限语言就是其极限集中的构形取有限长子串所组成的集合 l = z ix 是a 的有限长予串，并且a a 讨论元胞自动机的复杂性的多数工作是研究它们的极限语言的复杂 性如何对于元胞自动机生成的极限语言的复杂性作严格的分析一直是 一个非常困难的问题( 参看【2 ( ) ，2 1 ) 虽然在h u r d 的工作中举出了处于 c h o m s k y 层次中各个复杂性层次的元胞自动机的例子f 2 2 】，但是并没有提 供如何分析一个给定的元胞自动机的复杂性的理论方法这方面成功的 例子见【2 3 ，2 4 ，2 5 】，其中提出了斜演化、斜周期等新工具，证明了初等元 胞自动机中的2 2 号，9 4 号，1 2 2 号的极限语言都是非正规的，并且其中 1 2 2 号的极限语言还是非上下文无关的 以上讨论的对象都是元胞自动机的极限语言如果从映射的角度出 发，极限语言所反映的是元胞自动机的最大不变集的复杂性这种讨论有 其本身的合理性，但是也有明显的局限性首先它不能反映进入不变集之 前的过渡过程，其次对于满射的情况不能提供任何信息这样就需要从另 外一个方面来进行研究，对演化语言的研究就是一种方法 由于元胞自动机可以看成是复杂性系统的离散化( 粗粒化) 模型，将 其演化轨道糨粒化，可以用一个单侧无穷符号序列代表一条轨道 一个元胞自动机生成的时间序列是指8 ；0 g i 醇，n 0 ，也就是在位 点i 处的元胞的状态在元胞自动机演化时所构成的序列由于，与i 无 关，因此通常观察位点0 处就可以了应当指出，只用一个位点上的状态 代表构形，即是使用宽度为1 的观察窗口，这就是粗粒化方法在这儿一 个元胞自动机的所有时间序列所组成的语言我们称之为演化语言f 本文 中宽度为1 ) 为了研究演化语言，需要引进由，派生出来的另一个映射厂e 即演 化映射它的定义如下从串n = 0 0 一。n 3 血：出发，用，作用n 次， 得到符号串序列。生卅t 萌n 。t - f ) 1 t 礼，然后就有 ，8 ( n ) = f e ( a 0 一。n 8 n ：) = 0 0 0 0 6 n 称串n = 8 旦。- - 8 8 - o ：为a o a 6 o 器的- 厂8 原象 6 元腿囊动鞔生成静时阕缪嬲鳇复杂性研究第一牵元戆鑫秘搬楚奔 记e + 为在上的所有有限符号串全体所成的集合当然对予某些 z e 4 可能不存在，8 原象，而殷如果存在的话，这样的原象也不一定唯 称+ 的每个子集为上的个形式语言 本文中还需要作用于非空符号串上的个算子丌，7 r x ( x 7 f ) 就是去掉 鬈獒第一个f 最后一个) 笼号掰褥戆符号宰。 许多专家包括g i l m a n ，k f i r k a 和m a a s s 等人已经做了许多关予元胞 自动机演化语言复杂性方面的工作，并且得到许多有趣的结果f 1 1 ，1 2 事实上，j e n 也硬究过竞胞皇动撬静宽度1 盼演纯序列的嚣周羯性 2 罐。 本文主瑟就是壤形式语言来研究元胞耋动瓣潦纯语言的复杂性 g i l m a n 证明了如下命题1 ，相当于绘出了演化语言的一个上界 会题1 + 1 元脆囱动祝敢演他添言都是上下文有关语蠢。 予惩在c h o m s k y 酶语法艨次中，演化谮畜只有可能是如下三类： 正规语言，上下文无关语言和上下文有关语言 目麓对初等元腿自动机用形式语言麟究演佬诿赛鳇结果主要是 f 2 了，2 轧其中研究了1 8 号程2 2 号初等元魏自动辊的宽度大予等予2 的 时间演化复杂性，井证明前者为q e 上下文无关，而后者为非正规 本文主要是遥避禁止字的方法按照2 5 6 个袒等元臆是动瓿宽度1 酶 演纯语密静复杂程度进雩亍了分类，确定了部分元施基动祝演讫语富所楚 的c h o m s k y 层次，并且还得到了它们的严格数学表达式 7 元艟自动极生戏的时溺序列的复杂性研究 第二章时阚序列的复杂 生分耩 第三牵时褥疼列豹复杂性分析 2 1引言 扶凌力系统躲溅点出发，纛魏自凌撬霹鞋毳戒免类无穷维动力 系统。它的特点之楚用菲常简单盼映射黼则就可缝褥到极萁复杂的 时空模式可是迄今为止，对于露胞自动机的复杂性分类除了进行广泛 的计算机实验之钋 1 ，2 1 ，还缺少有效的数学方法，已经建囊的许多严 捂努类方法往往太褪，面虽摄戆用予藜平氏润惩鹃复杂性分辑，钢如觅 f 1 4 ，2 1 ，2 9 ，圳在【2 4 ，2 3 ，2 5 ，2 7 1 中采用了符号动力学的方法对于些 较为复杂的元胞自动机进行了复杂性分析，其中含有新的思想和方法，但 是在这些工俸中还必缝在确定它钠在c h o m s k y 静语言屡次率酶添法级 别，而没商能够给出簸杂性行为的全面搐述 本文将开发一种新的研究方法，这就是利用禁止字、计算机搜索和符 号动力学分辑对羼餐2 5 6 个初等嚣麓霆渗枫生残酶时淄廖残进孬浚纯复 杂性分类目前除了较复杂的一类之井的分析工作已经完成在下颡将 介绍分析的结果，并举例说明所用的方法 2 。2 禁止字 禁止字概念在有关形式语言戚符号串的文献中经常出现然黼对禁 止字酶遴论研究也霹魏是缦有用处鳇。为此诶蠹霹驻参考瞄( ，【3 1 ，1 5 乳 ，2 2 j 注意在本节中的符号集可以是任何菲空韵宵限集 禁止字概念与熟有以下性质的语言密切有关称语咨ec + 具有 因子性矮： 若符号串o e ，则z 的每个予串均属予e ( 2 ，1 ) 容易发现，在动力系统和某些其他领域中如现的语言往绽具有因子 生质 为方覆趣觅，我时总怒假定空率e 。 8 既鹣塞动疑生藏盼鞋赫蓐戮耱麓凝牲臻究鼙二章瓣魏黪i 豹复杂幢势耩 定义2 1 称j 寮符弩窜茹蹙语富露静一个禁止孛，舞巢。ge ，餐嚣 的每个冀子串都属于届， 注蛰谣言嚣爨裔缝囊2 ，1 ) ，鬟鬈警为e 鹣禁盎字瓣燕分盛要袭 警 是 xge ，德丌茹，茁硝se ( 2 , 2 ) 记凳谱言嚣在嚣4 孛麴替豢，又记蠡舻港要瓣掰搿禁立字眵 成 瓣集合，翳綮止字集歪矮有稳瀵 集中不存在慕个枣爨另一个率盼真子攀 ( 2 3 ) 潮霹予爨蠢嚣予壤矮瓣语富露容荔稽瓣 定璐2 1 e 一8 穷一4 一4 2 芦4f 2 鹳 试显然fc 麓+ 一麓+ 正嚣+ 任意串aee ，如柴a e + e ”+ ，则存 程a 麴一个子串a s e t ，露又囊予嚣具鸯辫予瞧震，a t e ，产生矛翳 蕊竣穆毯e 4 芝嚣”4 反之假设存在巢一串a 毯e 8 一鬈4 点，鬈8 ，憾是a e ，则定存在a 瓣个予警8 ，e ，聪此时靠g 冀+ e ”+ ，矛艚所以4 驴e “+ c 露+羽 对予舆脊因子憔朦的语言霖容荔得到e 7 一4 e , t 鬈8 ，并篮可敬建立 恳和之越的以下关系： e 盯一m t n 。r o 掰f 剪0 嚣( e 8 霆) ， 2 5 ) 蕤中m i n 舜髓置是如下定义的作用予语言五的算子f l9 】： m i n ( l ) 一p llx 戆簿个粪羲缀都不藩予三 ， r ( l ) 一协 将茹倒过来写成的符号串扩e 册 囊毙可凳，翔遴了滔言嚣夔骥蠢禁止字也裁簿予翔道了添蠢嚣本穷，纛 予e 戆蛰鬟显然笼慰予e 瓣莓馀褰l 蘑，翁e t 一8 e l e 4 ，因诧点岁缝 心 元胞自动机生成的时间序列鹤鬣杂性研究第= 章时间序列的篪杂性分析 往可能是对予e 的较为简单的麴舔一个简单的例子是有限补语言，邸 只有有限个禁止字的语言，由于点先有限集，从2 4 ) 可见有限枣 语誊 层必为正规语言 寒瑾2 2 懿袋d 满是性质f 2 3 ) ，羹l je = 嚣。一嚣4 d e 8 满足因子性 质，并且禁止字f ”= d 难首先v a e ，则age + d e 4 ，假设存在a 的一个真予串a 满足 a jge ，剽+ d ，辑墩8 冀4 d e + ，矛詹，赝默a 懿彳壬意真子串部 属于曰，故露满鼹因子性质 v a d ，珏ge ，并且幽予d 满慝性质( 2 3 ) ，d 的任意真子窜 a rg + d e 4 ，所以a t e ，由禁止字的定义霹知a e l f ，故d 冬磊 辫假设lage ”，agd ，则由a e ，可知age ，故a + d e + 又 由予辟崔d ，a 静任何冀子串都震予e ，刘a 髻麓4 d e + ( 如鬈a e 2 d e 4 ， 则必存在a 的某个真子串属予d ，不可能) 产生矛鹰。故e ”= d 职 例2 1 下面我们看个例子，取= 0 ，1 ) ，两个语言+ 1 1 ) 和 ( 0 l o ) + ( + 1 ) 都弯禁睦字集 l l ，瑟其中只鸯( 0 + l o ) s + 1 ) 瀵是鞠 子性质，并盥( 0 + 1 0 ) + ( e + 1 ) 一+ 一e + 1 1 4 。 通过禁止字来刻画元胞自渤祝生成酶时闻序列是本文的主要工具 2 3 计算机搜索 从这里开始总假设e = o ，1 ) 将由一个绘定的元胞自动机，生成 貔露澜序列全体撼必ec + ，我织将透过对予霆酶研究寒7 解，鳇演 化复杂性对于2 5 6 个初等元胞自动机，采用已经成为标准做法的规则米 区分它们f l j 如栗一个初等元胞自动梳的旒鄹弩为r ，燹| j 为清楚越见可将 ，积，e 分别记为鼻和努 显然e 具有因子性质( 2 1 ) ，因此可以从它的禁止字集会曰”来刻画 露 由于还不存在从一个绘定的语京求其禁止字的肖效方法，慝时对元 胞自动机来说很容易在计算机上作实验，因此可以编写用予寻找长度不 1 0 元胞自动机生成的时间序列的复杂性研究 第二章时间序列的复杂性分析 超过一定限制的所有禁止字的程序为此用v i s u a lc + + 语言编写的程序 对于2 5 6 个初等元胞自动机的禁止字作了全面的搜索 首先，利用共轭和对称关系，可以将需要讨论其演化复杂性的初等元 胞自动机的个数从2 5 6 个降低为8 8 个假设需要了解长度为k 的 时间序列由于初等元胞自动机的邻域半径为1 ，因此只需要研究长度为 2 k 一1 的初始串采取穷举初始串的所有可能性，并从长度2 开始，就可 以递归地得到长度k 的所有禁止字 根据k = 2 1 5 的搜索结果我们试将8 8 个初等元胞自动机分为4 类当然数值搜索有它的自身局限性，因此还需要作进一步的理论分析 下面的分类已经是实验结合理论分析后所得到的结果，但其中最后一类 ( 第1 v 类) 的理论分析还未完成 i 这一类中的初等元胞自动机的e 无禁止字，即其演化映射，8 为满 射这里又可以进一步分为两个子类： i 1 元胞自动机作为相空间s z 到自身的映射，也是满射，其中包 含1 0 个初等元胞自动机，它们的规则号为1 5 ，3 0 ，4 5 ，6 0 ，9 0 ， 1 0 5 ，1 0 6 ，1 5 0 ，1 5 4 ，1 7 0 i 2 映射，不是满射，其中包含4 个初等元胞自动机，它们的规则号 为9 4 ，1 2 2 ，1 2 6 ，1 8 4 i i 这是最大的一类，其中每个初等元胞自动机只存在有限多个禁止字， 即e 为有限补语言这一类包含5 3 个初等元胞自动机、它们的规则 号为0 ，1 ，2 ，3 ，4 ，5 ，6 ，8 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 8 ，1 9 ，2 3 ，2 4 ，2 9 ，3 2 ，3 4 ， 3 5 ，3 6 ，3 8 ，4 0 ，4 2 ，4 3 ，4 4 ，4 6 ，5 0 ，5 1 ，5 7 ，5 8 ，7 2 ，7 6 ，7 7 ，1 0 8 ，1 2 8 ，1 3 0 ， 1 3 2 ，1 3 6 ，1 3 8 ，1 4 0 ，1 4 2 ，1 4 6 ，1 5 2 ，1 6 0 ，1 6 2 ，1 6 8 ，1 7 2 ，1 7 8 ，2 0 0 ，2 0 4 ， 2 3 2 从实验和理论分析知道，这一类中的禁止字长度都不超过5 i i i 这一类中的每个初等元胞自动机有无限多个禁止字，e 为无限补正 规语言在这一类中包含8 个初等元胞自动机，它们的规则号为2 7 ， 2 8 ，3 3 ，7 8 ，1 0 4 ，1 3 4 ，1 5 6 ，1 6 4 元憝鸯动税生域兹时阕痒剃的复杂蛙磺完第二章l l 重翘序列豹复杂 生分辑 i v 这一类中的每个初等元胞自动机有无限多个禁止字，目可能魁非正 规语言这一类包含1 3 个锪等元胞自动机，它们的规则号为7 ，9 ， 2 2 ，2 5 ，2 6 ，3 7 ，4 l ，5 4 ，器8 ，6 2 ，怼，7 4 ，1 t 0 2 。4 第1 类：满射 这时产隽瀵射，这表臻昃鬃逶当选择裙始条箨，裁霹激实蠛任耩事 先指定的时间序列如前所述，我们将按照，为满射藏非满射而分成两 个子类米讨论 2 。4 1 子类i 1 在1 5 ，3 0 ，4 5 ，6 0 ，9 0 ，1 0 5 ，1 0 6 ，1 5 0 ，1 5 4 ，1 7 0 号初等元胞自动机中有 尼个在过去已有较多豹研究。对予9 0 号初等建胞自动撬宥经典昀代数研 究 3 巍号初等露施自动梳刘在m a t h e m a t i c a 中被用作伪睫辊数发生 器f 3 5 ，3 6 作为代表，在这里我l l 岁t e 塌为满射作出诚明对这个子类 中其他几个初等元臆自动机可以作类似的或鼹为簿单的讨论 定壤2 3 演亿浃射歹基为满瓣 证3 0 号初等元胞自动机的周部规则是 0 0 0 ，1 0 1 ，1 1 0 ，i i i _ o ；0 0 1 ，0 1 0 ，0 1 1 ，1 0 0 _ l 。( 2 6 它又可写为表达式 1 3 0 ( a 一1 ，a o ，a 1 ) 一。一1 + m a x ( a o ，a 1 ) ，( 2 7 ) 萁孛将符号a l ，秘，鑫l 看残为二遴麟鼗，为横2 热法。霹疆发蠛在给 定n o 和8 l 之后，矗。对于n 一1 怒1 - 1 映射这表明这个蒸本规则具宵左 满射性质 对予绘定黧惑阙序列豹长度嚣雳数学麴绡法。缓浚对予长度枣子 n 时结论已经成立，然后讨论长度为n 的情况设给定的时间序列为 o o o u 0 1 n 3 _ 1 0 子，则从i 网纳法假设知道存在穗0 0 “0 1 凸8 。的，8 一原象，记为 一l 罐- 8 1 一1 然焉任意取8 ：必0 或1 ，姨= 1 起，震局繁援囊 町 矬 。 甚 n o 地 端 0 烈 | i ot 件 穗 元胞自动机生成的时间序列的复杂性研究 第二章时间序列的复杂性分析 就可以逐个地确定o ：一”，o ? 一注意在( 2 8 ) 右边的自变量中前两个 是已经知道的然后从刚才得到的o ? _ 1 和给定的时间序列的最后两个符 号醯_ 1 和。子开始，并利用( 2 7 ) 的左满射性质，就可以逐个地确定。写1 ， ，o 旦。这样就得到所求的i e _ 原象 口 例2 2 用一个简单例子来解释上述证明设已知0 0 1 1 0 是时间序列 1 1 0 的一个蝠) 原象，要在此基础上求时间序列1 1 0 1 的塌一原象从下图 的两个分图可以看出，在f e ( 0 0 1 1 0 ) = 1 1 0 的演化基础上，对第一行右端 的符号分别取1 和0 ，然后按照箭头所示方向即可唯一地确定所有其他 符号其中l 用于标出位点0 的位置 上 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 注从以上证明还可以归纳地知道，长度为n 的时间序列恰好有2 n 一1 个，8 原象这和定理2 3 一起成为3 0 号初等元胞自动机能够作为随机 数发生器的理论基础 这一部分表明研究满射的时间序列并不能够反应满射规则的复杂性 这就需要我们研究更大宽度的演化语言才可能抓住某些满射复杂性的本 质值得注意的是在这一类初等元胞自动机中已经可以证明1 5 ，6 0 ，9 0 ， 1 0 5 ，1 5 0 ，1 7 0 号的任意宽度的演化语言都是正规的 2 4 2 子类1 2 这里只有4 个初等元胞自动机，编号是9 4 ，1 2 2 ，1 2 6 ，1 8 4 它们的尸 都是满射，但，都不是满射已知其中前两个具有非正规的极限语言 【2 4 ，2 斗对前3 个的证明依赖于它们都可以模拟9 0 号初等元胞自动机， 而后者的，8 为满射为此只需要用子串0 0 ，1 1 和时间演化步间隔2 即 可证明从略 但是1 8 4 号的处理要困难一点，下面给出它的证明 定理2 4 演化映射墙4 为满射 证只要对于每个茁证明存在丘，满足要求墙4 ( n ) = z 1 3 0 加吡 i十11 0 1 n o l 元胞自动机生成的时间序列的复杂性研究第二章时间序列的复杂性分析 由于时间序列形成的语言满足因予性质( 2 1 ) ， 串即可： x = 1 m 1 0 ”1 1 m 2 0 ”2 1 ”0 ” 其中的所有嘲，啦都是正整数 1 8 4 号的局部规则是 因此考虑以下类型的 0 0 0 ，0 0 1 ，0 1 0 ，1 1 0 _ o ；0 1 1 ，1 0 0 ，1 0 1 ，1 1 1 1 ( 2 9 ) 这时考虑如例( 2 2 ) 中所用的演化图是很方便的将( 2 9 ) 的符号串 z 从上到下放在位点0 的位置，在位点一1 处用时间序列 b = o “i 一1 0 ”1 ( 1 0 ”2 1 ) ( 1 0 一1 ) o ”k 又在位点1 处用时间序列 c = 1 ”l 一1 ( o l n l - 1 ) 1 ”2 ( 0 1 ”2 1 ) l m k ( 0 1 ”一1 ) ， 作类似的配置，然后用左( 右) 移位补足其他列，即表明用a = b r l c 就满 足，8 ( o ) = x 这里的关键在于当y 中不出现子串o o ( 1 1 ) 时，f ( y ) 相当 于左移( 右移) 口 例2 3 以上证明中的方法实际上很直观，举一个例子即可明白设 z = 1 3 0 3 1 3 0 3 ，就有b = 0 5 1 0 5 ，c = 1 2 0 1 5 0 1 2 ，使得，。( b r l c ) = x 其演化 图如下： 上 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 l 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 4 元胞自动机生成的时间序列的复杂性研究第二章时间序列的复杂性分析 2 5 第1 i 类：有限补正规情况 这里有5 3 个初等元胞自动机，占总数的5 3 8 s 6 0 一般来说，它 们的时空模式都是相当简单的这里仅有的例外是著名的1 8 号和1 4 6 号 初等元胞自动机，它们的时空模式较为复杂 在下面的表中列出这一类中所有5 3 个初等元胞自动机的全部禁止 字表2 1 中的结果是先用计算机搜索