7号初等元胞自动机生成的时间序列的复杂性分析

元胞自动机

第3期华东师范大学学报(自然科学版)

No.3 文章编号:1000 5641(2008)03 0075 08

7号初等元胞自动机生成的时间

序列的复杂性分析

秦大康, 江志松

1

2

(1.南通大学理学院,江苏南通 226007;2.华东理工大学数学系,上海 200237)摘要:使用禁止字理论、计算机搜索和符号动力学的方法对7号初等元胞自动机生成的时间序列从形式语言的角度进行复杂性分析,确定了禁止字集及其Chomsky层次,确定了演化语言的一个精简的Chomsky层次,并由此得到了时间序列的完整描述.

关键词:初等元胞自动机; 时间序列; 禁止字; 形式语言; Chomsky层次中图分类号:O231.5 文献标识码:A

Complexityanalysisoftimeseriesgeneratedby

elementarycellularautomatonofRule7

QINDa kang1,JIANGZhi song2

(1.SchoolofScience,NantongUniversity,NantongJiangsu226007,China;2.DepartmentofMathematics,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

Abstract: Usingthetoolsofdistinctexcludedblocks,computationalsearchandsymbolicdynamics,thecomplexityofthetimesseriesgeneratedbyelementarycellularautomatonofRule7wasanalyzed,thesetofdistinctexcludedblocksanditsChomskyhierarchyandtheChomskyhierarchyofareductionoftheevolutionlanguageweredetermined.Finally,themathematicalstructureunderlyingthetimese rieswasobtained.

Keywords: elementarycellularautomaton;timeseries;distinctexcludedblock;formallan guage;Chomskyhierarchy

0 引 言

元胞自动机最早是由vonNeumann提出来的,用于模拟生命系统所具有的自复制功能.元胞自动机可以看成是一个离散的动力系统,它的特点是具有非常简单的结构但是却能够产生极其复杂的行为.初等元胞自动机是元胞自动机中最简单的,即一维的邻域半径为1的元胞自动机,总共有256种,其中有一部分规则就已经能够产生相当复杂的行为.迄今为

收稿日期:2007 09

基金项目:南通大学引进人才科研启动基金

第一作者:秦大康,男,博士,讲师,研究方向为非线性复杂性.E mail:qindk@http://doc.guandang.net.

元胞自动机

76

华东师范大学学报(自然科学版)

[1,2]

2008年

止,对于元胞自动机的研究除了进行大量的计算机实验之外,还缺少有效的数学方法,已建立的许多复杂性的分类方法往往不太严格,很难应用于非平凡问题的复杂性研究[3 6].目前对初等元胞自动机语法复杂性的研究通常有两个方向,一是通过研究初等元胞自动机极限语言所处的Chomsky语言层次来确定其复杂性,二是通过研究初等元胞自动机演化语言所处的Chomsky语言层次来确定其复杂性[11 13].

文献[13]中已经对初等元胞自动机宽度为1的演化语言进行了系统的研究.初等元胞自动机中7,9,22,25,26,37,41,54,56,62,73,74,110号被暂归为第IV类.其中仅有56号初等元胞自动机的演化语言的结构被完全确定.7号初等元胞自动机的演化语言只能推断为非正规[13],并且还没能给出其演化语言在数学上的严格描述.本文首先通过计算机搜索的结果猜测其演化语言的禁止字的结构,再通过禁止字理论和有限自动机等方法严格确定其禁止字,从而给出其演化语言和禁止字集在数学上的严格描述.

[12]

[7 10]

1 记号与定义

首先给出初等元胞自动机的定义.假设在一条直线上按等间隔方式分布着一系列元胞,每个元胞的状态取自集合 ={0,1}.由于直线在两个方向上都没有限制,直线上所有元胞的状态可以由一个双侧无限的符号序列表示出来,称这样的序列为元胞自动机的一个构形.构形a可以表示为a= a-2a-1a0a1a2 ,对任意的i,ai! .在此,f同时表示元胞自动机的全局映射及其局部规则.记a为时刻t时的构形,ai是位点i处的元胞在时刻t的状态,则初等元胞自动机的局部规则必须满足

1at+i=f(ati-1,ati,ati+1).t

t

(1)

也就是说构形at+1位置i处的状态只与构形at位置i-1,i,i+1三处的状态有关(称半径为1),对一个构形作用一次规则,f就得到了一个新的构形.设a为初始构形,从迭代公式

at+1=f(at)就得到正半轨{at}t 0.

1n

一个元胞自动机生成的时间序列是指a0iai ai,n 0,也就是在位点i处的元胞的状

态在自动机演化时所构成的序列.由于f与i无关,因此通常观察位点0处就可以了.应当指出,只用一个位点上的状态代表构形,即是使用宽度为1的观察窗口,这就是粗粒化方法.在此一个元胞自动机的所有时间序列所组成的语言称之为演化语言(本文中宽度为1).

为了研究演化语言,需要引进由f派生出来的另一个映射fe,即演化映射.它的定义如下.从串a=a-n a0 an出发,用f作用n次,得到符号串序列a-n+t a0 an-t,1#t#n,然后就有

01n

fe(a)=fe(a0-n a00 a0n)=a0a0 a0.

01e

称串a=a0-n a00 a0n为a0a0 an0的f原象.

t

t

t

记 *为在 上的所有有限符号串全体所成的集合.当然对于某些x! f原象,而且如果存在的话,这样的原象也不一定唯一.称 式语言.

e

*

*

可能不存在

的每个子集为 上的一个形

为了研究方便,Wolfram利用0-255的二进制数对初等元胞自动机进行了编号,如7号初等元胞自动机,即将规则号7化为八位的二进制数00000111,则7号初等元胞自动机的局部规则f即为f(111)=0,f(110)=0,f(101)=0,f(100)=0,f(011)=0,f(010)=1,f(1(

元胞自动机

本文还需要作用于非空符号串上的一个算子 , x(x )就是去掉x的第一个(最后一个)符号所得的符号串.

2 禁止字

禁止字概念在有关形式语言或符号串的文献中经常出现.因而对禁止字的研究可能是很有用处的.读者可以参考文献[14-16].注意在本节中的符号集 可以是任何非空的有限集.禁止字概念与具有以下性质的语言密切有关.称语言E *具有因子性质:

若符号串x!E,则x的每个子串均属于E,且x同时也为E中某串的真子串.时总是假定空串 !E.

定义2.1 称非空符号串x是语言E的一个禁止字,如果x

都属于E.

注 若语言E具有性质(2),则x为E的禁止字的充分必要条件是

x

记E 为语言E在 性质

集中不存在某个串是另一个串的真子串.

则对于具有因子性质的语言E容易得到

定理2.1

[11]

*

(2)

容易发现,在动力系统和某些其他领域中出现的语言往往具有因子性质.为方便起见,此

E,但x的每个真子串

E,但 x,x !E.(3)

中的补集,又记E%为E的所有禁止字所成的集合,则禁止字集E%具有

(4)

E=

字集E%=D.

*

-E =

*

-

*

E%

*

.(5)

定理2.2[11] 如果D满足性质(4),则E= *- *D *满足因子性质,并且其禁止

所以如果语言E满足因子性质,那么知道了E的所有禁止字也就等于知道了语言E本身.由于E的补E 显然是对于E的等价刻画,而E = *E% *,因此E%往往可能是对于E的较为简单的刻画.一个简单的例子是有限补语言,即只有有限个禁止字的语言.由于E%为有限集,从(5)式可见有限补语言E必为正规语言.

当E%为有限集或正规语言时,给定了E%后求E的具体方法如下.(1)画出接受 *E% *的有限自动 …… 此处隐藏：12099字，全部文档内容请下载后查看。喜欢就下载吧 ……