ルール184のソースを表示

[[ファイル:Rule_184.png|サムネイル|429x429ピクセル|ランダムな初期状態から、ルール184に従った128ステップの様子。上から順に初期状態の黒の割合は25%、50%、75%である。左右にも同様のパターンが有る状態から幅300ピクセルのみを表示。]]
'''ルール184'''は1次元セル・オートマトンのルールの1つである。[[密度分類問題]]や、[[パーティクル・システム]]の記述、[[渋滞]]の解析に用いられる。
* ルール184は、一車線の高速道路の交通流の単純なモデルとして利用でき、より高精度な交通流をモデル化するセル・オートマトンのモデルの基礎である。このモデルでは、車両を表すセルは前方の車両の存在に応じて停止・移動する。車両の数は時間に対して不変である。という性質を持つ。そのため、ルール184は渋滞を表すために使われ、この分野では traffic rule と呼ばれる<ref>E.g. see {{Harvtxt|Fukś|1997}}.</ref>。
* ルール184は、不規則な凹凸のある面に堆積する粒子のモデルとも考えられる。0と1はそれぞれ表面の局所的な傾きに対応し、谷に対応する場所に粒子が1つずつ堆積する。ステップごとに、堆積する粒子の数は増加するが、一度堆積した粒子は移動しない。
* ルール184は、一次元媒体を通して左右に移動する粒子の[[対消滅]]としても解釈できる。2つの粒子が衝突する際、その粒子は共に消滅する。粒子の数は変化しないか2つ1組を最小単位として減少する。
上記の3つが矛盾するように感じられるのは、セル・オートマトンの状態と物理的な特徴の関連付けが非常に異なるためである。例えば、``1''の数は車両の数を表すが、堆積する粒子の数や対消滅する粒子の数ではない。

ルール184と言う名前は、状態遷移を表すウルフラムコードに由来している。最初に研究されたのは {{Harvtxt|Li|1987}} と {{Harvtxt|Krug|Spohn|1988}}によるものである。特にKrugとSpohnによる研究では、ルール184の上記の3つの物理モデルに言及している<ref>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.</ref>.

== 定義 ==
ルール184のオートマトンの状態は0と1のみを持ち、その場所自身に加え、左右のセルによって次の状態を決定する。各ステップにおいて、ルール184は以下のルールセットを適用して次の状態に遷移する<ref>This rule table is already given in a shorthand form in the name "Rule 184", but it can be found explicitly e.g. in {{Harvtxt|Fukś|1997}}.</ref>。
{| class="wikitable" style="text-align: center; margin-bottom: 10px;"
!現在の状態
| 111
| 110
| 101
| 100
| 011
| 010
| 001
| 000
|-
!中央のセルの次の状態
| 1
| 0
| 1
| 1
| 1
| 0
| 0
| 0
|}
この状態遷移表によってルール184は定義されている。ルール184の184は下の行の10111000を10進法で表記した値である<ref>For the definition of this code, see {{Harvtxt|Wolfram|2002}}, p.53. For the calculation of this code for Rule 184, see e.g. {{Harvtxt|Boccara|Fukś|1998}}.</ref>。

ルール184のルールセットは様々な方法で直感的に理解できる。
* 各ステップで、"10"が存在する場合、状態を入れ替えて"01"とする。この方法では、{{Harvtxt|Krug|Spohn|1988}} はルール184を「非対称スピン交換ダイナミクスを用いた動的イジング模型」の決定的な場合と呼んだ。
* 各ステップで、1が0に続く場合、1は右に移動する。1が1に続く場合は1は移動せず、1が続かない0も0のままである。この理解は、交通流のモデルに最も適している<ref>See, e.g., {{Harvtxt|Boccara|Fukś|1998}}.</ref>。
* 各ステップで、0のセルは左の状態をコピーする。1のセルは右の状態をコピーする。つまり、それぞれのセルは[[マルチプレクサ]]として働き、その動作は[[フレドキンゲート]]と密接に関係している<ref>{{Harvtxt|Li|1992}}. Li used this interpretation as part of a generalization of Rule 184 to nonlocal neighborhood structures.</ref>。

== ダイナミクスと密度分類問題（多数決問題） ==
上記のルールの説明から、ダイナミクスの2つの重要な特性が浮き出る。まず、ルール184は[[周期的境界条件]]を持つ任意の有限集合のセルに対して、0と1の数を変化させない。ルール184とその対称は、0と1の数を変化させない唯一のこのタイプのセル・オートマトンルールである<ref>{{Harvtxt|Boccara|Fukś|1998}}; {{Harvtxt|Alonso-Sanz|2011}}.</ref>。無限に続く配列でも1の割合（密度）が明確に定義されていれば、0と1の割合は不変である<ref>{{Harvtxt|Boccara|Fukś|1998}} have investigated more general automata with similar [[保存則|conservation properties]], as has {{Harvtxt|Moreira|2003}}.</ref>。また、ルール184は左右対称ではないが左右反転と同時に0と1を入れ替えると同じルールのセル・オートマトンとなる性質を持つ。

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

密度分類問題（多数決問題）は任意の有限集合上で実行されたとき、最大多数のセルが保持する値を計算するセル・オートマトンを構築する問題である。ルール184は、周期的境界条件を有する有限集合状のセル上で実行された場合、0と1の数が等しくない場合には各セルは多い側の状態が連続する場面に無限回遭遇するが、少ない側の状態が連続する場面には有限回しか遭遇しないという意味では解決できる<ref>{{Harvtxt|Capcarrere|Sipper|Tomassini|1996}}; {{Harvtxt|Fukś|1997}}; {{Harvtxt|Sukumar|1998}}.</ref>。密度分類問題は最終的にすべてのセルが最大多数の状態に安定する必要があるが、ルール184は0と1の数を変化させないため、全てのセルを最大多数の状態にすることは不可能である<ref>{{Harvtxt|Land|Belew|1995}}.</ref>。しかし、ルール184は最大多数のセルの状態を認識することが出来るという条件では解決している。

== 交通流 ==
[[ファイル:Rule_184_cars.svg|サムネイル|ルール184は交通流のシミュレーションとして実装される。1のセルは車両に対応し、前方があいている車両（テールランプが光っていない車両）は進むルールに対応する。]]
ルール184の1のセルを車両とすると、1車線の車両のように振る舞う。車両は前方が空いていれば1マス進み、空いていなければ止まる。ルール184のような交通流モデルや同様に空間と時間の両方を離散化した一般化は、パーティクルホッピングモデル（particle-hopping model）と呼ばれる<ref>{{Harvtxt|Nagel|1996}}; {{Harvtxt|Chowdhury|Santen|Schadschneider|2000}}.</ref>。非常に原始的なモデルであるが、ルール184のモデルは実際の交通に見られる身近な現象をすでに予測している。交通量が少ないときには車両は自由に動き、交通量が増加すると少し進んでは停止するような渋滞が見られる{{Sfnp|Tadaki|Kikuchi|1994}}。

ルール184が初めて用いられた場所を特定することは難しい。なぜなら、この分野の研究は極度に数学的抽象化を行うことには焦点があてられず、モデルのもっともらしさに焦点が当てられたため、セル・オートマトンの交通流シミュレーションの論文では実際の交通をより正確にシミュレートするためにより複雑なモデルが用いられたからである。それにもかかわらず、ルール184はセル・オートマトンを用いた交通流シミュレーションの基礎である。例えば {{Harvtxt|Wang|Kwong|Hui|1998}}は「1次元交通流問題を表す基礎的なセル・オートマトンはルール184である」と述べている。 {{Harvtxt|Nagel|1996}} は「交通流を扱うセル・オートマトンの多くはこのモデルに基づいている」と書いている。複数の速度で車両が動く1次元モデルを扱う場合があるが、同一の速度であればルール184に縮退する<ref>For several models of this type see {{Harvtxt|Nagel|Schreckenberg|1992}}, {{Harvtxt|Fukui|Ishibashi|1996}}, and {{Harvtxt|Fukś|Boccara|1998}}. {{Harvtxt|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.</ref> 。{{Harvtxt|Gaylord|Nishidate|1996}} はルール184を拡張し、車線変更を含む2車線の交通流モデルを構築した。このモデルではルール184とその左右・0-1対称を用いている。{{Harvtxt|Biham|Middleton|Levine|1992}} は本質的にルール184に従う車線のダイナミクスを用いた2次元の街のグリッドモデルを用いた<ref>See also {{Harvtxt|Tadaki|Kikuchi|1994}} for additional analysis of this model.</ref>。より詳しいセル・オートマトンによる交通流シミュレーションのモデルと統計力学については {{Harvtxt|Maerivoet|De Moor|2005}} と {{Harvtxt|Chowdhury|Santen|Schadschneider|2000}}を参照。

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

== 堆積 ==
[[ファイル:Rule_184_deposition.svg|サムネイル|ルール184は表面への堆積のモデルにも用いられる。斜めの正方格子を形成する粒子の層を考えると、新しい粒子（図中では明るい粒子で示される）がステップごとに谷（極小値）に堆積する。セルオートマトンの状態は表面の局所的な傾きに対応する。]]
図のように、ルール184は表面に堆積する粒子のモデルにも用いられる。これは {{Harvtxt|Krug|Spohn|1988}}<ref>See also {{Harvtxt|Belitsky|Ferrari|1995}} and {{Harvtxt|Chopard|Droz|1998|p=29}}.</ref> によって導入された。このモデルでは、斜めに配置された正方格子状に粒子が堆積する。下・左下・右下の3箇所が堆積している場所にのみ粒子は存在できる。表面（図中の黒い線）は堆積しうる表面のモデルである。各ステップにおいて、表面の谷（極小）に1つずつ新しい粒子（図中の明るい粒子）が堆積する。

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

このモデルに関する関連研究に、粒子が全ての谷に同時に到達するのではなく、粒子はランダムな時間間隔で堆積するとする物がある<ref>Also discussed by {{Harvtxt|Krug|Spohn|1988}}.</ref>。これらの確率的な堆積過程では、[[非同期セル・オートマトン]]のモデルでモデル化できる。

== 対消滅 ==
[[ファイル:Rule_184_annihilation.svg|サムネイル|ルール184と対消滅のモデル。粒子と反粒子（連続する同じ状態でモデル化される）は互いに逆向きに移動し、衝突すると対消滅する。]]
粒子の対消滅を考える。この過程の最も単純なモデルは、一次元空間を等速度で移動する1種類の粒子と逆方向に移動するその反粒子からなる{{Sfnp|Redner|2001}}。

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

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

{{Harvtxt|Pivato|2007}} はルール184に似ているがより複雑なシステムを用いた。0と1の交互のパターンを媒質とするだけでなく、単一の状態からなる領域も媒質とした。この観点から、Pivatoは領域の協会によって形成される7種類の粒子を記述し、それらが生じうる相互作用を分類した。対消滅モデルの詳細については{{Harvtxt|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.<ref>{{Harvtxt|Wolfram|2002|pp=[http://www.wolframscience.com/nksonline/page–989a–text 989], [http://www.wolframscience.com/nksonline/page–1109b–text 1109]}}.</ref>

== 関連項目 ==
* [[ルール30]]
* [[ルール90]]
* [[ルール110]]

== 脚注 ==
{{reflist|30em}}

== 参考文献 ==
{{refbegin|30em}}
*{{cite book |title=Discrete Systems with Memory |volume=75 |series=World Scientific series on nonlinear science, Ser. A |first=Ramon |last=Alonso-Sanz |publisher=World Scientific |year=2011 |isbn=9789814343633 |contribution-url=https://books.google.com/books?id=UgnhKU9w3K8C&pg=PA55 |pages=55–57 |contribution=Number-preserving rules |ref=harv|和書}}
*{{cite journal|last1=Belitsky|first1=Vladimir|last2=Ferrari|first2=Pablo A.|title=Ballistic annihilation and deterministic surface growth|journal=[[Journal of Statistical Physics]]|volume=80|issue=3–4|year=1995|pages=517–543|doi=10.1007/BF02178546|bibcode=1995JSP....80..517B|ref=harv}}
*{{cite journal|last1=Biham|first1=Ofer|author1-link=Ofer Biham|last2=Middleton|first2=A. Alan|last3=Levine|first3=Dov|title=Self-organization and a dynamic transition in traffic-flow models|journal=[[Physical Review A]]|volume=46|issue=10|year=1992|pages=R6124–R6127|doi=10.1103/PhysRevA.46.R6124|pmid=9907993|arxiv=cond-mat/9206001|bibcode=1992PhRvA..46.6124B|ref=harv}}
*{{cite journal|last1=Boccara|first1=Nino|last2=Fukś|first2=Henryk|title=Cellular automaton rules conserving the number of active sites|journal=[[Journal of Physics A]]: Math. Gen.|volume=31|issue=28|pages=6007–6018|year=1998|doi=10.1088/0305-4470/31/28/014|arxiv=adap-org/9712003|bibcode=1998JPhA...31.6007B|ref=harv}}
*{{cite journal|last1=Capcarrere|first1=Mathieu S.|last2=Sipper|first2=Moshe|last3=Tomassini|first3=Marco|title=Two-state, {{math|1=''r'' = 1}} cellular automaton that classifies density|journal=[[Physical Review Letters]]|year=1996|volume=77|pages=4969–4971|url=http://www.cs.bgu.ac.il/~sipper/papabs/twostater1.pdf|doi=10.1103/PhysRevLett.77.4969|pmid=10062680|issue=24|bibcode=1996PhRvL..77.4969C|ref=harv}}
*{{cite book |last1=Chopard |first1=Bastien |last2=Droz |first2=Michel |title=Cellular Automata Modeling of Physical Systems |year=1998 |publisher=[[Cambridge University Press]] |isbn=0-521-67345-3 |ref=harv|和書}}
*{{cite journal|last1=Chowdhury|first1=Debashish|last2=Santen|first2=Ludger|last3=Schadschneider|first3=Andreas|title=Statistical physics of vehicular traffic and some related systems|journal=[[Physics Reports]]|volume=329|issue=4|pages=199–329|year=2000|doi=10.1016/S0370-1573(99)00117-9|arxiv=cond-mat/0007053|bibcode=2000PhR...329..199C|ref=harv}}
*{{cite journal|last=Fukś|first=Henryk|title=Solution of the density classification problem with two similar cellular automata rules|journal=[[Physical Review E]]|volume=55|issue=3|pages=R2081–R2084|year=1997|doi=10.1103/PhysRevE.55.R2081|bibcode=1997PhRvE..55.2081F|ref=harv}}
*{{cite journal|last1=Fukś|first1=Henryk|last2=Boccara|first2=Nino|title=Generalized deterministic traffic rules|journal=[[International Journal of Modern Physics|International Journal of Modern Physics C]]|volume=9|issue=1|year=1998|pages=1–12|url=http://www.tjhsst.edu/~ekoniecz/fuks.pdf|doi=10.1142/S0129183198000029|archiveurl=https://web.archive.org/web/20070927215541/http://www.tjhsst.edu/~ekoniecz/fuks.pdf|archivedate=27 September 2007|bibcode=1998IJMPC...9....1F|ref=harv}}
*{{cite journal|last1=Fukui|first1=M.|last2=Ishibashi|first2=Y.|title=Traffic flow in 1D cellular automaton model including cars moving with high speed|journal=[[Journal of the Physical Society of Japan]]|volume=65|issue=6|pages=1868–1870|doi=10.1143/JPSJ.65.1868|year=1996|bibcode=1996JPSJ...65.1868F|ref=harv}}
*{{cite book |last1=Gaylord |first1=Richard J. |last2=Nishidate |first2=Kazume |contribution=Traffic Flow |title=Modeling Nature: Cellular Automata Simulations with Mathematica |publisher=[[Springer-Verlag]] |year=1996 |pages=29–34 |isbn=978-0-387-94620-7 |ref=harv|和書}}
*{{cite journal|last1=Krug|first1=J.|last2=Spohn|first2=H.|title=Universality classes for deterministic surface growth|journal=[[Physical Review A]]|volume=38|issue=8|pages=4271–4283|year=1988|doi=10.1103/PhysRevA.38.4271|pmid=9900880|bibcode=1988PhRvA..38.4271K|ref=harv}}
*{{cite journal|last1=Land|first1=Mark|last2=Belew|first2=Richard|title=No perfect two-state cellular automata for density classification exists|journal=[[Physical Review Letters]]|volume=74|issue=25|year=1995|pages=1548–1550|doi=10.1103/PhysRevLett.74.5148|pmid=10058695|bibcode=1995PhRvL..74.5148L|ref=harv}}
*{{cite journal|last=Li|first=Wentian|title=Power spectra of regular languages and cellular automata|journal=[[Complex Systems (journal)|Complex Systems]]|volume=1|pages=107–130|year=1987|url=http://www.nslij-genetics.org/wli/pub/cs87-no-figure.pdf|ref=harv}}
*{{cite journal|last=Li|first=Wentian|title=Phenomenology of nonlocal cellular automata|journal=[[Journal of Statistical Physics]]|volume=68|issue=5–6|pages=829–882|year=1992|doi=10.1007/BF01048877|bibcode=1992JSP....68..829L|ref=harv}}
*{{cite journal|last1=Maerivoet|first1=Sven|last2=De Moor|first2=Bart|title=Cellular automata models of road traffic|journal=[[Physics Reports]]|volume=419|issue=1|pages=1–64|year=2005|doi=10.1016/j.physrep.2005.08.005|arxiv=physics/0509082|bibcode=2005PhR...419....1M|ref=harv}}
*{{cite journal|last=Moreira|first=Andres|title=Universality and decidability of number-conserving cellular automata|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=292|pages=711–721|year=2003|doi=10.1016/S0304-3975(02)00065-8|arxiv=nlin.CG/0306032|issue=3|ref=harv}}
*{{cite journal|last=Nagel|first=Kai|title=Particle hopping models and traffic flow theory|year=1996|journal=[[Physical Review E]]|volume=53|issue=5|pages=4655–4672|doi=10.1103/PhysRevE.53.4655|arxiv=cond-mat/9509075|bibcode=1996PhRvE..53.4655N|ref=harv}}
*{{cite journal|last1=Nagel|first1=Kai|last2=Schreckenberg|first2=Michael|title=A cellular automaton model for freeway traffic|journal=[[Journal de Physique]] I|volume=2|pages=2221–2229|year=1992|doi=10.1051/jp1:1992277|issue=12|bibcode=1992JPhy1...2.2221N|ref=harv}}
*{{cite journal|last=Pivato|first=M.|title=Defect particle kinematics in one-dimensional cellular automata|year=2007|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=377|issue=1–3|pages=205–228|doi=10.1016/j.tcs.2007.03.014|arxiv=math.DS/0506417|ref=harv}}
*{{cite book |last=Redner |first=Sidney |isbn=9780521652483 |page=288 |publisher=[[Cambridge University Press]] |title=A Guide to First-Passage Processes |contribution=8.5 Ballistic Annihilation |contribution-url=https://books.google.com/books?id=xtsqMh3VC98C&pg=PA288 |year=2001 |ref=harv|和書}}
*{{cite arXiv|last=Sukumar|first=N.|title=Effect of boundary conditions on cellular automata that classify density|year=1998|eprint=comp-gas/9804001}}
*{{cite journal|last1=Tadaki|first1=Shin-ichi|last2=Kikuchi|first2=Macato|title=Jam phases in a two-dimensional cellular automaton model of traffic flow|journal=[[Physical Review E]]|volume=50|year=1994|pages=4564–4570|doi=10.1103/PhysRevE.50.4564|issue=6|bibcode=1994PhRvE..50.4564T|ref=harv}}
*{{cite journal|last1=Wang|first1=Bing-Hong|last2=Kwong|first2=Yvonne-Roamy|last3=Hui|first3=Pak-Ming|title=Statistical mechanical approach to Fukui-Ishibashi traffic flow models|journal=[[Physical Review E]]|volume=57|issue=3|year=1998|pages=2568–2573|doi=10.1103/PhysRevE.57.2568|bibcode=1998PhRvE..57.2568W|ref=harv}}
*{{cite book |last=Wolfram |first=Stephen |authorlink=Stephen Wolfram |year=2002 |title=[[A New Kind of Science]] |publisher=[[Wolfram Media]] |ref=harv|和書}}
{{refend}}

== 外部リンク ==
* [http://atlas.wolfram.com/01/01/184/ Rule 184 in Wolfram's atlas of cellular automata]

{{DEFAULTSORT:るうる184}}
[[Category:セル・オートマトン]]
[[Category:数学に関する記事]]