元胞自動(dòng)機(jī)生成的時(shí)間序列的復(fù)雜性研究.pdf

1、元胞自動(dòng)機(jī)是自然界許多復(fù)雜系統(tǒng)的理想化數(shù)學(xué)模型，它可以模擬許多自然現(xiàn)象與生命現(xiàn)象，大量未解決的問題為這個(gè)困難而有趣的領(lǐng)域展現(xiàn)了廣闊前景.　　自vonNeumann首次提出元胞自動(dòng)機(jī)的思想至今已有半個(gè)世紀(jì)，學(xué)者們對(duì)元胞自動(dòng)機(jī)進(jìn)行了大量研究，然而現(xiàn)在對(duì)元胞自動(dòng)機(jī)仍然缺少有效的數(shù)學(xué)方法，嚴(yán)格的數(shù)學(xué)結(jié)果也很少. 本文探求一種新的研究元胞自動(dòng)機(jī)的方法，使用禁止字理論、計(jì)算機(jī)搜索和符號(hào)動(dòng)力學(xué)的方法對(duì)于256個(gè)初等元胞自動(dòng)機(jī)生成的時(shí)間序列(

2、只觀察一個(gè)位點(diǎn)上的演化所得到的序列)進(jìn)行復(fù)雜性分析.借助時(shí)間序列所具有的特性通過研究它的禁止字來研究演化語言(本文所指的演化語言如無特別標(biāo)注都是指寬度為1的時(shí)間序列所組成的語言)，確定了大多數(shù)初等元胞自動(dòng)機(jī)生成的時(shí)間序列所處的Chomsky層次以及嚴(yán)格的數(shù)學(xué)表達(dá)式.　　在對(duì)初等元胞自動(dòng)機(jī)時(shí)間序列的禁止字分析之后，按照它們演化語言的復(fù)雜程度分為以下四類：第Ⅰ類為滿射，第Ⅱ類為有限補(bǔ)正規(guī)語言，第Ⅲ類為無限補(bǔ)正規(guī)語言，第Ⅳ類很有可能是非正規(guī)

3、語言.　　第Ⅰ類情況中的初等元胞自動(dòng)機(jī)沒有禁止字，其寬度1的演化語言為最大可能的正規(guī)語言，并且這一類中部分元胞自動(dòng)機(jī)的任意寬度演化語言都是正規(guī)的.　　第Ⅱ類情況中的初等元胞自動(dòng)機(jī)只有有限多個(gè)禁止字，因此其寬度1的演化語言為有限補(bǔ)正規(guī)語言.　　第Ⅲ類情況中的初等元胞自動(dòng)機(jī)有無限多個(gè)禁止字，但禁止字集是正規(guī)語言，經(jīng)過理論分析知道其演化語言為無限補(bǔ)正規(guī)語言.此類情況中一個(gè)代表性的例子是27號(hào)初等元胞自動(dòng)機(jī).　　第Ⅳ類情況中的初等元胞自