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

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

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

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

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

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

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

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

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

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