复杂Bernoulli移位细胞自动机的动力学研究

摘要

细胞自动机作为一种特殊的数学模型,其实质是一类时间、空间和状态都离散的动力学模型。二十世纪四、五十年代John von Neumann和Stanislaw Ulam在研究生命系统的自我复制现象时推断局部迭代简单动力系统有可能产生非常复杂的动力学现象,从此细胞自动机及其相关理论受到许多学者的潜心研究。其中包括细胞自动机复杂性的内在机理,在不同意义下的分类,以及与其他相关学科的联系等。二十世纪八十年代初,S.Wolfram针对细胞自动机具备规则简单性、局部互连性以及信息处理的高度并行性等优点,提出并号召人们研究结构最为简单的具有两个状态、邻域半径为一的基本细胞自动机(ECA)。在S.Wolfram针对256个基本细胞自动机模拟结果的基础上,L.O.Chua等结合细胞神经网络和非线性电路的研究成果对其进行了一系列非线性动力学的刻画。
　　 符号动力系统是研究细胞自动机的一个重要工具。根据不同的细胞自动机,设计其相关的局部规则,均可以诱导出双边无穷序列所组成的构型空间上相应的拓扑动力系统。借助计算机模拟将发现,细胞自动机呈现丰富的动力学行为。此外,细胞自动机也具有适合在超大规模集成器上实现的并行信息处理结构。1986年,C.Langton提出细胞自动机可以为信息传递、存储和修改等操作提供最基本的条件支持。另外,细胞自动机的一种特殊的时空周期演化结构一滑翔机,及其相关动力学性质也得到了广泛的关注。大量的理论研究成果为细胞自动机的应用领域奠定了基础,尤其是在自然现象模拟、密码学、复杂工业系统和并行计算等方面有广泛的应用。
　　 本文第二、三章以符号动力系统为主要工具,利用周期边界条件借助计算机进行模拟,在双边无穷符号序列空间中对复杂Bernoulli移位细胞自动机规则73的拓扑动力学和滑翔动力学行为进行了分析。第二章得到73号细胞自动机规则的8个具有Bernoulli移位性质的不变子系统及其相关决定系统,并给出这8个子系统之间的关系,最后通过分析全局映射f73在每个子系统上的动力学行为,证明其具有拓扑传递性,拓扑混合性,正拓扑熵等动力学性质。基于得到的不变子系统,第三章系统地研究了规则73中滑翔机、滑翔碰撞等滑翔动力学行为。借助De Bruijn图对滑翔机在不同以太背景下进行分类,并给出每一类的基本滑翔机及其相关的基本滑翔因子。同时发现,不同滑翔机之间相互组合之后会产生的多种不同的碰撞现象。结合分布式计算可以看到,ECA规则73的任意Bernoulli移位子系统提供了信息存储或者信息传递的基本条件,并且在特定的以太背景下可以设计速度不同的滑翔因子以实现信息的修改。
　　 一直以来,对细胞自动机进行更加完整和精确的分类是一项极具挑战又颇有意义的理论任务。诸多学者尝试从不同的角度进行讨论,但是由于受到许多条件的限制,分类结果缺乏一般性。最初,Wolfram通过大量的计算机实验将所有的细胞自动机分成四个大类。随后,L.O.Chua等通过三个几何变换,将所有的基本细胞自动机规则分成88个全局等价类。在L.O.Chua等对细胞自动机分类的基础之上,本文第四章针对其中3个全局等价类进行研究,通过构造相应的同胚映射将此3类细胞自动机与单边无穷符号序列空间上的移位映射建立拓扑共轭关系,进而将它们规结为同一类,记作PECA。此外,容易证明由这些具有特殊性质的规则诱导出的乘积动力系统与移位系统仍然保持等价关系,即二者具有等价的拓扑动力学性质,如正拓扑熵、拓扑混合、拓扑传递和拓扑正合等,从而是Devaney意义上和Li-Yorke意义上的混沌。
　　 文章最后对本文主要工作进行总结,根据研究中发现的问题与困难,提出对进一步研究的展望。