高橋，大輔

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

パターン生成CAの方程式と解について

新田，真奈美

早稲田大学基幹理工学研究科

高橋，大輔

早稲田大学基幹理工学研究科

https://doi.org/10.15017/1448878

出版情報：応用力学研究所研究集会報告. 25AO-S2 (20), pp.127-132, 2014-03. Research Institute for Applied Mechanics, Kyushu University

バージョン：

権利関係：

応用力学研究所研究集会報告

No.25AO-S2

「非線形波動研究の拡がり」（研究代表者 増田 哲）

Reports of RIAM Symposium No.25AO-S2

Proceedings of a symposium held at Chikushi Campus, Kyushu Universiy, Kasuga, Fukuoka, Japan, October 31 - November 2, 2013

Research Institute for Applied Mechanics Kyushu University

March, 2014 Article No. 20 (pp. 127 - 132)

パターン生成 CA ^{の方程式と} 解について

新田 真奈美（ NITTA Manami ），高橋 大輔（ TAKAHASHI Daisuke ）

（Received 17 January 2014; accepted 7 March 2014）

パターン生成CAの方程式と解について

早稲田大学基幹理工学研究科 新田真奈美（NITTA Manami）

早稲田大学基幹理工学研究科 高橋大輔 （TAKAHASHI Daisuke）

概要

セルオートマトン(CA)には，特徴的なパターンを示す解を持つものが数多く存在する．今回の研究で は２次元 CA が生成する縞状の解に注目し、その生成メカニズムを方程式の解の立場から解析し，更に パターンを持つような方程式の探索を行うことを目標としている．

1 はじめに

今回の研究では，図１のような十字型の近傍を持ち以下のような時間発展則で表される時間１次元空 間２次元 CA をあつかう．演算には束表現（∧，∨）及び共役操作（ ̅）を用いる．

𝑢_𝐶^𝑛+1= 𝑓(𝑢_𝐶^𝑛, 𝑢_𝑊^𝑛, 𝑢_𝐸^𝑛, 𝑢_𝑆^𝑛, 𝑢_𝑁^𝑛) (1)

𝑢_𝑁^𝑛 𝑢_𝑊^𝑛 𝑢_𝐶^𝑛 𝑢_𝐸^𝑛

𝑢_𝑆^𝑛

図１ 十字近傍

(1)の方程式に図２のように縞状の構造を持つ初期値を与え時間発展させた場合，一般的には縞状の構 造は保たれず，時間とともに崩れていくが，図２の構造を保った定常状態を持つ方程式が存在する．今 回の研究ではこの定常状態を縞パターンと呼び，(1)が縞パターンを生成するメカニズムについて解析 を行った．

n=0 n=1 n=2 n=3

（𝑢_𝐶^𝑛+1= 𝑢̅̅̅̅ ∧ 𝑢^𝑛_𝐶 ̅̅̅̅ ∧ 𝑢^𝑛_𝑊 ̅̅̅̅ ∧ 𝑢_𝐸^𝑛 ̅̅̅̅ ∧ 𝑢^𝑛_𝑆 ̅̅̅̅^𝑛_𝑁，格子数 30×30，周期境界条件）

図２ 縞パターンを持つ時間発展の例

2 座標曲線群によるリダクション

２次元 CA のもつ縞パターンに対して，座標曲線群の考えを導入し，曲線とパターンが対応するよう に以下の仮定をおく．

仮定１:同一曲線上に属するセルの状態値は等しい（時間変化しても構わない）

この仮定により状態値を曲線ごとにグループ化することが出来る．時刻 n の k 番目の曲線上での値を𝑣_𝑘^𝑛 とすれば，(1)の式は自身と隣り合う曲線の値𝑣_𝑘−1^𝑛 ，𝑣_𝑘^𝑛，𝑣_𝑘+1^𝑛 を用いて以下のような空間１次元の CA に リダクションすることが出来る．

𝑢_𝐶^𝑛+1= 𝑓(𝑢_𝐶^𝑛, 𝑢_𝑊^𝑛, 𝑢_𝐸^𝑛, 𝑢_𝑆^𝑛, 𝑢_𝑁^𝑛)

= 𝑔(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 ) (2)

今回の研究では以下の２つの基本の縞パターンと，それらを接続したパターンについて解析を行った．

基本パターン I

横縞からなるパターンを考える．図３のように水平線を座標曲線とすれば𝑖によらず𝑣_𝑘^𝑛= 𝑢_𝑖𝑘^𝑛となり，各 近傍の値は図４のようになる．したがって，時間発展方程式は以下で与えられる．

𝑣_𝑘^𝑛+1= 𝑓(𝑣_𝑘^𝑛, 𝑣_𝑘^𝑛, 𝑣_𝑘^𝑛, 𝑣_𝑘−1^𝑛 , 𝑣_𝑘+1^𝑛 )

= 𝑔₁(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 )

2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 -1 -1 -1 -1 -1 -2 -2 -2 -2 -2

（𝑣_𝑘^𝑛の𝑘部分を表記）

図３ 基本パターン I の曲線群

𝑢_𝑁^𝑛 𝑣_𝑘+1^𝑛

𝑢_𝑊^𝑛 𝑢_𝐶^𝑛 𝑢_𝐸^𝑛 → 𝑣_𝑘^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘^𝑛

𝑢_𝑆^𝑛 𝑣_𝑘−1^𝑛

図４ 基本パターン I の近傍

基本パターン II

同様に，斜め 45°の縞からなる基本パターン II は図６のような近傍を取り，以下のように与えられる．

𝑣_𝑘^𝑛+1= 𝑓(𝑣_𝑘^𝑛, 𝑣_𝑘−1^𝑛 , 𝑣_𝑘+1^𝑛 , 𝑣_𝑘−1^𝑛 , 𝑣_𝑘+1^𝑛 )

= 𝑔₂(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 )

0 1 2 3 4 -1 0 1 2 3 -2 -1 0 1 2 -3 -2 -1 0 1 -4 -3 -2 -1 0 図５ 基本パターン II の曲線群

𝑢_𝑁^𝑛 𝑣_𝑘+1^𝑛

𝑢_𝑊^𝑛 𝑢_𝐶^𝑛 𝑢_𝐸^𝑛 → 𝑣_𝑘−1^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘+1^𝑛

𝑢_𝑆^𝑛 𝑣_𝑘−1^𝑛

図６ 基本パターン II の近傍

このように２次元のパターンは座標曲線群と１次元 CA の組み合わせで実現される．この発想を逆にし て，１次元 CA からパターンを生み出す２次元 CA を生成することもできる．

２次元の縞パターン ⇔ 座標曲線群 ＋１次元 CA

3 基本パターンの接続

次に基本パターン I と基本パターン II の領域が共存する場合について考える．

パターン III

左側が基本パターンⅠ，右側が基本パターン II であるパターン III の場合，図７のように３つの領域 (a)，(b)，(c)に分かれ，(b)は図８のような新たな近傍の配置を持つ．よってそれぞれのリダクション は以下のようになる．

(a) 𝑣_𝑘^𝑛+1= 𝑔₁(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 )

(b) 𝑣_𝑘^𝑛+1= 𝑓(𝑣_𝑘^𝑛, 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 , 𝑣_𝑘−1^𝑛 , 𝑣_𝑘+1^𝑛 )

= 𝑔3(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 ) (c) 𝑣_𝑘^𝑛+1= 𝑔₂(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 )

2 2 2 3 4 1 1 1 2 3 0 0 0 1 2 -1 -1 -1 0 1 -2 -2 -2 -1 0

(a) (b) (c) 図７ パターン III の曲線群

𝑣_𝑘+1^𝑛

𝑣_𝑘^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘+1^𝑛 𝑣_𝑘−1^𝑛

図８ パターン III の接続部(b)の近傍

仮定１よりパターン III が存在するための必要条件は𝑔₁≡ 𝑔3≡ 𝑔2で与えられる．

同様に，その他の基本パターンの接続についても同様に必要条件を求めることが出来る．

パターン IV

図９のような左右が反転した基本パターン II 同士の接続を考える．基本パターン II の反転によって得 られる式を𝑔_2’として，接続領域(b)について新たに𝑔₄をおけば𝑔₂≡ 𝑔4≡ 𝑔2’が必要条件であることがわ かる．

4 3 2 3 4 3 2 1 2 3 2 1 0 1 2 1 0 -1 0 1 0 -1 -2 -1 0 (a) (b) (c) 図９ パターン IV の曲線群

𝑣_𝑘+1^𝑛 𝑣_𝑘+1^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘+1^𝑛

𝑣_𝑘−1^𝑛

図１０ パターン IV の接続部(b)の近傍

パターン V

基本パターン I とそれを 90°回転したパターンの接続を考える．基本パターン I の回転によって得られ る式を𝑔_1’として，接続領域について新たに𝑔₅をおけば𝑔₁≡ 𝑔5≡ 𝑔1’が必要条件であることがわかる．

2 2 2 2 2 2 1 1 1 1 2 1 0 0 0 2 1 0 -1 -1 2 1 0 -1 -2 図１１ パターン V の曲線群

𝑣_𝑘+1^𝑛 𝑣_𝑘+1^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘^𝑛

𝑣_𝑘^𝑛

図１２ パターン V の接続部の近傍

パターン VI

パターン III とは異なる基本パターン I と基本パターン II（180°回転）の接続を考える．パターン VI では接続領域が３種類に分かれるため．(a)，(b)，(c)としてそれぞれの式を𝑔₆，𝑔₇，𝑔₈とおく．基本 パターン II の回転によって得られる式を𝑔_2’’とすれば，𝑔₁≡ 𝑔6≡ 𝑔7≡ 𝑔8≡ 𝑔2’’が必要条件であること がわかる．

1 0 -1 -2 -3 -4 1 1 0 -1 -2 -3 0 0 0 0 -1 -2 -1 -1 -1 -1 -1 -1 図１３ パターン VI の曲線群

𝑣_𝑘^𝑛 𝑣_𝑘−1^𝑛 𝑣_𝑘−1^𝑛

𝑣_𝑘^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘−1^𝑛 𝑣_𝑘+1^𝑛 𝑣_𝑘^𝑛 𝑣_𝑘−1^𝑛

𝑣_𝑘−1^𝑛 𝑣_𝑘−1^𝑛 𝑣_𝑘^𝑛

(a) (b) (c) 図１４ パターン VI の接続部の近傍

上述のリダクションは，空間の回転と鏡映に対して対称ではない．したがって，たとえばある CA でパ ターン III が存在しても，それを 90°回転したパターンが存在するかどうかは保証されない．そこで今 回の研究では，回転および鏡映について対称な方程式についてのみ解析を行った．

仮定２：方程式が回転，鏡映対称性を持つ．

4 解析結果

仮定２を満たす 25 の独立な方程式に対して，解に仮定１を想定してパターン III～VI の存在を検証 した結果の一部を以下に示す．

表１ 束表現とその存在パターン

束表現 存在パターン（かっこ内は{0,1}限定で存在）

𝑢̅̅̅̅ ∧ 𝑢_𝐶^𝑛 ̅̅̅̅ ∧ 𝑢_𝑊^𝑛 ̅̅̅̅ ∧ 𝑢_𝐸^𝑛 ̅̅̅̅ ∧ 𝑢_𝑆^𝑛 ̅̅̅̅_𝑁^𝑛 III,IV 𝑢_𝐶^𝑛∧ 𝑢̅̅̅̅ ∧ 𝑢_𝑊^𝑛 ̅̅̅̅ ∧ 𝑢_𝐸^𝑛 ̅̅̅̅ ∧ 𝑢_𝑆^𝑛 ̅̅̅̅_𝑁^𝑛 IV,(V)

𝑢_𝑊^𝑛

̅̅̅̅ ∧ 𝑢̅̅̅̅ ∧ 𝑢_𝐸^𝑛 ̅̅̅̅ ∧ 𝑢_𝑆^𝑛 ̅̅̅̅_𝑁^𝑛 IV 𝑢_𝐶^𝑛

̅̅̅̅ ∧ (𝑢_𝑊^𝑛 ∨ 𝑢_𝐸^𝑛∨ 𝑢_𝑆^𝑛∨ 𝑢_𝑁^𝑛) IV,(III) 𝑢_𝐶^𝑛

̅̅̅̅ III,IV,V,VI

パターン V，VI をみたすものは１近傍の自明な例しか存在しなかった．これはそれらのパターンの存在 条件がとても厳しく，対称性と両立することが非常に難しいためである．ところが状態値を{0,1}に限 定すると方程式の同値性が緩くなる．例として次のような式がパターン III を持つかどうかを考える．

𝑢_𝐶^𝑛+1= 𝑢̅̅̅̅ ∧ (𝑢_𝐶^𝑛 _𝑊^𝑛 ∨ 𝑢_𝐸^𝑛∨ 𝑢_𝑆^𝑛∨ 𝑢_𝑁^𝑛) (3)

(3)についてリダクションを行うと次のような式となる．

𝑔1= 𝑔3(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 ) = 𝑣̅̅̅̅⋀(𝑣_𝑘^𝑛 _𝑘−1^𝑛 ∨ 𝑣_𝑘^𝑛∨ 𝑣_𝑘+1^𝑛 ) 𝑔2(𝑣_𝑘−1^𝑛 , 𝑣_𝑘^𝑛, 𝑣_𝑘+1^𝑛 ) = 𝑣̅̅̅̅⋀(𝑣_𝑘^𝑛 _𝑘−1^𝑛 ∨ 𝑣_𝑘+1^𝑛 )

式が一致しないため，一般束ではパターン III は存在しないことがわかる（図１５）．しかし２つの式

はどちらも ECA50 の時間発展方程式なので，

𝒈𝟐≢ 𝒈𝟑（一般束）⇔ 𝒈𝟐≡ 𝒈𝟑（ブール束）

となり，{0,1}ではパターン III が許される（図１６）.

図１５ パターン III が壊れる整数解 図１６ {0,1}でのパターン III

5 おわりに

今回の研究を通して，それぞれのパターンを持つ束表現の特徴を掴むことが出来た．上述の手法の汎 用化や，より複雑な共存パターンに対してこれらの結果を活用してゆくことを今後の課題としている．

参考文献

[1] 広田良吾・高橋大輔, “差分と超離散”, 共立出版 (2003)

[2] D.Takahashi, A. Shida, M. Usami, “On pattern formation mechanism of 2+1D max-plus models”, J. Phys. A, 34 (2001) 10715-10726