【作者】 管俊彪；

【导师】 傅新楚；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2009， 博士

【摘要】 由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】 Cellular automata (CA for short), formally introduced by John von Neumann in1951, are discrete (both in time, space and state) dynamical systems which serve asgood simulation tools for modeling many complex systems. In recent decades, moreand more researchers focus their attention on studying the theoretical and applied as-pects of CA. While in the field of theoretical research, the classification of CA is alwaysa hot topic, and heretofore many classification schemes have been presented from dif-ferent points of view. However, among them, the majority suffers the loss of generalitydue to many restricted conditions given under assumption. In this thesis, from the pointof view of symbolic dynamics, we investigate the extended CA which are composedof infinite number of cells without the restriction of boundary conditions, and the corework is to discuss the global equivalence classification. Moreover, other works includethe Cellular Neural Networks (CNN for short) realizations of Elementary Cellular Au-tomata (ECA for short) and global evolutionary properties of some additive ECA rules.More specifically, the main contents of this thesis are as follows:1. We find, in this thesis, two CNN genes (corresponding input-output Booleanfunctions are linearly separable) composed of five variables with two kinds ofneighborhoods to successfully extract the endings and bifurcation points in theprintfeature image. Noteworthy, the input-output Boolean function correspond-ing the CNN gene in practice should be linearly separable. In terms of ECAcomposed of both linear separable and linear non-separable rules, we thereforeoperate by two steps. First step, we directly implement linear separable ECArules via CNN genes, and second step, we optimally decompose the linear non-separable ECA rules into the logic operation combinations of linear separableECA rules, then utilize the CNN genes obtained in the first step to implementthem. In this sense we implement all ECA rules, which to some extent re?ectsthe ECA application in CNN.2. We present a topological conjugacy classification of ECA composed of bi-infinitenumber of cells from the point of view of symbolic dynamics, and the classifica-tion result coincides with that of ECA composed of finite number of cells withperiodic boundary conditions. Furthermore, we find that the two homeomor-phisms which are utilized to classify ECA in the extended case can also be usedto group one-dimensional CA with radius 2. The classification of additive rules validates the result. On the foundation of one-dimensional cases, we also pro-vide theoretically the homeomorphisms that classify high-dimensional CA in anextended case. Particularly, we find the dual rule of the famous game of life rulebasing on this platform.3. In light of many results obtained by Wolfram through large amount of computersimulations and empirical observations in A New Kind of Science published in2002, we firstly recap the main results in paper series conducted by Chua et alfrom 2002 to 2007, then we investigate some properties of Isle of Eden possessedby some ECA rules. We also give a simple proof of some global evolutionaryproperties of two representative additive ECA rules.更多还原