1. 引言
元胞自动机(Cellular Automata,以下简称CA)是为模拟包括自组织结构在内的复杂现象提供的一个强有力的方法,也称为细胞自动机。据文献 [1],J. Von Neumann为早期CA的发展做出了很大的贡献,但是他的这个思想来源于Stanislaw Ulam。其目标是设计一个具有通用图灵机那样自我繁殖的人工系统可计算的模型。Stanislaw Ulam给出建议后,J. Von Neumann采用2维元胞空间即CA结构,使用具有29个状态的2维元胞自动机(以下简称2D-CA)建立一个具有通用计算能力和自我复制特性的CA模型。后来Codd [2] 对2D-CA进行简化,使用具有8个状态的2D-CA建立了CA模型。但是,需要庞大数量的元胞单元才能实现这些CA模型,因此难以完成物理实现 [3]。后来,由A. W. Burks [1] 完成和扩展了J. Von Neumann的研究,完成了物理实现。20世纪80年代初,S. Wolfram [4] 提出对CA进行简化,简化后的CA不仅具有复杂的动力学的特征,而且还具有能够适合VLSI层次的简单规则结构,信息并行处理的局部互联结构。S. Wolfram对CA的简化极大的推动了CA理论和应用研究的发展。现在CA模型在各个领域的应用和研究都比较广泛。
查阅文献可以发现对于一维CA模型而言,大部分都是将CA模型应用到其它的领域,而没有对一维CA模型进行深入探讨,求其精确解。所以本文主要是研究一维CA模型,求出一维CA模型的精确解,将结论应用到生灭循环系统中。因为一维CA模型对于一般人而言理解起来比较抽象,生灭循环系统对于一般人而言理解起来就比较具体,更直观,所以可以用生灭循环系统来分析一维CA模型中的相互作用的过程,将一维CA模型的结论应用到生灭循环系统中可以更好理解一维CA模型,以至于可以将该模型更好的应用到其它的领域。
在第2部分先给出CA的一般定义,再由一般定义给出一维CA模型的定义,再此定义的基础上给出一维CA模型的关联函数,第3部分是对一维CA模型的关联函数求精确解,得出结论,第4部分将结论应用到生灭循环系统中。
2. 概念及其模型
元胞自动机CA也称为细胞自动机,格点自动机,分子自动机或单元自动机,CA是定义在一个具有离散,有限状态的元胞组成的元胞空间上,并按照一定的局部规则,在离散的时间维上演化的动力学系统。CA是一种局部互联的网格结构,每个元胞只跟它的邻居元胞有联系。散布在网格中的每个元胞都取有限的状态,根据局部规则并行地更新到下一个状态。
2.1. CA严格的定义如下 [5] [6] [7]
1) 形状大小一致的元胞网格覆盖n维空间的一部分;
2) 各个元胞在时刻
对应的局部状态值由其归属网格r的一组布尔变量
决定;
3) 各元胞状态值按以下演化规则
在离散的时间域中同步更新:
(2.1)
其中
是元胞归属网格r的指定邻居单元。
CA可以用如下的四元组来表示 [8]:
其中:
1) 元胞空间
:元胞空间指的是单元自动机中的元胞能够按照一定的几何结构组成的集合。
2) 元胞状态空间
:元胞自动机中的每一个元胞都是等价的,它们都是在相同的状态空间
中取值。
3) 局部演化规则f:CA是一种状态和时间都离散的动力系统,在不同时刻,元胞状态的转变是由元胞的演化规则f来确定的。
4) 边界条件b:根据元胞的数量CA可以分为有限CA和无限CA。边界条件决定了当元胞处于边界的时候邻居元胞超出CA的空间结构时的处理方法。
元胞又可称之为单元,细胞或者基元,是CA中最基本的组成部分。元胞分布在一维欧几里得空间的晶格点上。具有以下几个特点 [9]:
1) 元胞是CA最基本的单元。
2) 元胞具有记忆贮存状态的能力。
3) 所有的元胞状态都能够按照基元规则进行不断的更新。
周期型边界条件指的是相对边界进行连接起来的元胞空间,在一维空间中的表现是首尾相接的圆。
2.2. 一维CA模型
1) 一维元胞空间A:
是由1维元胞单元构成的空间结构。其中
为模
的整数集,
表示第i个元胞的向量坐标,
为元胞单元的1维空间地址索引值。
2) 元胞状态空间
:CA中元胞单元
的状态取值范围。在此一维CA模型下元胞的状态是向上或者向下,对应的元胞位置的变量取值为 +1或 −1。一般为具有n个元素的有限状态交换环
,状态赋值函数
确定了t时刻CA中第i个元胞单元与状态空间Zn之间的映射关系:
(2.2)
其中N为自然数。
3) 局部演化规则
:称由CA的领域半径
确定的第i个元胞单元的O阶领域状态配置:
其中
表示由原点到点
的距离,
表示由原点到点
的有向线段。
具有O个元胞的有限状态交换环。
,其中
是
的
邻域。与其演化状态
之间的映射:
为CA的领域函数规
。CA的领域半径由
确定的领域,其中k为常数且
。
4) 边界条件b:边界条件确定某个元胞单元
领域半径
之内的领域单元在超出CA空间结构时的处理方法。对于一维CA而言,每一个元胞上的变量只有两个近邻。因此在这里将采用周期型边界条件。
定义一维CA模型的关联函数,在一维元胞空间中,设有n个格点,处于每个元胞位置上,每个变量只能取 +1或 −1,并且只考虑近邻格点之间的相互作用,这样的格点系统称为一维CA模型,称C为一维元胞自动机模型的关联函数,则
(2.3)
其中
代表第i个元胞位置的变量,
取值为 +1或 −1,可以解释为对应于格点上元胞的向上或者向下或者元胞的生与死。
表示对一切可能的邻近对
的求和,J表示第i个元胞与第j个元胞的关联系
数常数。这里令
,表示每个元胞上的格点的特征都是相同的,当
时,元胞上的格点的特征不相同,使得格点趋于相反方向,因此,在这里只讨论
的情况。在一维CA模型的关联函数中只讨论相邻的元胞,所以它们的关联系数是相同的常数,则可以把关联系数J提到求和符号之前。则得
(2.4)
是与格点相应的使元胞能够进行相互作用的一种性质。B表示传递元胞间相互作用的动力。在此动力下的相互作用可以使得元胞的状态方向相同(向上或者向下)。
3. 一维CA模型的精确解
一维元胞自动机模型的关联函数为:
(3.1)
在边界条件中已知在一维CA模型中采用周期型边界条件,因此令:
(3.2)
想象将一维元胞看成一个环。
根据(3.2)式可将(3.1)式写为
(3.3)
相应的配分函数为
其中
表示对一切可能的格点状态
的求和。T表示元胞能量,
是一个常数,
表示每个元胞的能量为1,099,440焦耳。
引入矩阵P,其矩阵P的元定义为:
(3.4)
需要注意
可以取 ±1两个态,所以P是
矩阵
(3.5)
其中k表示一个元胞能量,元胞的能量k来源于ATP (三磷酸腺苷)。于是,配分函数可写为
(3.6)
将矩阵P进行对角化,得
(3.7)
是矩阵P的本征值,由久期方程
(3.8)
定之。解为
(3.9)
在这里将注意到
。将(3.7)式代入(3.6)式则有
(3.10)
因此
(3.11)
即配分函数是由矩阵P中较大的那个本征值所决定的。F表示格点系统可以对外界提供的有用的能量,M表示的是所有元胞的状态是馄饨的到所有元胞的状态是相同的性质的强度,F和M分别为
(3.13)
(3.14)
结论:在元胞能量T不同的情况下,M随着B变化的关系可以看出,对于一切
(即外界对元胞所提供的能量大于元胞所耗损的能量)的时候都有
。这表明在一维的情况下,CA模型不能够通过近邻格点间的相互通信使得各元胞之间的轨迹在一定空间范围内能够呈现出有序排列而获得能够被相互作用的性质,所以无论元胞的能量是多少,格点的平均取向是由两个对抗的因素相互竞争而决定的,即能量倾向于取极小,而熵倾向于取极大,对于一维CA模型情况来讲,由于近邻数比较低,使得格点排在相同方向的倾向不足以抗衡使得熵极大的倾向。
4. 在生灭循环系统中的应用
生灭循环系统过程的定义:在生灭循环系统中,主要的研究对象是系统内部状态的变化,或者是建立状态概率的过程,生灭循环系统来源于生物病菌学,一堆细菌,一个细菌在
时间内分裂成两个细菌的概率为
,死亡的概率为
,因为细菌是离散的,独立的,因此在任何时间内,各个细菌分裂或死亡的过程是相互独立的,如果细菌的分裂和死亡能够看成是概率学中的一个事件,则在
时间内发生2个及以上的分裂和死亡的概率为
时,像这样系统状态随着时间变化的过程称为生灭过程 [10] [11]。
生灭过程是一种特殊的离散状态的连续时间马尔可夫过程。生灭过程的特殊性在于状态为有限个或可数个,并且系统的状态变化一定是在相邻的状态之间进行的。
生灭循环系统过程由生物细菌学运用到CA模型的过程如下:设有n个格点,在任意一个时刻t格点系统所处的状态为
(对应于CA模型中的相互作用的过程中格点系统所处的状态),格点系统的状态Z会随着时间t的改变而相应的改变,只要这个过程能够满足以下几个条件,则可以称之为生灭循环系统过程。
1) 在
时间内,在
时间内第i个元胞向右进行一次相互作用的概率为
,即状态赋值规则由
到
,相对应的格点系统的状态空间由
变化到
,其中
为一个固定的常数,元胞向右相互作用表示分裂。
2) 在
时间内,在
时间内第i个元胞向右进行一次相互作用的概率为
,即状态赋值规则由
到
,相对应的格点系统的状态空间由
变化到
,其中
为一个固定的常数,元胞向左相互作用表示死亡。
3) 在
时间内,格点系统状态的改变在2次以上的概率
,即有2次以上的元胞向左或
向右相互作用的可能性是
。
表示在时间
内元胞发生相互作用的次数
表示在时间
内元胞第
次相互作用的可能性。
从生灭系统的定义可知,对于一个一维CA模型中的相互作用的过程而言,只要元胞能够向左或者向右相互作用,那么一维CA模型中的相互作用的过程可以用生灭循环系统来分析。在这里我们只研究元胞向左或向右相互作用的过程,对于元胞向左或向右相互作用发生的概率不做研究。
其中
代表第i个细菌位置的变量,
取值为 +1或 −1,可以解释为对应于格点上细菌的状态是分
裂或死亡。
表示对一切可能的邻近对
的求和,J表示第i个细菌与第j个细菌的关联系数。这里
令
,表示每个细菌上的格点的特征都是相同的。
是与格点相应的使细菌能够进行相互作用的一种性质。B表示细菌相互作用的动力。在此相互作用下可以使得细菌的状态相同(分裂或者死亡)。
元胞能量T在这里指的是温度,研究温度T不同的情况下,所有细菌的状态是馄饨的到所有细菌的状态是相同的性质的强度M随着格点系统可以对外界提供的有用的能量B变化的关系可以看出,对于一切
的时候都有
。因为细菌的分裂和死亡除了跟自身的周期有关,还跟外界环境有关系,例如以上提到的温度T,当达到细菌适应的温度,细菌是以滋养体形式存在,可以活跃的繁殖。当温度不适宜细菌生存时,细菌会停止代谢活动,不再繁殖,甚至死亡。所有的细菌是离散的,独立的个体,细菌的分裂和死亡不受相邻细菌的分裂或死亡所影响,所以一维CA模型不能够通过近邻格点间的相互作用使得各细菌之间的状态在一定空间范围内能够呈现出有序排列而获得能够被相互作用的性质,所以无论外界温度是多少,格点的平均取向是由两个对抗的因素相互竞争而决定的,即能量倾向于取极小,而熵倾向于取极大,对于一维CA模型情况来讲,由于近邻数比较低,使得格点排在相同状态的倾向不足以抗衡使得熵极大的倾向。
设计元胞自动机的目标就是设计一个具有通用图灵机那样自我复制的人工系统可计算的模型。图灵机程序是固定的,通用图灵机可以改变程序,在生灭循环系统中元胞向左或者向右的相互作用表示了元胞的死亡和分裂,而当元胞向左相互作用后,就表示该元胞的状态处于死亡状态,则此时的元胞不能再发生互相作用,当元胞处于分裂状态时,元胞的数量会增多,但格点的数量始终为n个;如果在元胞相互作用的过程中出现局部有相同的作用过程,那么这个局部相同的作用过程可以进行自我复制,一直复制到元胞的相互作用发生改变为止,因为元胞的向左或者向右相互作用的过程中,外界环境的不同会导致元胞相互作用的周期会有所改变,导致相同过程的相互作用会有所改变。这个过程就是在一维元胞自动机模型在相互作用的过程中生成了很多子一维元胞自动机模型进行相互作用。子一维元胞自动机模型真包含于一维元胞自动机模型,与一维元胞自动机模型局部有着相同的相互作用。
5. 总结
本文主要研究一维CA模型,求一维CA模型的精确解,将一维CA模型相互作用的过程及结论应用到生灭循环系统中。但是只研究一维CA模型还是远远不够的,还有二维甚至多维CA模型需要去研究以及求其精确解,因此接下来的主要任务是在此一维CA模型的基础上研究二维CA模型,求出二维CA模型的精确解,将二维CA模型相互作用的过程及其结论加以应用。
致谢
感谢伊犁师范大学为我提供一个很好的学习环境,对我学习和生活提供了很大的支持,遇到什么困难学校都能够帮助我解决。感谢我的同学,学姐学长以及学弟学妹们在学习和生活中对我的帮助和包容,感谢他们在我最困难的时候给与我最大的鼓励和支持。感谢我的父母,对我学业的肯定,为我能够顺利毕业提供了很大的帮助,不辞辛苦将我抚养长大,让我能够接受高等教育,提高自身的修养。同时也要感谢贵出版社录用我的论文,这是对我的成果给予最大的肯定。
基金项目
新疆维吾尔自治区高校科研计划自然科学重点项目(XJEDU2019I024)。
NOTES
*第一作者。
#通讯作者。