|
セル・オートマトン（、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。 正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「」「」「」といった呼称もある。 有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 ''t''においてのセルの状態、および近傍のセルの内部状態によって、次の時刻''t'' + 1 、すなわち新たな「ジェネレーション」（世代）での各セルの状態が決定される。初期状態（時刻 ''t'' =0）は、各セルの状態を設定することで選択される。次の世代（''t'' が1に進んだ状態）は、事前に設定された「規則」（一般に何らかの数学的関数）に従って初期状態でのそのセルおよび近傍の状態から決定される。セルの状態を更新する規則は一般にどのセルでも同一であり、途中で変更されず、並んでいる全セルに同時に適用される。ただしや非同期セル・オートマトンは例外である。 その概念は1940年代、ロスアラモス国立研究所で同僚だったスタニスワフ・ウラムとジョン・フォン・ノイマンが発見した。その後細々と研究されていたが、1970年代に2次元セル・オートマトンの一種ライフゲームが登場すると注目されるようになった。1980年代にはスティーブン・ウルフラムが1次元セル・オートマトンまたはを体系的に研究し、一部の規則群がチューリング完全であることを示した。彼が2002年に出版した ''A New Kind of Science'' では、セル・オートマトンが様々な科学の領域で応用できると主張している。 == 概要 == 2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる方眼紙を考える。方眼紙のひとつのマス目がセルにあたる。それぞれのセルは「黒」と「白」の2つの内部状態をもつ。セルの「近傍」とは、そのセルの周辺のセル群であり、通常は隣接するセルを指す。近傍には、とという2種類の典型的な定義がある。前者はセル・オートマトンの考案者の名を冠しており、直交して接する4つのセルを近傍とする〔。後者はフォン・ノイマン近傍を含み、さらに斜め方向の4つのセルも加えた中心のセルを囲む8つのセルの状態を考慮する〔。ムーア近傍の場合、それら9つのセルが取ることができる状態は全部で29 = 512個存在する。セル・オートマトンがどのように時間発展していくかのルールは表として与えられる。すなわち次の時間ステップ(t+1)で、中心のセルが「黒」「白」いずれになるかは、現在の時間ステップ(t)でとり得る512個のパターンそれぞれについての一覧表によって決定される。ライフゲームはこのモデルの有名な例である。もう1つのよく知られている近傍の定義として「拡張フォン・ノイマン近傍」があり、直交する4方向それぞれの最も近い2つのセルを近傍とし、全部で8つのセルを近傍とする〔。セルがとりうる状態数を ''k''、次の状態を決定するのに使われる近傍のセル数（自身も含める場合がある）を ''s'' とすると、このようなシステムの規則は ''k''''k''''s'' という式で表される。したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 229 または となる。 例えば1次元セル・オートマトンでは、時刻（ステップ）を ''t''、位置を1次元の ''i'' としたとき、セル ''xit'' の近傍は となる。 2次元のセル・オートマトンで最も有名なものがライフゲームである。ライフゲームは以下のようなルールで記述される。 * 誕生: 死んでいるセル（「白」）の周囲に3つの生きているセル（「黒」）があれば次の時間ステップでは生きる（「黒」になる）。 * 維持: 生きているセル（「黒」）の周囲に2つか3つの生きているセル（「黒」）があれば次の世代でも生き残る（「黒」のままである）。 * 死亡: 上以外の場合には次の世代では死ぬ（「白」になる）。 このライフゲームのルールは細菌などの生物の繁殖のアナロジーである。すなわち、孤独でも人口過密でも死んでしまう。最も快適な人口密度では子孫を残し繁栄するというものである。実際ライフゲームは生物の増殖のような複雑で多様な振舞いを示す。 一般に、各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始する。これを「コンフィギュレーション」と呼ぶ。また、全体が周期的なパターンを形成していて、一部がそのパターンから外れた状態で開始するということもある。後者は1次元のセル・オートマトンでは一般的である。 セル・オートマトンのシミュレーションには有限の格子を使うことが多い。2次元の場合、無限の平面ではなく、有限の四角形で表される。有限の格子での明らかな問題は端のセルをどう扱うかである。端をどう扱うかが格子全体のセルの状態に影響を与える。1つの手法は、端のセルを全て変化しない定数を状態として持つとするものである。別の手法は端のセルの近傍を一般のセルとは違う内容にするというものである。つまり、端のセルの近傍を通常より少なく定義することもできるが、その場合は規則も新たに定義しなければならない。別の手法として、2次元の場合に四角形の平面の端の上下と左右を繋げて、トーラス形にすることもある。これは、ある意味で無限の平面が同じ四角形で平面充填されていることになる。1次元であれば、線の端を繋いでループにすることになる。これは端の問題を回避するために行うが、モジュロ演算関数を使って容易にプログラム可能という利点もある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「セル・オートマトン」の詳細全文を読む スポンサード リンク
|