箱玉系について

はじめに

総合数理AdventCalenderがいつの間にか始まっていたので、自分もノリで参加することに。 何回かに分けて、"箱玉系"や”超離散化法"といった事柄について軽く触れていこうと思う。本稿では、超離散の発見の元となった箱玉系を紹介する。

本稿の目標

箱玉系について知ってもらう。

背景

まず、事前知識としてCAとSolitonの説明から。

CA (Cellular Automata, セルオートマトン)

CAは、"離散的な発展方程式"で表される。 (e.g. $u_n^{t+1}=f(u_{n-1}^t, u_n^t, u_{n+1}^t)$)
すなわち、CAとは
次の時間($t+1$)におけるセルの状態が
今の時間($t$)におけるセルの状態によって決まる、計算モデル。
(状態とは、"0"か"1"の値、もしくはその他整数を考える。)

2次元CAの有名なものに、 ライフゲーム (Conway's Game of Life)がある。

(wikipedia/Conway's_Game_of_Life)

以下は、1次元のものについて見ていく。

ECA (Elementaly Cellular Automata)

1次元CAの最も単純なものは、ECA (Elementaly Cellular Automata)と呼ばれる。
次の時間でのセルの状態(0 or 1)が
前の時間でのそのセルの状態とその両隣のセルの状態から決まるようなCAで、
ルールは$2^8=256$通りある。全ての型はそのルールによって名前がつけられている。

e.g. Rule90のECA

	0	1	2	3	4	5	6	7
時間$t$での $n-1,n,n+1$	000	001	010	011	100	101	110	111
時間$t+1$での$n$	0	1	0	1	1	0	1	0

(Ruleの番号 $90 = 2^1+2^3+2^4+2^6$)

シェルピンスキーのギャスケットとして有名な下の形は、Rule90のECAによって作られる。

(wikipedia/Sierpinski_triangle)

Filter型CA (Filter Automata)

先ほどまでのCAは、時間t+1における状態を得るためには、時間tの状態がわかっていれば十分である。それに対しFilter型CAは、
時間$t+1$における状態を得るために、
時間$t+1$の状態をも必要とするようなCAである。
その性質から、処理を左から順に行うことが多い (ECAはどこから処理しても変わらない)。

Soliton (ソリトン, 孤立波)

Solitonとは、
波の形状、速度が変わらず、
互いに衝突しても衝突の前後で各波の形状を保つ ような波のことである。
他に、性質として波の大きさによって速度が変わり、一般に波の大きい方が速度も大きい。

津波なんかもこれで説明できる(らしい)。
(こんなの)

箱玉系 (Box&ball system)

一言で言えば、「ソリトン的性質を持つ1次元Filter型CA」
箱と玉により説明されるので、箱玉系と呼ばれるようになった。

箱玉系のルール

箱玉系の性質

箱玉系は、Solitonの性質を持っている。
玉の塊を一つの波とみなすと、波が衝突した前後でそれぞれの波が保存されているのがわかる(右下に3つの玉がないのは見切れてるから..)。また、玉の数を波の大きさとすれば、波の大きさに速度が比例していることも見て取れる。

まとめ

箱玉系は、

• Filter型CAである。
• 一番近い空箱に玉を移動させるルールで表される。
• Solitonの性質を持つ。