1/fゆらぎにもとづく2次元3状態万能セルオートマトンの探索

全文

(1)情報処理学会第 73 回全国大会. 3C-6. 1/f ゆらぎにもとづく 2 次元 3 状態万能セルオートマトンの探索蜷川繁金沢工業大学情報学部情報工学科〒 924-0838 石川県白山市八束穂 3-1 e-mail: ninagawa@infor.kanazawa-it.ac.jp. 1. はじめに計算万能であることが証明されているセルオートマ. トンのライフゲーム [1] や単純セルオートマトンのルール 110[2] は，いっぽうで 1/f ゆらぎを示すことが知ら. 図 2: 固定パターン. 白は状態 0，黒は状態 1，グレイ. れている [3, 4]．このことから計算万能性と 1/f ゆらぎ. は状態 2 のセルを表わす．. の間には何らかの関連性があるのではないかと予想されることから，2 次元 3 状態 9 近傍 CA において，1/f ゆらぎを示すルールを遺伝的アルゴリズムを用いて探索した [5]．本論文では得られたセルオートマトンの振. t. 舞いを調べ，計算万能性の可能性を探る．. t+1. t. t+1. 100. 図 3: 2 種類の周期 2 のパターン． 10. て得られたルールのうち，もっとも計算万能性の可能性があると思われるルールは 134 桁の 3 進数で次のよ 1. うに表わされる．. 0222222110110002112002101201102220. 0.1 1. 10. 100. 1000. 10000. 1022201021020100102010022001002212 1002221211002212212112201100200221. 図 1: 実験で得られたルールのパワースペクトル．. 01010010021210120222000002220000 このルールのパワースペクトルを図 1 に示す．f = 1 ∼. 2. 400 の範囲で最小自乗法で ln(Sf ) = α + β ln(f ) に当てはめると β = −0.535 となる．. 実験で得られたルール本研究で対象となる 2 次元 3 状態 9 近傍セルオート. マトンの遷移関数 d は次式で表現される．. 3. xi = d(c, n1 , n2 ), i = 45c + n1 (19 − n1 )/2 + n2 .. 種々のパターン本ルールに存在する固定パターンを図 2 に示す．な. ここで c ∈ {0, 1, 2} は近傍の中心セルの状態， n1 ，n2. お，ダイヤモンド型の固定パターンは小さいものから. は周囲 8 セルのうち，それぞれ，状態が 1，2 のセル. 順に 2 つまで表示しているが，これら以外に任意の大. 数を表し，xi ∈ {0, 1, 2} は中心セルの次ステップでの. きさのものが可能である．. 状態を示す．本研究では d(0, 0, 0) = 0 という遷移規. 周期 2 のパターンの主なものを図 3 に，グライダー. 則のみを対象とするので，遷移規則は 134 桁の 3 進数. を図 4 に示す．図 5 はイーターとよばれる固定パター. x134 · · ·x1 で表現される．文献 [5] で述べた実験によっ. 2-11. Copyright 2011 Information Processing Society of Japan. All Rights Reserved.. t.

(2) 情報処理学会第 73 回全国大会. t. t+1. t. t+1. t+2. t+3. t+4. t+5. t+2. 図 4: グライダー. 図 7: 周期 6 のパターン．. t. t+1. t+2. t+3. 図 5: イーターがグライダーを吸収する様子．. t. t+8. t+14. t+22. ンにグライダーが衝突し，グライダーが消滅する様子図 8: 右から飛来したグライダーと固定パターンの衝. を示す．右から飛来したグライダーと周期 2 の周期パターンの衝突によってイーターが生成される様子を図 6 に示す．周期 6 の周期パターンの 1 つを図 7 に示す．右から飛来したグライダーと固定パターンの衝突の様子を図 8 に示す．この衝突によって固定パターンが. 突の様子．. 5. 謝辞本研究は科研費（20500216）の助成を受けたもので. ある．. 2 セルだけ下へずれる．. 4. 参考文献. おわりに本研究で得られたルールにおいて，固定パターン，周. 期パターン，グライダー，イーターが存在し，それら. [1] E.R. Berlekamp, J. H. Conway, R. K. Guy: Winning Ways for Your Mathematical Plays, Vol.2, Academic Press, New York (1982).. の間の相互作用を調べた．今後は，これらのパターンを使って，論理回路が構成できるかどうか調べる予定である．. [2] M. Cook: Universality in Elementary Cellular Automata. Complex Systems 15 (2004) 1–40. [3] Ninagawa, S., Yoneda, M., Hirose, S.: 1/f Fluctuation in the ”Game of Life”. Physica D 118 (1988) 49–52. [4] S. Ninagawa: Power Spectral Analysis of Ele-. t. t+5. t+9. mentary Cellular Automata. Complex Systems 17 (2008) 399–411.. t+33. [5] 蜷川繁: 1/f ゆらぎにもとづく 2 次元セルオートマ図 6: 周期 2 のパターンとグライダーの衝突によって. トンの探索，情報処理学会創立 50 周年記念 (第 72. イーターが生成される過程．. 回) 全国大会講演論文集. (2010). 2-12. Copyright 2011 Information Processing Society of Japan. All Rights Reserved..

(3)