關(guān)于二維170規(guī)則元胞自動(dòng)機(jī)的研究.pdf

1、元胞自動(dòng)機(jī)（cellular automata,簡(jiǎn)稱(chēng)CA）是一類(lèi)特殊的無(wú)輸出有限自動(dòng)機(jī)，它是由規(guī)則排列的元胞組成的離散動(dòng)力系統(tǒng)，任一個(gè)元胞都可被賦值。近年來(lái)，元胞自動(dòng)機(jī)在生物學(xué)、物理學(xué)、密碼學(xué)等方面都得到了廣泛的應(yīng)用，具有非常強(qiáng)的研究?jī)r(jià)值。許多國(guó)內(nèi)外學(xué)者借助不同的工具對(duì)其進(jìn)行了研究，其中代數(shù)工具是當(dāng)中重要的一個(gè)分支。 本文簡(jiǎn)單介紹了元胞自動(dòng)機(jī)的起源、發(fā)展過(guò)程、研究方向等基礎(chǔ)知識(shí)，并對(duì)幾類(lèi)二維170規(guī)則元胞自動(dòng)機(jī)進(jìn)行了討論，用矩陣

2、方法研究它們的一些特性。 本文內(nèi)容分為四部分，每個(gè)部分為一章。 第一章是引言.這部分簡(jiǎn)單介紹了元胞自動(dòng)機(jī)的基礎(chǔ)知識(shí)，以及國(guó)內(nèi)外學(xué)者利用代數(shù)工具對(duì)元胞自動(dòng)機(jī)進(jìn)行研究的一些內(nèi)容，并給出元胞自動(dòng)機(jī)的基本概念和記號(hào)。 第二章是關(guān)于零邊界條件下170規(guī)則（簡(jiǎn)稱(chēng)170N規(guī)則）元胞自動(dòng)機(jī)的研究.這部分利用矩陣的方法對(duì)二維170N規(guī)則CA的GOE進(jìn)行討論，得到一個(gè)求它的GOE個(gè)數(shù)的步驟，并將一維線性元胞自動(dòng)機(jī)的相關(guān)理論推廣到二維

3、中來(lái)，得到一個(gè)求二維170N規(guī)則CA的瞬時(shí)長(zhǎng)度和極大圈長(zhǎng)的算法。 主要結(jié)果： 定理2.1.2 設(shè)是一個(gè)二維170N規(guī)則元胞自動(dòng)機(jī)，是它的任一個(gè)位形，若存在可逆矩陣、，使得為對(duì)角型矩陣，則是的GOE的充分必要條件是，其中求二維170N規(guī)則元胞自動(dòng)機(jī)的GOE個(gè)數(shù)的步驟： 步驟1 給定 . 算出 . 步驟2 計(jì)算，其中是位形通式，記乘積結(jié)果為 . 步驟3 對(duì)作行、列的初等變換化為對(duì)角型，對(duì)作相同的行初等

4、變換得 . 步驟4 算出滿足條件“，”的的組合數(shù)，|GOE|就等于所求得的組合數(shù). 推論2.1.3 設(shè)是一個(gè)二維170N規(guī)則元胞自動(dòng)機(jī)，是非負(fù)整數(shù)，為正整數(shù)（1）當(dāng)時(shí)，若 |GOE|若 |GOE|（2）當(dāng)時(shí)，若 |GOE|若 |GOE|給定、，求二維170N規(guī)則元胞自動(dòng)機(jī)的算法為： （1）對(duì)進(jìn)行標(biāo)準(zhǔn)化，化為標(biāo)準(zhǔn)型（2） 就是的極小多項(xiàng)式，令的最低次數(shù)，（3）若，則，否則（4） （5）令中系數(shù)不為0

5、的項(xiàng)的第二低的次數(shù)（6）若，跳到第（9）步，否則（7） （8）返回到第（5）步（9） （10）停止第三章是關(guān)于周期邊界條件下170規(guī)則（簡(jiǎn)稱(chēng)170P規(guī)則）元胞自動(dòng)機(jī)的研究.這部分內(nèi)容與第二章類(lèi)似，同樣是利用矩陣的方法對(duì)170P規(guī)則元胞自動(dòng)機(jī)進(jìn)行討論，得到相應(yīng)的結(jié)論。 主要結(jié)果： 求二維170P規(guī)則元胞自動(dòng)機(jī)的GOE個(gè)數(shù)的步驟： 步驟1 給定，有位形通式，記，其中為階列矩陣， . 步驟

6、2 當(dāng)時(shí)若為偶數(shù)在中，對(duì)進(jìn)行對(duì)角化，對(duì)作相應(yīng)的行變換，直到具有下列形式則|GOE|=“使至少有一個(gè)的組合數(shù)”. 若為奇數(shù)在中，對(duì)進(jìn)行對(duì)角化，對(duì)作相應(yīng)的行變換，直到具有下列形式則|GOE|=“使的組合數(shù)” . 當(dāng)時(shí) 在中，對(duì)進(jìn)行對(duì)角化，對(duì)作相應(yīng)的行變換，直到具有下列形式記這一矩陣為則|GOE|=“使的組合數(shù)”. 當(dāng)時(shí) 若為偶數(shù) 計(jì)算出記為①式其中在①式中，對(duì)進(jìn)行對(duì)角化，對(duì)做相應(yīng)的行變換，直到

7、變?yōu)橄铝行问接涍@一矩陣為則|GOE|=“使的組合數(shù)”. 若為奇數(shù) 計(jì)算出記為②式其中在②式中，對(duì)進(jìn)行對(duì)角化，對(duì)做相應(yīng)的行變換，直到具有下列形式記這一矩陣為則|GOE|=“使的組合數(shù)” . 當(dāng)給定，求170P規(guī)則元胞自動(dòng)機(jī)的的算法與170N規(guī)則元胞自動(dòng)機(jī)的類(lèi)似，只需將其中的步驟（1）換成（1’）： （1’）當(dāng)時(shí)，直接對(duì)進(jìn)行標(biāo)準(zhǔn)化，化為標(biāo)準(zhǔn)型當(dāng)時(shí)，對(duì)進(jìn)行標(biāo)準(zhǔn)化，化為標(biāo)準(zhǔn)型，其中 . 第四章是

8、關(guān)于170N和171N混合規(guī)則元胞自動(dòng)機(jī)的研究。這部分與第二章類(lèi)似，同樣是利用矩陣的方法對(duì)170N和171N混合規(guī)則元胞自動(dòng)機(jī)進(jìn)行討論，得到相應(yīng)的結(jié)論。 主要結(jié)果： 注：此章的矩陣多項(xiàng)式的定義遵循定義4.1.1。 定理4.1.2 設(shè)是一個(gè)二維170N和171N混合規(guī)則元胞自動(dòng)機(jī)，是它的任意一個(gè)位形，則E是的GOE ，其中、、、、的定義在預(yù)備知識(shí)中給出，當(dāng)為偶數(shù)時(shí)（即為奇數(shù)時(shí)） 當(dāng)為奇數(shù)時(shí)（即為偶

9、數(shù)時(shí)） 求170N和171N混合規(guī)則元胞自動(dòng)機(jī)的GOE個(gè)數(shù)的步驟： 步驟1 根據(jù)給定 .有位形通式，求出 . 步驟2 算出步驟3 將通過(guò)初等變換化成對(duì)角形，對(duì)實(shí)施相同的行初等變換化為 . 步驟4 算出滿足條件“”的的組合數(shù)，這個(gè)組合數(shù)就是所要求的GOE的個(gè)數(shù). 當(dāng)給定，求170和171混合規(guī)則元胞自動(dòng)機(jī)的的算法與170N規(guī)則元胞自動(dòng)機(jī)的類(lèi)似，只需將其中的步驟（1）換成（1’’）：