「ルール184」の版間の差分

履歴の双方向閲覧

新しい編集 →

削除された内容追加された内容

ビジュアルウィキテキスト

インライン

2017年11月23日 (木) 07:01時点における版

ランダムな初期状態から、ルール184に従った128ステップの様子。上から順に初期状態の黒の割合は25%、50%、75%である。左右にも同様のパターンが有る状態から幅300ピクセルのみを表示。

ルール184は1次元セル・オートマトンのルールの1つである。密度分類問題や、パーティクル・システムの記述、渋滞の解析に用いられる。

ルール184は、一車線の高速道路の交通流の単純なモデルとして利用でき、より高精度な交通流をモデル化するセル・オートマトンのモデルの基礎である。このモデルでは、車両を表すセルは前方の車両の存在に応じて停止・移動する。車両の数は時間に対して不変である。これらの用途のため、ルール184はtraffic ruleと呼ばれる^[1]。
ルール184は不規則な凹凸のある面に堆積する粒子のモデルにもなる。0と1は表面の局所的な傾きに対応し、谷に対応する場所に粒子が1つずつ堆積する。ステップごとに、堆積する粒子の数は増加するが、一度堆積した粒子は移動しない。
ルール184は、一次元媒体を通して左右に移動する粒子の対消滅としても理解できる。2つの粒子が衝突する際、その粒子は共に消滅する。粒子の数は変化しないか減少する。

上記の3つは矛盾するように見えるのは、セル・オートマトンの状態と物理的な特徴の関連付けが異なるためである。例えば、1の状態の数は車両の数に一致するが、堆積する粒子の数や対消滅する粒子の数には一致しない。

ルール184と言う名前は、状態遷移を表すウルフラムコードによるもので、最初に研究されたのは Li (1987) と Krug & Spohn (1988)によるものである。特にKrugとSpohnによる研究では、ルール184の上記の3つの物理モデルに言及している^[2].

定義

ルール184のオートマトンの状態は0と1のみを持ち、その場所自身に加え、左右のセルによって次の状態を決定する。各ステップにおいて、ルール184は以下のルールセットを適用して次の状態に遷移する^[3]。

現在の状態	111	110	101	100	011	010	001	000
中央のセルの次の状態	1	0	1	1	1	0	0	0

この状態遷移表によってルール184は定義されている。ルール184の184は下の行の10111000を10進法で表記した値である^[4]。

ルール184のルールセットは様々な方法で直感的に理解できる。

各ステップで、"10"が存在する場合、状態を入れ替えて"01"とする。この方法では、Krug & Spohn (1988) はルール184を「非対称スピン交換ダイナミクスを用いた動的イジング模型」の決定的な場合と呼んだ。
各ステップで、1が0に続く場合、1は右に移動する。1が1に続く場合は1は移動せず、1が続かない0も0のままである。この理解は、交通流のモデルに最も適している^[5]。
各ステップで、0のセルは左の状態をコピーする。1のセルは右の状態をコピーする。つまり、それぞれのセルはマルチプレクサとして働き、その動作はフレドキンゲートと密接に関係している^[6]。

ダイナミクスと密度分類問題（多数決問題）

上記のルールの説明から、ダイナミクスの2つの重要な特性が浮き出る。まず、ルール184は周期的境界条件を持つ任意の有限集合のセルに対して、0と1の数を変化させない。ルール184とその対称は、0と1の数を変化させない唯一のこのタイプのセル・オートマトンルールである^[7]。無限に続く配列でも1の割合（密度）が明確に定義されていれば、0と1の割合は不変である^[8]。また、ルール184は左右対称ではないが左右反転と同時に0と1を入れ替えると同じルールのセル・オートマトンとなる性質を持つ。

ルール184では、全体が左か右に1マスずつ移動するように見えるパターンに安定する。具体的には、初期状態の1の割合が50%未満であれば右に移動するように見えるパターンとなり、1のセル同士は2マス以上離れる。逆に、初期状態の1の割合が50%を超える場合は左に移動するように見えるパターンとなり、こちらでは0のセル同士は2マス以上離れる。初期状態の1の割合が50%であれば、左に移動しているように見えるパターンと右に移動しているようにみえるパターンが織り交ざったように見えるパターンで安定化する^[9]。

密度分類問題（多数決問題）は任意の有限集合上で実行されたとき、最大多数のセルが保持する値を計算するセル・オートマトンを構築する問題である。ルール184は、周期的境界条件を有する有限集合状のセル上で実行された場合、0と1の数が等しくない場合には各セルは多い側の状態が連続する場面に無限回遭遇するが、少ない側の状態が連続する場面には有限回しか遭遇しないという意味では解決できる^[10]。密度分類問題は最終的にすべてのセルが最大多数の状態に安定する必要があるが、ルール184は0と1の数を変化させないため、全てのセルを最大多数の状態にすることは不可能である^[11]。しかし、ルール184は最大多数のセルの状態を認識することが出来るという条件では解決している。

交通流

ルール184は交通流のシミュレーションとして実装される。1のセルは車両に対応し、前方があいている車両（テールランプが光っていない車両）は進むルールに対応する。

ルール184の1のセルを車両とすると、1車線の車両のように振る舞う。車両は前方が空いていれば1マス進み、空いていなければ止まる。ルール184のような交通流モデルや同様に空間と時間の両方を離散化した一般化は、パーティクルホッピングモデル（particle-hopping model）と呼ばれる^[12]。非常に原始的なモデルであるが、ルール184のモデルは実際の交通に見られる身近な現象をすでに予測している。交通量が少ないときには車両は自由に動き、交通量が増加すると少し進んでは停止するような渋滞が見られる^[13]。

ルール184が初めて用いられた場所を特定することは難しい。なぜなら、この分野の研究は極度に数学的抽象化を行うことには焦点があてられず、モデルのもっともらしさに焦点が当てられたため、セル・オートマトンの交通流シミュレーションの論文では実際の交通をより正確にシミュレートするためにより複雑なモデルが用いられたからである。それにもかかわらず、ルール184はセル・オートマトンを用いた交通流シミュレーションの基礎である。例えば Wang, Kwong & Hui (1998)は「1次元交通流問題を表す基礎的なセル・オートマトンはルール184である」と述べている。 Nagel (1996) は「交通流を扱うセル・オートマトンの多くはこのモデルに基づいている」と書いている。複数の速度で車両が動く1次元モデルを扱う場合があるが、同一の速度であればルール184に縮退する^[14] 。Gaylord & Nishidate (1996) はルール184を拡張し、車線変更を含む2車線の交通流モデルを構築した。このモデルではルール184とその左右・0-1対称を用いている。Biham, Middleton & Levine (1992) は本質的にルール184に従う車線のダイナミクスを用いた2次元の街のグリッドモデルを用いた^[15]。より詳しいセル・オートマトンによる交通流シミュレーションのモデルと統計力学については Maerivoet & De Moor (2005) と Chowdhury, Santen & Schadschneider (2000)を参照。

ルール184を交通流モデルとして考えるとき、車両の平均速度が注目される。車両の密度が50%未満であれば、平均速度は単位時間に1マスへと収束する。しかし、車両の密度が1/2を超えると、平均速度は密度 ρに対して ${\tfrac {1-\rho }{\rho }}$ となり、 $ρ = 1/2$ において相転移が生じる。ルール184が $ρ = 1/2$ のランダムな初期状態から開始する場合、平均速度はステップ数の平方根に従って定常状態に近づく。密度が50%ではない場合には、平均速度には指数関数的に近づく^[16]。

堆積

図のように、ルール184は表面に堆積する粒子のモデルにも用いられる。これは Krug & Spohn (1988)^[17] によって導入された。このモデルでは、斜めに配置された正方格子状に粒子が堆積する。下・左下・右下の3箇所が堆積している場所にのみ粒子は存在できる。表面（図中の黒い線）は堆積しうる表面のモデルである。各ステップにおいて、表面の谷（極小）に1つずつ新しい粒子（図中の明るい粒子）が堆積する。

この過程をルール184でモデル化するには、表面の計上を0と1で表す必要がある。各折れ線は+1（上り坂）と-1（下り坂）を組み合わせることで表すことができ、それぞれをセルの状態の0と1に対応させる。谷は左に下り坂、右に上り坂がある状態であるため、"10"に対応する。そしてその場所に粒子が堆積すると、"10"であった場所を"01"に変更することに対応し、折れ線は右に進む。これがルール184のルールに対応する^[18]。

このモデルに関する関連研究に、粒子が全ての谷に同時に到達するのではなく、粒子はランダムな時間間隔で堆積するとする物がある。^[19] これらの確率的な堆積過程では、非同期セル・オートマトンのモデルでモデル化できる。

対消滅

粒子の対消滅を考える。この過程の最も単純なモデルは、一次元空間を等速度で移動する1種類の粒子と逆方向に移動するその反粒子からなる^[20]。

この過程のルール184を用いてモデル化では、粒子と反粒子は単一セルの状態ではなく、同じ状態のセルの間としてモデル化される。0が連続する2つのセルは粒子を表し、ステップごとに右に移動する。そして、1が連続する2つのセルは反粒子を表し、ステップ時間ごとに左に移動する。粒子が存在しない残りの部分は0と1が交互に並び、粒子がこの中を移動する。この解釈では、粒子と反粒子は対消滅する相互作用を持つ。右に移動する粒子と左に移動する反粒子が衝突すると、近くの粒子に影響をあたえることなく両者が消滅する^[21]。

1次元の周期的セル・オートマトンなどの他のシステムの挙動は、この対消滅の観点からも記述できる^[22]。この対消滅モデルをルール184の観点から見ると、他のモデルにはない「0と1が交互に存在する」という媒質から生じる粒子の位置の制約が存在する。ルール184に対応する粒子の系では、連続する2つの粒子が同じ種類である場合、粒子は奇数マス離れることになるが、反粒子同士の距離は偶数マスとなる。しかし、この制限はこの系の統計的な振る舞いに影響を及ぼさない。

Pivato (2007) はルール184に似ているがより複雑なシステムを用いた。0と1の交互のパターンを媒質とするだけでなく、単一の状態からなる領域も媒質とした。この観点から、Pivatoは領域の協会によって形成される7種類の粒子を記述し、それらが生じうる相互作用を分類した。対消滅モデルの詳細についてはChopard & Droz (1998, pp. 188–190)を参照。

文脈自由構文解析

In his book A New Kind of Science, Stephen Wolfram points out that rule 184, when run on patterns with density 50%, can be interpreted as parsing the context free language describing strings formed from nested parentheses. This interpretation is closely related to the ballistic annihilation view of rule 184: in Wolfram's interpretation, an open parenthesis corresponds to a left-moving particle while a close parenthesis corresponds to a right-moving particle.^[23]

参照

注記

^ E.g. see Fukś (1997).
^ One can find many later papers that, when mentioning Rule 184, cite the early papers of Stephen Wolfram. However, Wolfram's papers consider only automata that are symmetric under left-right reversal, and therefore do not describe Rule 184.
^ This rule table is already given in a shorthand form in the name "Rule 184", but it can be found explicitly e.g. in Fukś (1997).
^ For the definition of this code, see Wolfram (2002), p.53. For the calculation of this code for Rule 184, see e.g. Boccara & Fukś (1998).
^ See, e.g., Boccara & Fukś (1998).
^ Li (1992). Li used this interpretation as part of a generalization of Rule 184 to nonlocal neighborhood structures.
^ Boccara & Fukś (1998); Alonso-Sanz (2011).
^ Boccara & Fukś (1998) have investigated more general automata with similar conservation properties, as has Moreira (2003).
^ Li (1987).
^ Capcarrere, Sipper & Tomassini (1996); Fukś (1997); Sukumar (1998).
^ Land & Belew (1995).
^ Nagel (1996); Chowdhury, Santen & Schadschneider (2000).
^ Tadaki & Kikuchi (1994).
^ For several models of this type see Nagel & Schreckenberg (1992), Fukui & Ishibashi (1996), and Fukś & Boccara (1998). Nagel (1996) observes the equivalence of these models to rule 184 in the single-speed case and lists several additional papers on this type of model.
^ See also Tadaki & Kikuchi (1994) for additional analysis of this model.
^ Fukś & Boccara (1998).
^ See also Belitsky & Ferrari (1995) and Chopard & Droz (1998, p. 29).
^ Krug & Spohn (1988).
^ Also discussed by Krug & Spohn (1988).
^ Redner (2001).
^ Krug & Spohn (1988); Belitsky & Ferrari (1995).
^ Belitsky & Ferrari (1995).
^ Wolfram (2002, pp. 989, 1109).

参考文献

Alonso-Sanz, Ramon (2011). “Number-preserving rules”. Discrete Systems with Memory. World Scientific series on nonlinear science, Ser. A. 75. World Scientific. pp. 55–57. ISBN 9789814343633
Belitsky, Vladimir; Ferrari, Pablo A. (1995). “Ballistic annihilation and deterministic surface growth”. Journal of Statistical Physics 80 (3–4): 517–543. Bibcode: 1995JSP....80..517B. doi:10.1007/BF02178546.
Biham, Ofer; Middleton, A. Alan; Levine, Dov (1992). “Self-organization and a dynamic transition in traffic-flow models”. Physical Review A 46 (10): R6124–R6127. arXiv:cond-mat/9206001. Bibcode: 1992PhRvA..46.6124B. doi:10.1103/PhysRevA.46.R6124. PMID 9907993.
Boccara, Nino; Fukś, Henryk (1998). “Cellular automaton rules conserving the number of active sites”. Journal of Physics A: Math. Gen. 31 (28): 6007–6018. arXiv:adap-org/9712003. Bibcode: 1998JPhA...31.6007B. doi:10.1088/0305-4470/31/28/014.
Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). “Two-state, $r = 1$ cellular automaton that classifies density”. Physical Review Letters 77 (24): 4969–4971. Bibcode: 1996PhRvL..77.4969C. doi:10.1103/PhysRevLett.77.4969. PMID 10062680.
Chopard, Bastien; Droz, Michel (1998). Cellular Automata Modeling of Physical Systems. Cambridge University Press. ISBN 0-521-67345-3
Chowdhury, Debashish; Santen, Ludger; Schadschneider, Andreas (2000). “Statistical physics of vehicular traffic and some related systems”. Physics Reports 329 (4): 199–329. arXiv:cond-mat/0007053. Bibcode: 2000PhR...329..199C. doi:10.1016/S0370-1573(99)00117-9.
Fukś, Henryk (1997). “Solution of the density classification problem with two similar cellular automata rules”. Physical Review E 55 (3): R2081–R2084. Bibcode: 1997PhRvE..55.2081F. doi:10.1103/PhysRevE.55.R2081.
Fukś, Henryk; Boccara, Nino (1998). “Generalized deterministic traffic rules”. International Journal of Modern Physics C 9 (1): 1–12. Bibcode: 1998IJMPC...9....1F. doi:10.1142/S0129183198000029. オリジナルの27 September 2007時点におけるアーカイブ。.
Fukui, M.; Ishibashi, Y. (1996). “Traffic flow in 1D cellular automaton model including cars moving with high speed”. Journal of the Physical Society of Japan 65 (6): 1868–1870. Bibcode: 1996JPSJ...65.1868F. doi:10.1143/JPSJ.65.1868.
Gaylord, Richard J.; Nishidate, Kazume (1996). “Traffic Flow”. Modeling Nature: Cellular Automata Simulations with Mathematica. Springer-Verlag. pp. 29–34. ISBN 978-0-387-94620-7
Krug, J.; Spohn, H. (1988). “Universality classes for deterministic surface growth”. Physical Review A 38 (8): 4271–4283. Bibcode: 1988PhRvA..38.4271K. doi:10.1103/PhysRevA.38.4271. PMID 9900880.
Land, Mark; Belew, Richard (1995). “No perfect two-state cellular automata for density classification exists”. Physical Review Letters 74 (25): 1548–1550. Bibcode: 1995PhRvL..74.5148L. doi:10.1103/PhysRevLett.74.5148. PMID 10058695.
Li, Wentian (1987). “Power spectra of regular languages and cellular automata”. Complex Systems 1: 107–130.
Li, Wentian (1992). “Phenomenology of nonlocal cellular automata”. Journal of Statistical Physics 68 (5–6): 829–882. Bibcode: 1992JSP....68..829L. doi:10.1007/BF01048877.
Maerivoet, Sven; De Moor, Bart (2005). “Cellular automata models of road traffic”. Physics Reports 419 (1): 1–64. arXiv:physics/0509082. Bibcode: 2005PhR...419....1M. doi:10.1016/j.physrep.2005.08.005.
Moreira, Andres (2003). “Universality and decidability of number-conserving cellular automata”. Theoretical Computer Science 292 (3): 711–721. arXiv:nlin.CG/0306032. doi:10.1016/S0304-3975(02)00065-8.
Nagel, Kai (1996). “Particle hopping models and traffic flow theory”. Physical Review E 53 (5): 4655–4672. arXiv:cond-mat/9509075. Bibcode: 1996PhRvE..53.4655N. doi:10.1103/PhysRevE.53.4655.
Nagel, Kai; Schreckenberg, Michael (1992). “A cellular automaton model for freeway traffic”. Journal de Physique I 2 (12): 2221–2229. Bibcode: 1992JPhy1...2.2221N. doi:10.1051/jp1:1992277.
Pivato, M. (2007). “Defect particle kinematics in one-dimensional cellular automata”. Theoretical Computer Science 377 (1–3): 205–228. arXiv:math.DS/0506417. doi:10.1016/j.tcs.2007.03.014.
Redner, Sidney (2001). “8.5 Ballistic Annihilation”. A Guide to First-Passage Processes. Cambridge University Press. p. 288. ISBN 9780521652483
Sukumar, N. (1998). "Effect of boundary conditions on cellular automata that classify density". arXiv:comp-gas/9804001。 {{cite arXiv}}: 引数|ref=harvは不正です。 (説明)
Tadaki, Shin-ichi; Kikuchi, Macato (1994). “Jam phases in a two-dimensional cellular automaton model of traffic flow”. Physical Review E 50 (6): 4564–4570. Bibcode: 1994PhRvE..50.4564T. doi:10.1103/PhysRevE.50.4564.
Wang, Bing-Hong; Kwong, Yvonne-Roamy; Hui, Pak-Ming (1998). “Statistical mechanical approach to Fukui-Ishibashi traffic flow models”. Physical Review E 57 (3): 2568–2573. Bibcode: 1998PhRvE..57.2568W. doi:10.1103/PhysRevE.57.2568.
Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media

外部リンク

Rule 184 in Wolfram's atlas of cellular automata

[1] E.g. see Fukś (1997).

[2] One can find many later papers that, when mentioning Rule 184, cite the early papers of Stephen Wolfram. However, Wolfram's papers consider only automata that are symmetric under left-right reversal, and therefore do not describe Rule 184.

[3] This rule table is already given in a shorthand form in the name "Rule 184", but it can be found explicitly e.g. in Fukś (1997).

[4] For the definition of this code, see Wolfram (2002), p.53. For the calculation of this code for Rule 184, see e.g. Boccara & Fukś (1998).

[5] See, e.g., Boccara & Fukś (1998).

[6] Li (1992). Li used this interpretation as part of a generalization of Rule 184 to nonlocal neighborhood structures.

[7] Boccara & Fukś (1998); Alonso-Sanz (2011).

[8] Boccara & Fukś (1998) have investigated more general automata with similar conservation properties, as has Moreira (2003).

[FOOTNOTELi1987-9] Li (1987).

[10] Capcarrere, Sipper & Tomassini (1996); Fukś (1997); Sukumar (1998).

[11] Land & Belew (1995).

[12] Nagel (1996); Chowdhury, Santen & Schadschneider (2000).

[FOOTNOTETadakiKikuchi1994-13] Tadaki & Kikuchi (1994).

[14] For several models of this type see Nagel & Schreckenberg (1992), Fukui & Ishibashi (1996), and Fukś & Boccara (1998). Nagel (1996) observes the equivalence of these models to rule 184 in the single-speed case and lists several additional papers on this type of model.

[15] See also Tadaki & Kikuchi (1994) for additional analysis of this model.

[FOOTNOTEFukśBoccara1998-16] Fukś & Boccara (1998).

[17] See also Belitsky & Ferrari (1995) and Chopard & Droz (1998, p. 29).

[FOOTNOTEKrugSpohn1988-18] Krug & Spohn (1988).

[19] Also discussed by Krug & Spohn (1988).

[FOOTNOTERedner2001-20] Redner (2001).

[21] Krug & Spohn (1988); Belitsky & Ferrari (1995).

[FOOTNOTEBelitskyFerrari1995-22] Belitsky & Ferrari (1995).

[23] Wolfram (2002, pp. 989, 1109).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]