セル・オートマトン
セル・オートマトン(cellular automaton、略称:CA)とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。
正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「homogeneous structure」「tessellation structure」「iterative array」といった呼称もある。
有限種類の(多くは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 とすると、このようなシステムの規則は kks という式で表される。したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 229 または 1.34 となる。
例えば1次元セル・オートマトンでは、時刻(ステップ)を t、位置を1次元の i としたとき、セル xit の近傍は {xi−1t−1, xit−1, xi+1t−1} となる。
2次元のセル・オートマトンで最も有名なものがライフゲームである。ライフゲームは以下のようなルールで記述される。
誕生: 死んでいるセル(「白」)の周囲に3つの生きているセル(「黒」)があれば次の時間ステップでは生きる(「黒」になる)。
維持: 生きているセル(「黒」)の周囲に2つか3つの生きているセル(「黒」)があれば次の世代でも生き残る(「黒」のままである)。
死亡: 上以外の場合には次の世代では死ぬ(「白」になる)。
このライフゲームのルールは細菌などの生物の繁殖のアナロジーである。すなわち、孤独でも人口過密でも死んでしまう。最も快適な人口密度では子孫を残し繁栄する性質を持つ。実際、ライフゲームは生物の増殖のような複雑で多様な振舞いを示す。
一般に各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始する。これを「コンフィギュレーション」と呼ぶ。また、全体が周期的なパターンを形成し、一部がそのパターンから外れた状態で開始する場合もある。後者は1次元のセル・オートマトンでは一般的である。
多くのセル・オートマトンのシミュレーションでは有限の格子を使う。2次元の場合、無限の平面ではなく、有限の四角形で表される。有限の格子での明らかな問題は端のセルの扱いであり、端のセルの扱いが格子全体のセルの状態に影響を与えるため重要な問題である。1つの手法は、端のセルを全て変化しない定数を状態として持つとする手法である。別の手法は端のセルの近傍を一般のセルとは違う内容にする手法である。つまり、端のセルの近傍を通常より少なく定義できるが、その場合は規則も新たに定義する必要がある。別の手法として、2次元の場合に四角形の平面の端の上下と左右を繋げて、トーラス形にする手法もある。これは、ある意味で無限の平面が同じ四角形で平面充填されている状態に近い。1次元であれば、線の端を繋いでループにする空間に相当する。これは端の問題を回避するために行うが、モジュロ演算関数を使って容易にプログラム可能という利点もある。
1940年代にロスアラモス国立研究所で働いていたスタニスワフ・ウラムは結晶の成長について研究していたとき、モデルとして単純な格子ネットワークを使用していた。同じころロスアラモスで一緒に働いていたジョン・フォン・ノイマンは自己複製機械を研究していた。フォン・ノイマンはまず、あるロボットの記述に基づいて別のロボットの記述を行うという設計を考えていた。この設計は運動学モデル(Kinematic model)と呼ばれている。設計を進めるに連れ、フォン・ノイマンは、複製を作るための「部品の海」をロボットに与えることのコストの膨大さやあるロボットが別のロボットを作るということを記述する大変さを徐々に理解していった。ノイマンは1948年の Hixon Symposium にて "The general and logical theory of automata" と題した論文を読む。またウラムはフォン・ノイマンに自己複製の還元主義的モデルとして離散系を使ってはどうかと示唆した。Nils Aall Barricelli はそういったモデルを使って人工生命を研究していた。
1950年代、ウラムとノイマンは液体の動きを計算する方法を生み出した。その中心となった考え方は液体を離散的単位の集まりとみなすということで、各単位の動作をその近傍の挙動に基づいて計算する。それらが元となってセル・オートマトンが生まれた。ウラムの格子ネットワークのように、フォン・ノイマンのセル・オートマトンは2次元で、その中に自己複製機械がアルゴリズム的に埋め込まれた。これがユニバーサルコンストラクタであり、近傍として隣接する4つのセルのみ(ノイマン近傍)を考慮し、1つのセルあたり29の内部状態を持っている。このモデルで彼は自己複製機械として動作するパターンを20万個のセルを使ってデザインし、それが無限に自己複製を繰り返すことを数学的に証明した。この設計は平面充填モデルとして知られている。1968年、エドガー・F・コッドは 8 状態で自己複製を繰り返すコッドのセル・オートマトンを考案している。
同じく1940年代、ノーバート・ウィーナーとアルトゥーロ・ローゼンブリュートがセル・オートマトンを開発し興奮性媒質のモデルに採用した。その具体的な目的は、心筋におけるインパルス伝導の数学的説明であった。その業績は不整脈や興奮性媒質についての後の研究でよく引用されている。
1960年代、セル・オートマトンは力学系の特殊形として研究され、数学の一分野である記号力学と関連して研究され始めた。1969年、グスタフ・A・ヘドランドはその観点で数多くの成果をまとめ、それがセル・オートマトンの数学的研究における重要な論文とされている。
1969年、ドイツのコンピュータのパイオニアの1人であるコンラート・ツーゼは、著書 Calculating Space の中で、宇宙の物理法則は本質的には離散的であり、宇宙全体が一種の巨大なセル・オートマトン上の決定的な計算の結果であると主張した。この著書が今日デジタル物理学と呼ばれている分野の基礎を築いた。
1970年代、2状態で2次元のセル・オートマトンであるライフゲームが特にコンピュータコミュニティでよく知られるようになった。ジョン・コンウェイの発明によるもので、マーティン・ガードナーがサイエンティフィック・アメリカン誌(日本では日経サイエンス誌)で紹介したことで有名となったのである。ライフゲームは単純だが、システムとして興味深い挙動を示し、ランダム性と規則性の間で変動する。ライフゲームの最も顕著な特徴として「グライダー」(格子を横断して移動していくセル群)が頻繁に発生することが挙げられる。グライダーをうまく配置すると一種の相互作用が生まれる。長年の研究により、ライフゲームがチューリングマシンをエミュレートできることが判明した。それが単なる趣味の話題と受け止められたためか、ライフゲームの特殊性の研究や関連する規則の研究が若干行われた以外、この発見を受けた研究はなされなかった。
1981年、熱力学第二法則に反するように見える自然界の様々な複雑なパターンを検討していたスティーブン・ウルフラムは、セル・オートマトンの研究を始めた。当初の動機はセル・オートマトンで神経ネットワークなどのシステムをモデリングできるのではないかというものだった。1983年6月、Reviews of Modern Physics 誌にて基本セル・オートマトン(特にルール30)についての最初の論文を発表。ウルフラムは、単純な規則で示される振る舞いの予期せぬ複雑さを見て、自然界の複雑さも同様の機構によって生まれているのではないかと考えた。しかし、彼の研究によってセル・オートマトンは神経ネットワークのモデリングには貧弱すぎることが判明した。さらにウルフラムは真の無作為性と計算既約性の概念を定式化し、ルール110がチューリング完全であると推測した(1990年代にウルフラムの助手 Matthew Cook がそれを証明した)。
ウルフラムは1980年代中盤以降に学界を去ってMathematicaを開発し、彼のそれまでの研究結果を広い範囲の単純で抽象的な系に拡張して適用するのに Mathematica を使った。2002年、ウルフラムはそれらの成果を1280頁の著書 A New Kind of Science として発表した。この中でセル・オートマトンがあらゆる科学にとって重要な関わりを持つことを主張している。一部で誤解されているように、同書は物理法則がセル・オートマトンに基づいているとは言っていない(ツーゼとは異なる)が、セル・オートマトンに基づいた物理モデルをいくつか記述しており、他にも各種抽象系に基づいたモデルを示している。
最も単純だが自明ではないCAは、1次元で各セルは2つの状態をとることができ、近傍は両側に接している隣のセルという場合である。あるセルとその両側の3つのセルで近傍を構成するので、1つの近傍がとりうるパターンは 23=8 種類となる。規則はそれらパターンについて、そのセルが次世代に1と0のどちら状態となるかを決定する。したがって規則群の組合せは 28=256 通り存在する。それら256種類のCAは一般にウルフラムが考案した0から255までのルール番号で参照され、これをウルフラム・コードと呼ぶ。これら256種類のCAはいくつかの論文で研究・比較されている。ルール30とルール110のCAは特に興味深い。下図は、1カ所だけ1にした初期状態からのそれらCAの変化の様子を示している。図の各行がCAの1世代の履歴であり、一番上の行が t =0 である。各ピクセルは、0を白、1を黒で描画している。
例えば「ルール30」と呼ばれるのは、上の表のように時刻t+1における中央のセルの内部状態一覧を並べると0,0,0,1,1,1,1,0となっており、この2進数の数を10進数に直すと30であるためであり、これをウルフラム・コードと呼ぶ。
ルール30は「クラス3」の挙動を示し、単純な初期状態からもカオス的な経過を示し、無作為な履歴になっている。
ルール110はライフゲームのように「クラス4」の挙動を示し、完全な無作為でもなく、完全な反復でもない。局所的構造が現れ、様々な複雑な形で相互作用する。1994年ウルフラムの研究助手だったマシュー・クックは、それら構造の一部がチューリング完全性をサポートするのに十分であることを証明した。ルール110は非常に単純な1次元のシステムであり、具体的なことを実行するよう設計するのは困難であるため、この成果は興味深い。この結果からウルフラムはクラス4のセル・オートマトンが本質的にチューリング完全である可能性を示唆した。1998年、セル・オートマトンの学会がサンタフェ研究所で開催され、クックはその成果を発表したが、ウルフラムは A New Kind of Science の出版前にその証明の詳細を公表したくなかったため、証明の詳細は発表されなかった。2004年、Cookの証明がウルフラムの発行する雑誌 Complex Systems (Vol. 15, No. 1) で発表された。実に証明してから10年が経過している。ルール110をベースとして極小の万能チューリングマシンが構築されている。
また、ルール90の1次元セル・オートマトンは典型的なフラクタル図形であるシェルピンスキーのギャスケットを生成する。(WolframAlphaでルール90を見る→)
一部の生物学的過程はセル・オートマトンでシミュレートできる。
イモガイやガクフボラといった貝の貝殻の模様はセル・オートマトンの描くパターンによく似ている。貝殻の辺縁に狭い帯状に色素細胞がある。各色素細胞は活性化されると色素を分泌し、同時に近傍の色素細胞の活性化を阻害するようになっており、天然のセル・オートマトンの規則のように作用する。この色素細胞の帯が貝殻に色の模様を残しつつ、少しずつ貝殻が成長していく。例えば、イモガイの一種タガヤサンミナシはウルフラムが研究したルール30CAとよく似た模様である。
植物はCA的機構で気体の吸入と排出を行っている。葉に多数存在する気孔がセル・オートマトンのセルのように振る舞う。
頭足類は表皮に色素胞があり、体表の模様を変化させるが、これを2状態で2次元のセル・オートマトンでシミュレートできる。各状態は色素胞を広げた状態と縮めた状態に対応する。
神経細胞をシミュレートするしきい値型CAが考案されており、認知や学習といった複雑な挙動をシミュレートできる。
線維芽細胞もセル・オートマトンと似た挙動を示す。個々の線維芽細胞はその近傍の細胞としか相互作用しない。
ベロウソフ・ジャボチンスキー反応はセル・オートマトンを使ってシミュレートできる。1950年代、A・M・ジャボチンスキーはソ連のB・P・ベロウソフの研究成果をさらに進め、マロン酸、酸化した臭素酸塩、セリウム塩の混合物の薄い均一な層を置いておくと、同心円や渦巻き模様などの幾何学的模様が生じることを発見した。1988年8月、サイエンティフィック・アメリカン(日本では日経サイエンス)誌上の "Computer Recreation" という記事で、A. K. Dewdney はベロウソフ・ジャボチンスキー反応に非常によく似た挙動を示すセル・オートマトンを紹介した。ベロウソフ・ジャボチンスキー反応が、分子レベルでそのセル・オートマトンと同じような仕組みで発生しているのかどうかは不明である。これまで、セル・オートマトン的な化学反応が自然界で観察されたことはない。そのような化学反応は全て研究室や実験室でのみ観測されている。
ソリトンのようなふるまいを見せる、箱玉系と呼ばれているセル・オートマトンがある。
離散的(非連続的)時間で記述され、時刻t+1における1つのセルの内部状態は、時刻tにおける状態によって決定されるといった点で、セル・オートマトンはチューリングマシンとよく似ている。実際、万能チューリングマシンと等価な動作をするセル・オートマトンが存在することが知られている。しかし、チューリングマシンは「逐次的な処理を行うデジタルコンピュータ」のモデルであるのに対し、セル・オートマトンは各セルが並列に演算処理を実現しており、いわば "並列コンピュータ" であるという点で大きく異なる。
セル・オートマトンの概念をハードウェアで実装して情報処理を行おうとする試みも行われている。処理要素は格子状に配置され、2次元か3次元の平面充填構造とされる。それ以外の並べ方も可能だが、まだ試されたことはない。各処理要素(すなわちセル)は隣接する少数のセルだけとやり取りする。遠いセルとの直接通信手段は存在しない。セルの相互作用には、電荷、磁化、振動などの物理的な手段を使う。いずれにしても各処理要素間を結線する必要はない。これは、今日のノイマン型コンピュータのプロセッサとはかなり違う。
例えばシストリックアレイはCAプロセッサアレイの一例である。
センサーネットワークやさらに微細な構造をネットワークとして設計し、分散処理を行わせることに関心が集まっている。分散システムを使い大域的なレベルで情報処理するという考え方から創発計算というアイデアが生まれた。ポートランド州立大学の教授でサンタフェ研究所にも所属しているメラニー・ミッチェルは、そのために自己進化するセルの格子を使うアイデアに取り組んでいる。ミッチェルらはセル格子のプログラムに進化的アルゴリズムを採用している。分散型システムにおける計算は古典的なコンピュータとは大きく異なり、大域的および局所的なパターンの変化という形で情報処理がなされる。
この手法の発想の元になっているのは、社会性昆虫、神経系、経済システムといった自然界に見られる複雑なシステムである。研究の焦点は、進化する分散型システムでいかにして計算が発生するかを解明することである。モデルを構築しどのようにして創発計算が生じるかを解明するため、ミッチェルらはセル・オートマトン内のパターンを進化させるべく遺伝的アルゴリズム (GA) を適用した。既にGAによって洗練された創発計算戦略が生じる規則を発見している。ミッチェルらが採用したのは1次元2値で6個の近傍を持つセル・オートマトンである。先頭と末尾は繋がっているので、環状になっている。
2次元セル・オートマトンを擬似乱数発生に使った例がある。
ルール30は、ブロック暗号に応用可能という提案がある。
セル・オートマトンを公開鍵暗号に使うという提案もある。
セル・オートマトンを誤り訂正符号の設計に応用した例として、D. Roy Chowdhury、S. Basu、I. Sen Gupta、P. Pal Chaudhuri の論文 "Design of CAECC - Cellular Automata Based Error Correcting Code" がある。この論文ではセル・オートマトンを使って SEC-DED符号(1ビット誤り訂正-2ビット誤り検出符号)を構築する新たな手法が定義されており、その符号の高速ハードウェアデコーダも報告されている。
Andrew Ilachinski は著書 Cellular Automata で、多くの学者が宇宙自体がセル・オートマトンなのではないかという疑問を投げかけていると指摘した。Ilachinskiは、この問題の重要性を示すには簡単な観察をしてみるのがよいと主張し、例えばルール110の発展するパターンをどうやったらうまく説明できるか考えてみるのがよいとした。そして、もしそのイメージの生成方法を知らないとしたら、何らかの粒子状のオブジェクトの運動の軌跡ではないかと推測するだろうと述べている。実際、物理学者 James Crutchfield はその考え方から厳密な数学的理論を構築した。この考え方を推し進めていくと、素粒子物理学で説明されている我々の世界も根底ではCAと見なせるのではないかという考え方に到達する。
その考え方に沿った理論はまだ発展途中だが、この仮説に興味を惹かれた学者らが離散的フレームワークで世界を理解することについて興味深い憶測と有益な直観を示している。AI研究者マービン・ミンスキーは、4次元CA格子で素粒子の相互作用を理解する方法を研究した。コンピュータの先駆者コンラート・ツーゼは、素粒子の持つ情報についての問題を解くため、不規則な格子を考案した。またエドワード・フレドキンは "finite nature hypothesis" と名付けた仮説を提唱。「最終的に時間や空間を含む全ての物理量は離散的で有限だと判明するだろう」とした。フレドキンとウルフラムはデジタル物理学の信奉者である。
21世紀に入ると、非標準計算についての著作からこの考え方に沿った示唆が生まれている。ウルフラムの A New Kind of Science では、CAが物理学を含めた様々な主題を理解する鍵だとしている。(Francesco Berto が創始し、Gabriele Rossi と Jacopo Tagliabue が発展させた)iLabsが2010年に出版した Mathematics Of the Models of Reference では「菱形十二面体」をベースとする格子と独特の規則で2次元および3次元の宇宙を説明するモデルを提案している。このモデルはチューリングマシンと等価であり、完全な可逆性を有し(様々な量を保存し、情報を決して失わない)、宇宙の発展についての質的な論述を計算できる論理が組み込まれている。
『NUMBERS 天才数学者の事件ファイル』シーズン2のエピソード「誘拐事件の真相」にて、1次元セルオートマトンへの言及がある。
エリック・レイモンドはハッカー文化のシンボルとして、ライフゲームのグライダーを描いたエンブレムを提案した。
グレッグ・イーガンの小説『順列都市』(早川文庫)では、オートヴァースと呼ばれる人工生命シミュレータが登場する。
ウィル・マッカーシイの小説 Bloom では、セル・オートマトンを論じている。
ロバート・J・ソウヤーの WWW 三部作ではセル・オートマトンが重要な役割を演じ、ウェブ上の人工生命が意識を獲得する方法に関係している。
フランシス・ビトンティがライフゲームのアルゴリズムを使用して靴のデザインを自動生成させた。生成させる度に色のグラデーションやフォルムがわずかに異なる仕様。