CA符号动力学理论及其应用研究

论文摘要

由John von Neumann于1951年正式提出的细胞自动机(Cellular Automata,简称CA)是时间、空间和状态均离散的动力系统,充当着复杂系统良好的模拟工具.近年来,越来越多的科研工作者投入到CA的理论和应用研究之中.而在理论方面中,关于CA的分类问题始终是研究的热点课题.迄今为止,从多种不同角度分类CA的工作已非常之多,不过大多还是建立在预先给定的一些限制条件下,因此不具有一般性.本文从符号动力学角度出发,核心工作为讨论拓展情形下即由无穷个细胞组成的无边界条件限制的CA的全局等价分类问题,此外,其它主要工作还包括基本细胞自动机(Elementary Cellular Automta,简称ECA)的细胞神经网络(Cellular Neural Networks,简称CNN)实现及加性ECA规则的全局演化性质.具体来说,论文主要工作内容如下:1.我们找出了两个由五个变量不同邻域组成的CNN基因(对应的输入输出布尔函数是线性可分的)成功实现了指纹特征图象中的端点和分支点的提取.这里值得一提的是,实际应用中的CNN基因对应的输入输出布尔函数必须是线性可分的.因此,对于由线性可分和线性不可分组成的ECA规则,我们分两步执行,第一步,直接用CNN基因实现线性可分的ECA规则.第二步,将线性不可分的ECA规则最优分解成线性可分的ECA规则的逻辑运算组合形式,再利用第一步的CNN基因实现.这样,所有的ECA规则都可以由CNN实现,某种程度上体现了ECA在CNN中的应用.2.从符号动力学角度出发对由双边无穷个细胞组成的ECA进行了拓扑共轭分类.分类结果表明,由有限个细胞组成的周期边界条件下的ECA在拓展成双边无穷情形下的全局等价分类保持不变.进一步,我们发现用分类一般情形下的ECA的两个同胚映射同样适合分类一维半径为2的CA,加性规则的分类验证了这一点.在一维基础上,我们又对高维的一般情形下的CA给出了理论上拓扑共轭分类所需的同胚映射.特别地,利用这个平台,我们反过来寻找出了著名的生命游戏所对应的对偶规则.3.源于Wolfram的在2002年出版的一类新科学(A New Kind of Science)一书中许多的模拟实验和经验观察结果,我们先回顾了从2002年到2007年Chua等人的系列论文的主要工作,而后讨论了ECA规则的Isle of Eden性质,简洁地证明了两个代表性加性ECA规则的一些全局演化性质.

论文目录

• 摘要
• ABSTRACT（英文摘要）
• 第一章 绪论
• 1.1 CA 的背景及意义
• 1.1.1 CA 模型
• 1.1.2 CA 数学定义
• 1.1.3 CA 的应用
• 1.2 CA 研究现状
• 1.3 本文的工作
• 第二章 ECA 的CNN 实现
• 2.1 CNN 简介
• 2.1.1 CNN 定义
• 2.1.2 标准的CNN 模型
• 2.1.3 CNN 应用于指纹识别
• 2.2 ECA 简介
• 2.2.1 基本概念
• 2.2.2 ECA 的布尔立方体表示及最优分解
• 2.3 ECA 的CNN 实现
• 第三章 CA 的全局等价分类
• 3.1 引言
• 3.2 ECA 拓扑共轭分类
• 3.2.1 ECA 局部规则映射的建立
• 3.2.2 ECA 局部规则映射的分类
• 3.3 一维半径为2 的CA 的等价分类
• 3.3.1 加性规则的分类及验证
• 3.3.2 T20 和T52 全局等价规则探索
• 3.4 高维CA 全局等价分类
• 3.4.1 二维CA 的等价分类
• 3.4.2 生命游戏的对偶规则
• 第四章 ECA 的非线性动力学行为
• 4.1 相关背景及基本概念
• 4.1.1 Wolfram 的一类新科学
• 4.1.2 对Wolfram 的一类新科学的非线性动力学展望
• 4.2 Isle of Eden
• 4.3 加性ECA 规则全局演化公式
• 4.4 加性ECA 规则演化性质
• 第五章 总结与展望
• 5.1 本文总结
• 5.2 研究展望
• 参考文献
• 附录A ECA 局部规则映射的表示
• 附录B ECA 局部规则映射的拓扑共轭分类
• 附录C 线性不可分ECA 规则的最优异或分解
• 附录D 线性可分ECA 规则的CNN 实现基因
• 附录E ECA 规则演化基树图独立连通分支个数
• 作者在攻读博士学位期间的学术论文
• 致谢