论文部分内容阅读
从数学上看,细胞自动机(Cellular Automata,简称CA)是一种时间、空间和状态都离散的动力系统。研究表明,通过设计不同的局部映射,细胞自动机可以表现出复杂丰富的动力学行为。比如,初等细胞自动机规则110具有普适的计算功能,是目前发现的最简单的图灵系统。同样,在二维细胞自动机中,Conway发明的生命游戏(Game of Life)是最早的从分析角度被证明的一个具有普适计算功能的规则,其演化可以涌现出丰富的动力学现象,如滑翔机(Glider)、滑翔枪(Glider gun)、碰撞(Collision)、宇宙飞船(Spaceship)等。因此,细胞自动机可以用来模拟许多现实的动态系统,比如,交通、人口和生态模型等。本文主要在符号动力系统的观点下讨论一维的细胞自动机规则110和二维的细胞自动机规则B2/S7(Diffusion Rule)和B3/S23(Game of Life)的一些动力学性质。论文具体安排如下:第一章介绍了细胞自动机的发展简史、基础知识、经验分类以及本文的主要结构和内容。第二章讨论了初等细胞自动机110号规则滑翔机E3,由此找到了它的全局映射的一个不变子系统,讨论了在子系统上的动力学性质,刻画了它的复杂性。例如,拓扑传递、拓扑混合、正拓扑熵等,从而得到它们是Li-Yorke和Devaney意义下混沌的。第三章介绍了二维细胞自动机符号动力学的基础知识,用拓扑共轭的方法初步对二维Moore邻域OuterTotalistic细胞自动机规则进行了分类,并且通过滑翔机讨论了二维细胞自动机规则B2/S7(Diffusion Rule)和B3/S23(Game of Life)的符号动力学,得到了相应的结果。最后,第四章对全文作了总结与展望。