この記事は良質な記事に選ばれています

セル・オートマトン

提供: miniwiki
移動先:案内、検索
ファイル:Gospers glider gun.gif
セル・オートマトンの一種ライフゲームで、ゴスパー（English版）のグライダー銃がグライダーを放っているところ[1]

セル・オートマトン（英: cellular automaton、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。

正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「homogeneous structure」「tessellation structure」「iterative array」といった呼称もある[2]。

有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 t においてのセルの状態、および近傍のセルの内部状態によって、次の時刻t+1 、すなわち新たな「ジェネレーション」（世代）での各セルの状態が決定される。初期状態（時刻 t=0）は、各セルの状態を設定することで選択される。次の世代（t が1進んだ状態）は、事前に設定された「規則」（一般に何らかの数学的関数）に従って初期状態でのそのセルおよび近傍の状態から決定される。セルの状態を更新する規則は一般にどのセルでも同一であり、途中で変更されず、並んでいる全セルに同時に適用される。ただし確率的セル・オートマトン（English版）や非同期セル・オートマトンは例外である。

その概念は1940年代、ロスアラモス国立研究所で同僚だったスタニスワフ・ウラムとジョン・フォン・ノイマンが発見した。その後細々と研究されていたが、1970年代に2次元セル・オートマトンの一種ライフゲームが登場すると注目されるようになった。1980年代にはスティーブン・ウルフラムが1次元セル・オートマトンまたは基本セル・オートマトン（English版）を体系的に研究し、一部の規則群がチューリング完全であることを示した。彼が2002年に出版した A New Kind of Science では、セル・オートマトンが様々な科学の領域で応用できると主張している。

概要

ファイル:Vierer-Nachbarschaft.png
フォン・ノイマン近傍（DがPの近傍）

2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる方眼紙を考える。方眼紙のひとつのマス目がセルにあたる。それぞれのセルは「黒」と「白」の2つの内部状態をもつ。セルの「近傍」とは、そのセルの周辺のセル群であり、通常は隣接するセルを指す。近傍には、四方を近傍とするフォン・ノイマン近傍（English版）と八方を近傍とするムーア近傍（English版）という2種類の典型的な定義がある[3]。前者はセル・オートマトンの考案者の名を冠しており、直交して接する4つのセルを近傍とする[3]。後者はフォン・ノイマン近傍を含み、さらに斜め方向の4つのセルも加えた中心のセルを囲む8つのセルの状態を考慮する[3]。ムーア近傍の場合、それら9つのセルが取ることができる状態は全部で29 = 512個存在する。セル・オートマトンの時間発展の様子を表すルールは表で与えられる。すなわち次の時間ステップ（ t+1 ）で、中心のセルが「黒」「白」いずれになるかは、現在の時間ステップ（ t ）でとり得る512個のパターンそれぞれについての一覧表により決定される。ライフゲームはこのモデルの有名な例である。もう1つのよく知られている近傍の定義として「拡張フォン・ノイマン近傍」があり、直交する4方向それぞれの最も近い2つのセルを近傍とし、全部で8つのセルを近傍とする[3]。セルがとりうる状態数を k、次の状態を決定するのに使われる近傍のセル数（自身も含める場合がある）を s とすると、このようなシステムの規則は kks という式で表される[4]。したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 229 または {{safesubst:#invoke:val|main}} となる。

例えば1次元セル・オートマトンでは、時刻（ステップ）を t、位置を1次元の i としたとき、セル xit の近傍は {xi−1t−1, xit−1, xi+1t−1} となる。

2次元のセル・オートマトンで最も有名なものがライフゲームである。ライフゲームは以下のようなルールで記述される。

  • 誕生: 死んでいるセル（「白」）の周囲に3つの生きているセル（「黒」）があれば次の時間ステップでは生きる（「黒」になる）。
  • 維持: 生きているセル（「黒」）の周囲に2つか3つの生きているセル（「黒」）があれば次の世代でも生き残る（「黒」のままである）。
  • 死亡: 上以外の場合には次の世代では死ぬ（「白」になる）。

このライフゲームのルールは細菌などの生物の繁殖のアナロジーである。すなわち、孤独でも人口過密でも死んでしまう。最も快適な人口密度では子孫を残し繁栄する性質を持つ。実際、ライフゲームは生物の増殖のような複雑で多様な振舞いを示す。

一般に各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始する。これを「コンフィギュレーション」と呼ぶ[5]。また、全体が周期的なパターンを形成し、一部がそのパターンから外れた状態で開始する場合もある。後者は1次元のセル・オートマトンでは一般的である。

ファイル:Torus.png
トーラス

多くのセル・オートマトンのシミュレーションでは有限の格子を使う。2次元の場合、無限の平面ではなく、有限の四角形で表される。有限の格子での明らかな問題は端のセルの扱いであり、端のセルの扱いが格子全体のセルの状態に影響を与えるため重要な問題である。1つの手法は、端のセルを全て変化しない定数を状態として持つとする手法である。別の手法は端のセルの近傍を一般のセルとは違う内容にする手法である。つまり、端のセルの近傍を通常より少なく定義できるが、その場合は規則も新たに定義する必要がある。別の手法として、2次元の場合に四角形の平面の端の上下と左右を繋げて、トーラス形にする手法もある。これは、ある意味で無限の平面が同じ四角形で平面充填されている状態に近い。1次元であれば、線の端を繋いでループにする空間に相当する。これは端の問題を回避するために行うが、モジュロ演算関数を使って容易にプログラム可能という利点もある。

歴史

ファイル:John von Neumann ID badge.png
ロスアラモス国立研究所のIDバッジをつけたジョン・フォン・ノイマン

1940年代にロスアラモス国立研究所で働いていたスタニスワフ・ウラムは結晶の成長について研究していたとき、モデルとして単純な格子ネットワークを使用していた[6]。同じころロスアラモスで一緒に働いていたジョン・フォン・ノイマンは自己複製機械を研究していた[7]。フォン・ノイマンはまず、あるロボットの記述に基づいて別のロボットの記述を行うという設計を考えていた。この設計は運動学モデル（Kinematic model）と呼ばれている[8][9]。設計を進めるに連れ、フォン・ノイマンは、複製を作るための「部品の海」をロボットに与えることのコストの膨大さやあるロボットが別のロボットを作るということを記述する大変さを徐々に理解していった。ノイマンは1948年の Hixon Symposium にて "The general and logical theory of automata" と題した論文を読む[7]。またウラムはフォン・ノイマンに自己複製の還元主義的モデルとして離散系を使ってはどうかと示唆した[10][11]。Nils Aall Barricelli はそういったモデルを使って人工生命を研究していた。

1950年代、ウラムとノイマンは液体の動きを計算する方法を生み出した。その中心となった考え方は液体を離散的単位の集まりとみなすということで、各単位の動作をその近傍の挙動に基づいて計算する[12]。それらが元となってセル・オートマトンが生まれた。ウラムの格子ネットワークのように、フォン・ノイマンのセル・オートマトン（English版）は2次元で、その中に自己複製機械がアルゴリズム的に埋め込まれた。これがユニバーサルコンストラクタ（English版）であり、近傍として隣接する4つのセルのみ（ノイマン近傍）を考慮し、1つのセルあたり29の内部状態を持っている[13]。このモデルで彼は自己複製機械として動作するパターンを20万個のセルを使ってデザインし、それが無限に自己複製を繰り返すことを数学的に証明した[13]。この設計は平面充填モデルとして知られている[14]。1968年、エドガー・F・コッドは 8 状態で自己複製を繰り返すコッドのセル・オートマトンを考案している。

同じく1940年代、ノーバート・ウィーナーとアルトゥーロ・ローゼンブリュート（English版）がセル・オートマトンを開発し興奮性媒質（English版）のモデルに採用した[15]。その具体的な目的は、心筋におけるインパルス伝導の数学的説明であった。その業績は不整脈や興奮性媒質についての後の研究でよく引用されている[16]。

1960年代、セル・オートマトンは力学系の特殊形として研究され、数学の一分野である記号力学（English版）と関連して研究され始めた。1969年、グスタフ・A・ヘドランド（English版）はその観点で数多くの成果をまとめ[17]、それがセル・オートマトンの数学的研究における重要な論文とされている。

1969年、ドイツのコンピュータのパイオニアの1人であるコンラート・ツーゼは、著書 Calculating Space の中で、宇宙の物理法則は本質的には離散的であり、宇宙全体が一種の巨大なセル・オートマトン上の決定的な計算の結果であると主張した。この著書が今日デジタル物理学と呼ばれている分野の基礎を築いた[18]。

1970年代、2状態で2次元のセル・オートマトンであるライフゲームが特にコンピュータコミュニティでよく知られるようになった。ジョン・コンウェイの発明によるもので、マーティン・ガードナーがサイエンティフィック・アメリカン誌（日本では日経サイエンス誌）で紹介したことで有名となったのである[19]。ライフゲームは単純だが、システムとして興味深い挙動を示し、ランダム性と規則性の間で変動する。ライフゲームの最も顕著な特徴として「グライダー」（格子を横断して移動していくセル群）が頻繁に発生することが挙げられる。グライダーをうまく配置すると一種の相互作用が生まれる。長年の研究により、ライフゲームがチューリングマシンをエミュレートできることが判明した[20]。それが単なる趣味の話題と受け止められたためか、ライフゲームの特殊性の研究や関連する規則の研究が若干行われた以外、この発見を受けた研究はなされなかった。

1981年、熱力学第二法則に反するように見える自然界の様々な複雑なパターンを検討していたスティーブン・ウルフラムは、セル・オートマトンの研究を始めた[21]。当初の動機はセル・オートマトンで神経ネットワークなどのシステムをモデリングできるのではないかというものだった[21]。1983年6月、Reviews of Modern Physics 誌にて基本セル・オートマトン（English版）（特にルール30）についての最初の論文を発表[21]。ウルフラムは、単純な規則で示される振る舞いの予期せぬ複雑さを見て、自然界の複雑さも同様の機構によって生まれているのではないかと考えた[21]。しかし、彼の研究によってセル・オートマトンは神経ネットワークのモデリングには貧弱すぎることが判明した[21]。さらにウルフラムは真の無作為性と計算既約性（English版）の概念を定式化し[22]、ルール110（English版）がチューリング完全であると推測した（1990年代にウルフラムの助手 Matthew Cook がそれを証明した）。

ウルフラムは1980年代中盤以降に学界を去ってMathematicaを開発し、彼のそれまでの研究結果を広い範囲の単純で抽象的な系に拡張して適用するのに Mathematica を使った。2002年、ウルフラムはそれらの成果を1280頁の著書 A New Kind of Science として発表した。この中でセル・オートマトンがあらゆる科学にとって重要な関わりを持つことを主張している。一部で誤解されているように、同書は物理法則がセル・オートマトンに基づいているとは言っていない（ツーゼとは異なる）が、セル・オートマトンに基づいた物理モデルをいくつか記述しており、他にも各種抽象系に基づいたモデルを示している。

分類

ウルフラムはあらゆる1次元のセル・オートマトンの時間発展の仕方を調べ上げ、セル・オートマトンを含む単純な計算モデルの4つのクラスを定義した。それまでのセル・オートマトンの研究では、パターンの種類から規則群を分類する傾向があったのに対して、ウルフラムの分類は規則自体を分類する最初の試みだった。4つのクラスは次の通りである。

  • クラス1 - 秩序状態。ほぼ全ての初期状態で素早く安定した均質な状態になる。初期状態に無作為性があっても消滅する[23]。
  • クラス2 - 秩序状態。ほぼ全ての初期状態で素早く安定状態または周期的に振動する状態になる。初期状態の無作為性は消滅する場合もあるが、残存する場合もある。初期状態を部分的に変更した場合、その影響は局所的となる傾向がある[23]。
  • クラス3 - カオス状態。ほぼ全ての初期状態でセル全体がランダムな変化を続ける。安定した構造が現れても、すぐに周囲のノイズによって破壊される。初期状態の部分的変更は全体に拡散していく傾向がある[23]。
  • クラス4 - ほぼ全ての初期状態で規則的なパターンとランダムなパターンが共存し、複雑なパターンを形成する。局所的に形成された構造は長期間存続することができる[24]。

秩序状態であるクラス1、クラス2は新しい変化を生み出さない、いわば死んだ世界である。カオス状態であるクラス3はランダムすぎて、意味のある情報を生み出すことができない。ウルフラムは秩序状態とカオス状態の間にあるクラス4の様な状態こそが、生命現象などの現実世界で見られる複雑な現象を引き起こす源だと考えた。この研究により、複雑系と呼ばれる新しい科学分野の基盤が確立した。

これらの定義は質的なもので、その解釈には若干の幅がある。ウルフラムは「どんな一般分類体系でも、ある定義ではこのクラスになるが、別の定義では別のクラスになるというケースが必然的に存在する。セル・オートマトンでもそれは変わらない。あるクラスの特徴と別のクラスの特徴を備えた規則群は時として存在する」としている[25]。ウルフラムの分類は、セル・オートマトンの出力を圧縮した長さの分類と経験的に合致している[26]。

CulikとYuによって、ウルフラムの4つのクラスの算術的階層における位置が証明されている。クラス1と2は[math]\Pi^0_2[/math]-完全、クラス3は[math]\Sigma^0_3[/math]-完全に所属する。

ウルフラムの分類に触発され、CAを形式的に厳密に分類しようとする試みもなされてきた。例えば、CulikとYuは3つのwell-definedなクラス（そしてそれらのどれにも分類されない4番目のクラス）を提案した。これを Culik-Yu クラスなどと呼び、ある規則群がどのクラスに属するかの判定は決定不能だと証明された[27][28][29]。

可逆型

現在状態から1つ前の状態（プレイメージ）が一意に求められるセル・オートマトンを「可逆的」(reversible) であるという[30]。セル・オートマトンを状態から状態への関数と考えると、可逆性はその関数が全単射であることを意味する[30]。可逆型のセル・オートマトンは、時間を遡った際の挙動もセル・オートマトンとして記述できる。これは、セル・オートマトンを位相幾何学的に説明したカーティス-ヘドランド-リンドンの定理（English版）の帰結である[31][32]。可逆でない有限のセル・オートマトンには、どんな状態からも絶対生成（到達）できない配置が存在する。そのような配置を「エデンの園配置」と呼ぶ[33]。換言すれば、エデンの園パターンにはプレイメージが存在しない。

1次元のセル・オートマトンについては、プレイメージを探すアルゴリズムが知られていて、各ルールについて可逆的かそうでないかは既に判明している[34][35]。2次元以上のセル・オートマトンについては、任意のルールの可逆性は決定不能であることが証明されている。Jarkko Kari による証明は、ワンのタイル（English版）のタイル並べ問題と関連している[36]。

可逆型セル・オートマトンは、熱力学の法則に従う気体や液体の力学現象のシミュレーションに使われることが多い。その場合のセル・オートマトンは特別に可逆性を持つよう設計される。この種のシステムの研究者としてトマソ・トフォリやノーマン・マーゴラス（English版）らがいる。意識的に可逆型セル・オートマトンを作る手法はいくつか存在する。二階セル・オートマトン（English版）やブロック・セル・オートマトン（English版）がそれで、どちらもセル・オートマトンの定義に何らかの修正を施す。これらは厳密には上に挙げたようなセル・オートマトンの定義から外れているが、十分に大きな近傍と多数の状態を持つ従来型のセル・オートマトンでエミュレートできることが判っており、従来型のセル・オートマトンのサブセットと見なすことができる。逆に全ての可逆型セル・オートマトンはブロック・セル・オートマトンでエミュレートできる[37][38]。

総和型

特殊なセル・オートマトンとして、総和型 (totalistic) セル・オートマトンがある。総和型セル・オートマトンでの各セルの状態は数値で表され（通常、有限個の整数値）、時刻 t におけるセルの値は、時刻 t−1 における近傍（自身も含むこともある）のセル群の値の総和だけに依存して決定される[39][40]。時刻 t におけるセルの状態が自身の t−1 での状態に依存する場合、そのようなセル・オートマトンを「外部総和型」(outer totalistic) と呼ぶ[40]。ライフゲームは、値として 0 と 1 をとる外部総和型のセル・オートマトンの例である。同じく外部総和型でムーア近傍だが、規則をライフゲームとは変えたセル・オートマトンを欧米では "life-like" と呼ぶ[41][42]。

その他

CAの概念は様々な拡張が可能である。

ファイル:Oscillator.gif
六角形のセルに基づくセル・オートマトン（ルール34/2）

例えば、矩形の格子ではなく別の多角形を使うという拡張がある。例えば六角形を平面に敷き詰めたとき、個々の六角形をセルとして扱うことができる。多くの場合そのようなセル・オートマトンは、矩形格子で近傍と規則をうまく調整したものと等価である。他にもペンローズ・タイルのような平面充填で格子を形成することもできる[43]。

また、規則を決定的なものではなく確率的なものにする拡張もある。そのようなCAを確率的セル・オートマトン（English版）と呼ぶ。この場合、時刻 t のパターンから時刻 t+1 のとりうる各パターンの遷移確率が確率的規則により指定される。もっと単純な規則を使うこともあり、例えば「基本的にライフゲームの規則に従うが、毎回0.001%の確率で本来とは反対の色になる」といった規則を設定する。

時間や場所によって近傍の定義や規則を変化させるという拡張もある。例えば、最初の世代では水平方向の隣接したセルを近傍とするが、次の世代では垂直方向の隣接するセルを近傍とする、といった具合である。

CAでは、あるセルの新たな状態は、他のセルの新たな状態に影響されない。この原則を変更することもできる。

連続値セルオートマトン（English版）と呼ばれるものもある。総和型と似ているが、規則や状態が離散値ではなく連続な値（一般に単位区間の値）を用いる。つまり、セルの状態は有限個の実数で表される。例えば、液体における拡散パターンのモデルなどに使われる。

Continuous spatial automata では位置が連続的である。ある位置の状態は有限個の実数である。時間も連続的に推移し、状態は微分方程式にしたがって変化する。重要な例として反応拡散系があり、アラン・チューリングはシマウマの縞模様やヒョウのドット模様を生み出した化学反応を説明する微分方程式を提案した[44]。そのようなパターンをCAで近似的に生成することも可能である。continuous spatial automata でライフゲームのグライダーのような現象が生じる例も知られている[45]。

1次元セル・オートマトン

最も単純だが自明ではないCAは、1次元で各セルは2つの状態をとることができ、近傍は両側に接している隣のセルという場合である。あるセルとその両側の3つのセルで近傍を構成するので、1つの近傍がとりうるパターンは 23=8 種類となる。規則はそれらパターンについて、そのセルが次世代に1と0のどちら状態となるかを決定する。したがって規則群の組合せは 28=256 通り存在する[4]。それら256種類のCAは一般にウルフラムが考案した0から255までのルール番号で参照され、これをウルフラム・コード（English版）と呼ぶ。これら256種類のCAはいくつかの論文で研究・比較されている。ルール30とルール110（English版）のCAは特に興味深い。下図は、1カ所だけ1にした初期状態からのそれらCAの変化の様子を示している。図の各行がCAの1世代の履歴であり、一番上の行が t =0 である。各ピクセルは、0を白、1を黒で描画している。

ルール30セル・オートマトン

ファイル:CA rule30s.png
現在の状態 中央のセルの次の状態
000
*0*
001
*1*
010
*1*
011
*1*
100
*1*
101
*0*
110
*0*
111
*0*

ルール110セル・オートマトン

ファイル:CA rule110s.png
現在の状態 中央のセルの次の状態
000
*0*
001
*1*
010
*1*
011
*1*
100
*0*
101
*1*
110
*1*
111
*0*

例えば「ルール30」と呼ばれるのは、上の表のように時刻t+1における中央のセルの内部状態一覧を並べると0,0,0,1,1,1,1,0となっており、この2進数の数を10進数に直すと30であるためであり、これをウルフラム・コード（English版）と呼ぶ。

ルール30は「クラス3」の挙動を示し、単純な初期状態からもカオス的な経過を示し、無作為な履歴になっている。

ルール110はライフゲームのように「クラス4」の挙動を示し、完全な無作為でもなく、完全な反復でもない。局所的構造が現れ、様々な複雑な形で相互作用する。1994年ウルフラムの研究助手だったマシュー・クックは、それら構造の一部がチューリング完全性をサポートするのに十分であることを証明した。ルール110は非常に単純な1次元のシステムであり、具体的なことを実行するよう設計するのは困難であるため、この成果は興味深い。この結果からウルフラムはクラス4のセル・オートマトンが本質的にチューリング完全である可能性を示唆した。1998年、セル・オートマトンの学会がサンタフェ研究所で開催され、クックはその成果を発表したが、ウルフラムは A New Kind of Science の出版前にその証明の詳細を公表したくなかったため、証明の詳細は発表されなかった[46]。2004年、Cookの証明がウルフラムの発行する雑誌 Complex Systems (Vol. 15, No. 1) で発表された。実に証明してから10年が経過している。ルール110をベースとして極小の万能チューリングマシンが構築されている[47]。

ルール90

また、ルール90の1次元セル・オートマトンは典型的なフラクタル図形であるシェルピンスキーのギャスケットを生成する。（WolframAlphaでルール90を見る→rule 90）

ファイル:SierpinskiTriangle.PNG
シェルピンスキーのギャスケット
現在の状態 中央のセルの次の状態
000
*0*
001
*1*
010
*0*
011
*1*
100
*1*
101
*0*
110
*1*
111
*0*

生物学における例

ファイル:Textile cone.JPG
イモガイの一種タガヤサンミナシのセル・オートマトン状模様の貝殻[48]

一部の生物学的過程はセル・オートマトンでシミュレートできる。

イモガイやガクフボラといった貝の貝殻の模様はセル・オートマトンの描くパターンによく似ている。貝殻の辺縁に狭い帯状に色素細胞がある。各色素細胞は活性化されると色素を分泌し、同時に近傍の色素細胞の活性化を阻害するようになっており、天然のセル・オートマトンの規則のように作用する[48]。この色素細胞の帯が貝殻に色の模様を残しつつ、少しずつ貝殻が成長していく。例えば、イモガイの一種タガヤサンミナシはウルフラムが研究したルール30CAとよく似た模様である[48]。

植物はCA的機構で気体の吸入と排出を行っている。葉に多数存在する気孔がセル・オートマトンのセルのように振る舞う[49]。

頭足類は表皮に色素胞があり、体表の模様を変化させるが、これを2状態で2次元のセル・オートマトンでシミュレートできる。各状態は色素胞を広げた状態と縮めた状態に対応する[50]。

神経細胞をシミュレートするしきい値型CAが考案されており、認知や学習といった複雑な挙動をシミュレートできる。

線維芽細胞もセル・オートマトンと似た挙動を示す。個々の線維芽細胞はその近傍の細胞としか相互作用しない[51]。

化学における例

ベロウソフ・ジャボチンスキー反応はセル・オートマトンを使ってシミュレートできる。1950年代、A・M・ジャボチンスキーはソ連のB・P・ベロウソフ（English版）の研究成果をさらに進め、マロン酸、酸化した臭素酸塩、セリウム塩の混合物の薄い均一な層を置いておくと、同心円や渦巻き模様などの幾何学的模様が生じることを発見した。1988年8月、サイエンティフィック・アメリカン（日本では日経サイエンス）誌上の "Computer Recreation" という記事で[52]、A. K. Dewdney はベロウソフ・ジャボチンスキー反応に非常によく似た挙動を示すセル・オートマトンを紹介した[53]。ベロウソフ・ジャボチンスキー反応が、分子レベルでそのセル・オートマトンと同じような仕組みで発生しているのかどうかは不明である。これまで、セル・オートマトン的な化学反応が自然界で観察されたことはない。そのような化学反応は全て研究室や実験室でのみ観測されている。

物理における例

ソリトンのようなふるまいを見せる、箱玉系と呼ばれているセル・オートマトンがある。

応用

並列コンピュータ

離散的(非連続的)時間で記述され、時刻t+1における1つのセルの内部状態は、時刻tにおける状態によって決定されるといった点で、セル・オートマトンはチューリングマシンとよく似ている。実際、万能チューリングマシンと等価な動作をするセル・オートマトンが存在することが知られている。しかし、チューリングマシンは「逐次的な処理を行うデジタルコンピュータ」のモデルであるのに対し、セル・オートマトンは各セルが並列に演算処理を実現しており、いわば "並列コンピュータ" であるという点で大きく異なる。

セル・オートマトンの概念をハードウェアで実装して情報処理を行おうとする試みも行われている。処理要素は格子状に配置され、2次元か3次元の平面充填構造とされる。それ以外の並べ方も可能だが、まだ試されたことはない。各処理要素（すなわちセル）は隣接する少数のセルだけとやり取りする。遠いセルとの直接通信手段は存在しない。セルの相互作用には、電荷、磁化、振動などの物理的な手段を使う。いずれにしても各処理要素間を結線する必要はない。これは、今日のノイマン型コンピュータのプロセッサとはかなり違う。

例えばシストリックアレイ（English版）はCAプロセッサアレイの一例である。

遺伝的アルゴリズムを使った進化するセル・オートマトン

センサーネットワークやさらに微細な構造をネットワークとして設計し、分散処理を行わせることに関心が集まっている。分散システムを使い大域的なレベルで情報処理するという考え方から創発計算というアイデアが生まれた[54]。ポートランド州立大学の教授でサンタフェ研究所にも所属しているメラニー・ミッチェル（English版）[55]は、そのために自己進化するセルの格子を使うアイデアに取り組んでいる[54]。ミッチェルらはセル格子のプログラムに進化的アルゴリズムを採用している[56]。分散型システムにおける計算は古典的なコンピュータとは大きく異なり、大域的および局所的なパターンの変化という形で情報処理がなされる。

この手法の発想の元になっているのは、社会性昆虫、神経系、経済システムといった自然界に見られる複雑なシステムである[56]。研究の焦点は、進化する分散型システムでいかにして計算が発生するかを解明することである。モデルを構築しどのようにして創発計算が生じるかを解明するため、ミッチェルらはセル・オートマトン内のパターンを進化させるべく遺伝的アルゴリズム (GA) を適用した。既にGAによって洗練された創発計算戦略が生じる規則を発見している[57]。ミッチェルらが採用したのは1次元2値で6個の近傍を持つセル・オートマトンである。先頭と末尾は繋がっているので、環状になっている。

乱数

2次元セル・オートマトンを擬似乱数発生に使った例がある。[58]

暗号

ルール30は、ブロック暗号に応用可能という提案がある。[59]

セル・オートマトンを公開鍵暗号に使うという提案もある。[60]

誤り訂正符号

セル・オートマトンを誤り訂正符号の設計に応用した例として、D. Roy Chowdhury、S. Basu、I. Sen Gupta、P. Pal Chaudhuri の論文 "Design of CAECC - Cellular Automata Based Error Correcting Code" がある。この論文ではセル・オートマトンを使って SEC-DED符号（1ビット誤り訂正-2ビット誤り検出符号）を構築する新たな手法が定義されており、その符号の高速ハードウェアデコーダも報告されている。

物質世界の基盤のモデルとしてのCA

"「デジタル物理学」"

Andrew Ilachinski は著書 Cellular Automata で、多くの学者が宇宙自体がセル・オートマトンなのではないかという疑問を投げかけていると指摘した[61]。Ilachinskiは、この問題の重要性を示すには簡単な観察をしてみるのがよいと主張し、例えばルール110（English版）の発展するパターンをどうやったらうまく説明できるか考えてみるのがよいとした[62]。そして、もしそのイメージの生成方法を知らないとしたら、何らかの粒子状のオブジェクトの運動の軌跡ではないかと推測するだろうと述べている。実際、物理学者 James Crutchfield はその考え方から厳密な数学的理論を構築した[63]。この考え方を推し進めていくと、素粒子物理学で説明されている我々の世界も根底ではCAと見なせるのではないかという考え方に到達する。

その考え方に沿った理論はまだ発展途中だが、この仮説に興味を惹かれた学者らが離散的フレームワークで世界を理解することについて興味深い憶測と有益な直観を示している。AI研究者マービン・ミンスキーは、4次元CA格子で素粒子の相互作用を理解する方法を研究した[64]。コンピュータの先駆者コンラート・ツーゼは、素粒子の持つ情報についての問題を解くため、不規則な格子を考案した[65]。またエドワード・フレドキンは "finite nature hypothesis" と名付けた仮説を提唱。「最終的に時間や空間を含む全ての物理量は離散的で有限だと判明するだろう」とした[66]。フレドキンとウルフラムはデジタル物理学の信奉者である。

21世紀に入ると、非標準計算についての著作からこの考え方に沿った示唆が生まれている。ウルフラムの A New Kind of Science では、CAが物理学を含めた様々な主題を理解する鍵だとしている。（Francesco Berto が創始し、Gabriele Rossi と Jacopo Tagliabue が発展させた）iLabs[67]が2010年に出版した Mathematics Of the Models of Reference では「菱形十二面体」をベースとする格子と独特の規則で2次元および3次元の宇宙を説明するモデルを提案している。このモデルはチューリングマシンと等価であり、完全な可逆性を有し（様々な量を保存し、情報を決して失わない）、宇宙の発展についての質的な論述を計算できる論理が組み込まれている[68]。

ポップカルチャーにおけるセル・オートマトン

具体例

脚注

  1. ↑ Daniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X
  2. ↑ Wolfram, Stephen (1983). “Statistical Mechanics of Cellular Automata”. Reviews of Modern Physics 55 (3): 601–644. Bibcode 1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601. http://www.stephenwolfram.com/publications/articles/ca/83-statistical/. 
  3. ↑ 3.0 3.1 3.2 3.3 Kier, Seybold & Cheng 2005, p. 15
  4. ↑ 4.0 4.1 Bialynicki-Birula & Bialynicka-Birula 2004, p. 9
  5. ↑ Schiff 2011, p. 41
  6. ↑ Pickover, Clifford A. (2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc. ISBN 978-1402757969. 
  7. ↑ 7.0 7.1 Schiff 2011, p. 1
  8. ↑ John von Neumann, “The general and logical theory of automata,” in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1-31.
  9. ↑ John G. Kemeny, “Man viewed as a machine,” Sci. Amer. 192(April 1955):58-67; Sci. Amer. 192(June 1955):6 (errata).
  10. ↑ Schiff 2011, p. 3
  11. ↑ Ilachinski 2001, p. xxix
  12. ↑ Bialynicki-Birula & Bialynicka-Birula 2004, p. 8
  13. ↑ 13.0 13.1 Wolfram 2002, p. 876
  14. ↑ von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press. 
  15. ↑ Wiener, N.; Rosenblueth, A. (1946). “The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle”. Arch. Inst. Cardiol. México 16: 205. 
  16. ↑ Davidenko, J. M.; Pertsov, A. V.; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). “Stationary and drifting spiral waves of excitation in isolated cardiac muscle”. Nature 355 (6358): 349–351. Bibcode 1992Natur.355..349D. doi:10.1038/355349a0. PMID 1731248. 
  17. ↑ Hedlund, G. A. (1969). “Endomorphisms and automorphisms of the shift dynamical system”. Math. Systems Theory 3 (4): 320–3751. doi:10.1007/BF01691062. http://www.springerlink.com/content/k62915l862l30377/. 
  18. ↑ Schiff 2011, p. 182
  19. ↑ Gardner, Martin (1970). “Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"”. Scientific American (223): 120–123. http://www.ibiblio.org/lifepatterns/october1970.html. 
  20. ↑ Paul Chapman. Life universal computer. November 2002
  21. ↑ 21.0 21.1 21.2 21.3 21.4 Wolfram 2002, p. 880
  22. ↑ Wolfram 2002, p. 881
  23. ↑ 23.0 23.1 23.2 Ilachinski 2001, p. 12
  24. ↑ Ilachinski 2001, p. 13
  25. ↑ Wolfram 2002, p. 231
  26. ↑ Zenil, Hector (2010). “Compression-based investigation of the dynamical properties of cellular automata and other systems”. Complex Systems 19 (1). http://www.complex-systems.com/pdf/19-1-1.pdf. 
  27. ↑ G. Cattaneo, E. Formenti, L. Margara (1998). “Topological chaos and CA”, in M. Delorme, J. Mazoyer: Cellular automata: a parallel model. Springer. ISBN 978-0-7923-5493-2. 
  28. ↑ Burton H. Voorhees (1996). Computational analysis of one-dimensional cellular automata. World Scientific. ISBN 978-981-02-2221-5. 
  29. ↑ Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. ISBN 978-3-540-56149-1. 
  30. ↑ 30.0 30.1 Kari, Jarrko 1991, p. 379
  31. ↑ Richardson, D. (1972). “Tessellations with local transformations”. J. Computer System Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6. 
  32. ↑ Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces - Tome I, Volume 1. Archives contemporaines. ISBN 978-2-84703-033-4. 
  33. ↑ Schiff 2011, p. 103
  34. ↑ Serafino Amoroso, Yale N. Patt, Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures. J. Comput. Syst. Sci. 6(5): 448-464 (1972)
  35. ↑ Sutner, Klaus (1991). “De Bruijn Graphs and Linear Cellular Automata”. Complex Systems 5: 19–30. http://www.complex-systems.com/pdf/05-1-3.pdf. 
  36. ↑ Kari, Jarkko (1990). “Reversibility of 2D cellular automata is undecidable”. Physica D 45: 379–385. Bibcode 1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U. 
  37. ↑ Kari, Jarkko (1999). “On the circuit depth of structurally reversible cellular automata”. Fundamenta Informaticae 38: 93–107. 
  38. ↑ Durand-Lose, Jérôme (2001). “Representing reversible cellular automata with reversible block cellular automata”. Discrete Mathematics and Theoretical Computer Science AA: 145–154. 
  39. ↑ Wolfram 2002, p. 60
  40. ↑ 40.0 40.1 Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific, 44–45. ISBN 978-981-238-183-5. 
  41. ↑ "life-like cellular automaton" という用語の初出は少なくとも Barral, Chaté & Manneville (1992) まで遡るが、この文献では外部総和型全般をそのように呼んでおり、2次元に限定していない。
  42. ↑ (2010) Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2.  - こちらはより限定的な意味で "life-like" と呼んでいる。
  43. ↑ http://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html
  44. ↑ Murray, J.. Mathematical Biology II. Springer. 
  45. ↑ Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata", Theoretical Computer Science, 372 (1), March 2007, pp.46-68
  46. ↑ Giles, Jim (2002). “What Kind of Science is This?”. ネイチャー (417): 216–218. 
  47. ↑ Weinberg, Steven (October 24, 2002). “Is the Universe a Computer?”. The New York Review of Books (Rea S. Hederman). http://www.nybooks.com/articles/archives/2002/oct/24/is-the-universe-a-computer/?pagination=false . October 12, 2012閲覧.. 
  48. ↑ 48.0 48.1 48.2 Coombs, Stephen (February 15, 2009), The Geometry and Pigmentation of Seashells, pp. 3–4, http://www.maths.nott.ac.uk/personal/sc/pdfs/Seashells09.pdf . 2012閲覧. 
  49. ↑ Peak, West; Messinger, Mott (2004). “Evidence for complex, collective dynamics and emergent, distributed computation in plants”. Proceedings of the National Institute of Science of the USA 101 (4): 918–922. Bibcode 2004PNAS..101..918P. doi:10.1073/pnas.0307811100. PMC 327117. PMID 14732685. http://www.pnas.org/cgi/content/abstract/101/4/918. 
  50. ↑ http://gilly.stanford.edu/past_research_files/APackardneuralnet.pdf
  51. ↑ Yves Bouligand (1986). Disordered Systems and Biological Organization, 374–375. 
  52. ↑ A. K. Dewdney, The hodgepodge machine makes waves, Scientific American, p. 104, August 1988.
  53. ↑ M. Gerhardt and H. Schuster, A cellular automaton describing the formation of spatially ordered structures in chemical systems, Physica D 36, 209-221, 1989.
  54. ↑ 54.0 54.1 The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
  55. ↑ http://www.santafe.edu/about/people/profile/Melanie%20Mitchell
  56. ↑ 56.0 56.1 The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
  57. ↑ Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
  58. ↑ Tomassini, M.; Sipper, M.; Perrenoud, M. (2000). “On the generation of high-quality random numbers by two-dimensional cellular automata”. IEEE Transactions on Computers 49 (10): 1146–1151. 
  59. ↑ Wolfram, S. "Cryptography with Cellular Automata", In Advances in Cryptology: CRYPTO '85 Proceedings [Williams, H. C. (Ed.)]. Lecture Notes in Computer Science 218. Springer-Verlag, 429–432, 1986.
  60. ↑ "Cellular Automaton Public-Key Cryptosystem", Complex Systems, Vol. 1, No. 1 (1987).
  61. ↑ Ilachinski 2001, p. 660
  62. ↑ Ilachinski 2001, pp. 661–662
  63. ↑ J. P. Crutchfield, "The Calculi of Emergence: Computation, Dynamics, and Induction", Physica D 75, 11-54, 1994.
  64. ↑ M. Minsky, "Cellular Vacuum", International Journal of Theoretical Physics 21, 537-551, 1982.
  65. ↑ K. Zuse, "The Computing Universe", Int. Jour. of Theo. Phy. 21, 589-600, 1982.
  66. ↑ E. Fredkin, "Digital mechanics: an informational process based on reversible universal cellular automata", Physica D 45, 254-270, 1990
  67. ↑ iLabs
  68. ↑ F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference, College Publications, 2010
  69. ↑ Weisstein, Eric W.. “Cellular Automaton”. . 2011閲覧.
  70. ↑ the Hacker Emblem page on Eric S. Raymond's site
  71. ↑ (1999) Strange constellations: a history of Australian science fiction, Contributions to the study of science fiction and fantasy. Greenwood Publishing Group, 190–200. ISBN 978-0-313-25112-2. 
  72. ↑ Hayles, N. Katherine (2005). My mother was a computer: digital subjects and literary texts. University of Chicago Press, 214–240. ISBN 978-0-226-32147-9. 
  73. ↑ Kasman, Alex. “MathFiction: Bloom”. . 2011閲覧.
  74. ↑ http://www.sfwriter.com/syw1.htm
  75. ↑ http://www.dezeen.com/2014/09/26/francis-bitonti-3d-printed-molecule-shoes-adobe-stratasys/

参考文献

  • 『アインシュタインの部屋』上・下 - エド・レジス著／大貫昌子訳　工作舎　ISBN 978-4-87502-171-1・ISBN 978-4-87502-172-8
  • 『コンピューターレクリエーションI 遊びの発想』 - A.K.デュードニー著 別冊サイエンス32
  • 『哲学者クロサキと工学者アイハラの神はカオスに宿りたもう』 - 合原 一幸、 黒崎 政男 共著
  • 『箱玉系の数理』 - 時弘哲治 朝倉書店
  • (2004) Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 0198531001. 
  • (2005) Cellular Automata Modeling of Physical Systems. Cambridge University Press. ISBN 0-521-46168-5. 
  • (1991) in Gutowitz, Howard: Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862. 
  • Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835. 
  • (2005) Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576. 
  • Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. ISBN 9781118030639. 
  • Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080. 
  • Barral, Bernard; Chaté, Hugues; Manneville, Paul (1992). “Collective behaviors in a family of high-dimensional cellular automata”. Physics Letters A 163 (4): 279–285. doi:10.1016/0375-9601(92)91013-H. 
  • Cellular automaton FAQ from the newsgroup comp.theory.cell-automata
  • A. D. Wissner-Gross. 2007. Pattern formation without favored local interactions, Journal of Cellular Automata 4, 27-36 (2008).
  • "Neighbourhood Survey" 三角格子や大きな近傍のセル・オートマトンなどを論じている
  • von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
    • 『自己増殖オートマトンの理論』- フォン・ノイマン著 岩波書店
  • Cosma Shalizi's Cellular Automata Notebook 書誌情報が豊富
  • Wolfram's papers on CAs
  • A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society, vol. B237, pp. 37 – 72. - 連続的オートマトンの一種を提唱している。
  • Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
  • The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
  • The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
  • Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata"
  • Zuse´s publications on CA-based physics (1967, 1969, 1970), with comments by Juergen Schmidhuber
  • Klaus Sutner. 1989. A Note on Culik-Yu Classes Complex Systems 3 (1989) 107-115.

関連項目

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=セル・オートマトン&oldid=110413」から取得