Complex Systems Created by Cellular Automata
(English here)
ギャラリー
セルオートマトンて何？
セルオートマトンの歴史
複雑系て何？
人工生命て何？
リンク集
アイコンの説明:
![[new]](new.gif)
: 新情報
![[good]](good.gif)
: お勧め
![[demo]](demo.gif)
: デモ
セルオートマトンの歴史
セルオートマトンはもともと1940年代末に生物の自己複製機能を摸擬するために、数学者のウラムとフォン・ノイマンによって提案されたものです[Ne66]。ウラムはモンテカルロ法という計算機シミュレーション法を開発したことで知られています。また彼は水素爆弾の製造にもかかわりました。フォン・ノイマンは最も有名な数学者の一人で、ゲーム理論の創始者[Po92]、史上初の電子計算機の設計者として知られています。当時フォン・ノイマンは機械またはオートマトン（自動機械と訳される）が自分自身のレプリカを作ることができるかどうかについて研究していました。彼は、自己複製には機械自身が自分自身の設計図（ブループリント）を有しており、それを複製することができれば自分自身を複製できると結論づけました。無論、このブループリントは実際の生物でDNA（一部のウィルスではRNA）に対応します。ただし、この時点で遺伝情報の実体がDNAであることを支持する実験結果があがっていましたが、それが証明されたわけではなく、その構造解明が待たれていました。ケンブリッジ大学のワトソンとクリックがこれを行い、DNAが複製に適した２重螺旋構造であることが分かったのは、それから数年後でした[Wa68]。彼等はこの研究によって1962年にノーベル賞を受賞しています。ワトソンとクリックがフォンノイマンの研究を知っていたとは考えられませんが、フォンノイマンの方では分子生物学者たちの遺伝子研究を知っていて、そこからヒントを得たのかもしれません。
さて、フォン・ノイマンは当初、様々な標準的な機械の部品を機械自身が組み合わせることを頭に描いていましたが、当時同じ職場（米国ニューメキシコ州、ロスアロモス国立研究所）にいたウラムがそれら機械の部品の代わりに有限状態数を持つ理想化されたセル空間を考えることを示唆しました。この示唆を受けたフォン・ノイマンは2次元の自己複製するセル・オートマトンの完全な記述を1952年に書き上げました。このセルオートマトンには自分自身と前後左右の５つのセルで構成されるいわゆるフォンノイマンネイバー構造が使われました。これは設計図に記述されたものならどのようなものでも再生してしまう能力を有していました。このような能力を有するものはユニバーサルコンストラクタと呼ばれます。またこのセルオートマトンの中には、アラン・チューリングが提唱したどのようなアルゴリズムになれる能力がある万能コンピュータ（universal computer）も組み込まれました。一連の研究の後、彼は反共的な信念から軍事問題に熱中しセルオートマトンの研究には戻りませんでした。フォンノイマンは、1957年に癌で亡くなっています。また、ウラムはその後も研究を続け研究論文もいくつか発表しました。彼は1984年に亡くなっています。
1970年頃、イギリスケンブリッジ大学の数学者コーンウェイは最初非常に単純なパターンが大規模パターンに成長していき、なおかつどのパターンが成長するのかが決してわからないようなルールを試行錯誤しながら探していました。当時コンピュータ技術が未熟だったため、彼は紙に書いてシミュレーションをしていたということです。彼はこうやって探しあてたルールすなわち、ライフゲームを人気数学ライターであるマーチンガードナーに送りました。ガードナーはそれをScientific American誌に紹介したところ[Ga70,Ga71]、大きな反響を呼びました。ライフゲームは２次元２状態のセルオートマトンで、そのルールは自分自身と周囲のセルの状態数の和によって定義された非常に単純なものでしたが、非常に複雑で予測しがたいダイナミクスを有していました。その後、ライフゲームは万能コンピュータ（万能チューリング機械）であることが証明されています[Be82]。これは簡単に言えば、ライフゲームが原理的には計算機で実行可能なすべての計算過程を作り出せることを示しています。ただし、それらが効率のよいアルゴリズムになる保証はありません。
またガードナーはエドワード・フレドキンが発見したフォンノイマンのもの比べ非常に単純なルールで自己複製ができるセルオートマトンすなわちフレドキン・ルールを紹介しました[Ga71]。フレドキンはガードナーによって紹介される10年程以前にそのルールを発見していました。このルールは余りにも単純なので、多くの人が度胆を抜かれたここと思います。（フレドキンルールのJAVA-Appletによるデモはこちら）
セルオートマトンの次のブームは１９８０年代半ば、イギリスの天才児ウルフラムによってもたらされました。彼は１次元のセルオートマトンを徹底的に調べ上げました[Wo83]。また、それらを時間発展の仕方から定性的に以下の４つのクラスに分けました。[Wo84]
- クラス１：セル空間がすべて同じ状態のセルに覆われてしまい、変化しなくなる。
- クラス２：セルの時間発展が局所化され、周期的または定常的になる。
- クラス３：セル全体がランダムな時間発展をする。
- クラス４：セルの時間発展は複雑で、局所化されている。また長い過渡状態を持つ。
これはウルフラムクラスと呼ばれています。クラス１および２は秩序状態で、クラス３はカオス状態です。このどちらにも属さないクラス４は秩序とカオスの中間に位置する状態で複雑な状態とされました。このように多くのセルオートマトンを実行し、それを統計的に取り扱うというやりかたは、物理学者には非常に受け入れやすく多くの共感を呼びました。ただしウルフラムクラスは分け方に曖昧なところがあり、また４つのクラスに属さないものも存在することがわかっています[Su99, Su00a]。
さて、ウルフラムに少し遅れてセルオートマトン研究で高い評価を得たのがラングトンです。彼は今では人工生命研究の創始者として高い評価を受けていますが、３０歳代後半にロスアロモス研究所にポスドクとして雇われるまでは不遇の日々を送っていました。ただし、ミシガン大学で遺伝的アルゴリズムの創始者ホランドと出会ったことは非常に幸運だったといえるでしょう。（この辺のくだりは、[Wa92]に詳しく書かれています。）彼はウルフラムが4つのクラスについて述べた論文から示唆を受け、クラス１，２の秩序状態から、クラス４の複雑な状態を経て、クラス３に至る相転移を調べている間に、相転移が起きる場合すなわちクラス４を引き起こすルールには共通の性質があることに気づきました。すなわち次の瞬間、ある任意のセルが０以外の状態になる確率がある数を超えると秩序からカオスに変化することがわかりました。この確率はλパラメータと名づけられました。また彼は、このセルオートマトンの相転移が現実の世界の２次の相転移に非常に似ていることに気がつきました。ラングトンはセルオートマトンが臨界λ値をもつ時、すなわち相転移点において生命に必要な計算能力がもっとも高くなり[La90]、そのため複雑な計算能力を有する生命は規則的な体制（regime）からカオス的な体制に変化する間際の状態（カオスの縁）に存在すると予測しました。
我々の脳は脳細胞が連結されてできています。もし、ある刺激がクラス３のように脳全体をカオス状態にしてしまうほど脳細胞の連結の度合いが強かったなら、複雑な計算はできません。また連結の度合いが非常に弱く、クラス２のように刺激が十分伝わらなくて空間的に局所化されたり、クラス１のように刺激の影響がすぐに消えてしまったりしても不都合です。すなわち、どうしてもクラス４のような程よい連結の強さが必要なのです。
このようにカオスの縁の予測は、定性的は納得できるものの、どうしてカオスの縁が自発的に現れるのかは説明されていません。このことについて、パッカードがセルオートマトンのルールを遺伝的アルゴリズムによって進化させてやるとルールがカオスの縁に近づくと主張しています[Pa88]。これは「カオスの縁への適応」と呼ばれています。カオスの縁の概念（すなわち計算能力と相転移の相関）、およびカオスの縁への適応という仮説を、カウフマンのように受け入れる者[Ka93]もあれば、ミッチェルのようにパッカードの解釈を再検証する[Mi93a,Mi93b]もいます。
ラングトンはまた、フォンノイマンが手掛けた自己再生セルオートマトンに対しても興味をもちました。彼は生命は必ずしもユニバーサルコンストラクタである必要がないと考え、自己再生能力のみを満足するセルオートマトンを提案しました[La84]。このセルオートマトンはループと呼ばれ現在でも人工生命の研究で議論されています（ループのアプレットはこちら）．ループでは、予め決められた初期状態を与える必要があり、自己組織化とは言えない部分があります。また空間全体の状態を同時に更新すること（同期性）なども気になります。これはループというよりはセルオートマトン全体の属性です。明らかに同期性がないとセルオートマトンでパターンを作るのが著しく難しくなります。ループだけでなく、ゲームオブライフのグライダーなどの興味深いパターンも明らかに同期性に依存しています。また、ループやその拡張版では保存則を無視して、”化学物質”が無からあらわれます。このように保存則を無視して生命現象を議論できるのかという疑問もあります。ラングトンの一連の研究から10年以上が過ぎましたが、生命現象とセルオートマトンの研究はまだまだ謎でいっぱいです。
以上のように、セルオートマトンは生命現象の知られざる秘密を探りたいという目的で提案され、発展してきましたが、現在は画像処理や流体力学等の実用分野でも使われるようになってきています。残念ながらこれら実用分野での歴史は私の知識の範囲を越えるため、割愛しましたのでご了承下さい。
参考文献
[Be82] Berlekamp, E., Conway, J., Guy, R. (1982). "Winning Ways for your Mathematical Plays", Academic Press.
[Ga70] Gardner, M. "Mathematical games", 1970 Sci. Am., 223 October,
120-123.
[Ga71] Gardner, M. "Mathematical games", 1971 Sci. Am., 224 February,
112-117.
[Ka93] Kauffman, S. A. "The origin of order", Oxford University Press (1993).
[La84] Langton, C. G. "Self-reproduction in cellular automata", Physica D, Vol. 10, 135-144(1984).
[La90] Langton, C. G. "Computation at the edge of chaos: phase transition
and emergent computation", 1990 Physica D, 42, 12-37.
[Mi93a] Mitchell M. et al. "Revisiting the edge of chaos: evolving cellular
automata to perform computations", Complex Systems, 7, 89-130, 1993. (online paper)
[Mi93b] Melanie Mitchell, James P. Crutchfield, and Peter T. Hraber; "Dynamics, Computation, and the ``Edge of Chaos'': A Re-Examination" In G. Cowan, D. Pines, and D. Melzner (editors), Complexity: Metaphors, Models, and Reality. Santa Fe Institute Stuides in the Sciences of Complexity, Proceedings Volume 19. Reading, MA: Addison-Wesley. (online paper)
[Ne66] von Neumann, J. "Theory of self-reproducing automata", edited
and completed by A. Burks, University of Illinois Press, Champaign, IL
(1966).
[Pa88] Packard, N. H. "Adaptation toward the edge of chaos", Dynamic
Patterns in Complex Systems, 293-301, Singapore, 1988. World Scientific.
[Po92] Poundstone, W. "Prisoner's dilemma", Bantam Doubleday Dell Publishing
Group, Inc. (1992). （松浦俊輔訳 ”囚人のジレンマ −フォン・ノイマンのゲームの理論” 青土社、 1995).
[Su99] Suzudo, T. "Crystallisation of two-dimensional cellular automata", Complexity International,Vol. 6 (1999). to download pdf-formatted file
[Su00a] 鈴土知明 ”２次元セルオートマトンの相転移と結晶化”，複雑系研究会６， (1999) （物性研究 vol. 74 no.1, 59 (2000/4）) (to download pdf-formatted file of the paper)
[Wa68] J. D. Watson "The double helix", Weidenfeld Publishers Ltd. London (1968). （江上不二夫他 訳 ”二重らせん”講談社文庫 1986）
[Wa92] M. Michell Waldrop "Complexity -The emerging science at the edge of order and chaos", (1992)（田中三彦，遠山峻征 訳 ”複雑系”，新潮社 1997）
[Wo83] Wolfram, S. "Statistical mechanics of cellular automata" , Rev.
Mod. Phys. 55 (1983), 601-644. (Online paper)
[Wo84] Wolfram, S. "Universarity and complexity in cellular automata", 1984 Physica D, 10, 1-35. (Online paper)
![[CA]](honeycomb.jpg)
![[CA]](crystal3b.jpg)
![[CA]](pond.jpg)
![[CA]](crystalDiag.jpg)
Last Modified on 22, June, 2004
- : 新情報
- : お勧め
- : デモ
セルオートマトンの歴史
セルオートマトンはもともと1940年代末に生物の自己複製機能を摸擬するために、数学者のウラムとフォン・ノイマンによって提案されたものです[Ne66]。ウラムはモンテカルロ法という計算機シミュレーション法を開発したことで知られています。また彼は水素爆弾の製造にもかかわりました。フォン・ノイマンは最も有名な数学者の一人で、ゲーム理論の創始者[Po92]、史上初の電子計算機の設計者として知られています。当時フォン・ノイマンは機械またはオートマトン（自動機械と訳される）が自分自身のレプリカを作ることができるかどうかについて研究していました。彼は、自己複製には機械自身が自分自身の設計図（ブループリント）を有しており、それを複製することができれば自分自身を複製できると結論づけました。無論、このブループリントは実際の生物でDNA（一部のウィルスではRNA）に対応します。ただし、この時点で遺伝情報の実体がDNAであることを支持する実験結果があがっていましたが、それが証明されたわけではなく、その構造解明が待たれていました。ケンブリッジ大学のワトソンとクリックがこれを行い、DNAが複製に適した２重螺旋構造であることが分かったのは、それから数年後でした[Wa68]。彼等はこの研究によって1962年にノーベル賞を受賞しています。ワトソンとクリックがフォンノイマンの研究を知っていたとは考えられませんが、フォンノイマンの方では分子生物学者たちの遺伝子研究を知っていて、そこからヒントを得たのかもしれません。さて、フォン・ノイマンは当初、様々な標準的な機械の部品を機械自身が組み合わせることを頭に描いていましたが、当時同じ職場（米国ニューメキシコ州、ロスアロモス国立研究所）にいたウラムがそれら機械の部品の代わりに有限状態数を持つ理想化されたセル空間を考えることを示唆しました。この示唆を受けたフォン・ノイマンは2次元の自己複製するセル・オートマトンの完全な記述を1952年に書き上げました。このセルオートマトンには自分自身と前後左右の５つのセルで構成されるいわゆるフォンノイマンネイバー構造が使われました。これは設計図に記述されたものならどのようなものでも再生してしまう能力を有していました。このような能力を有するものはユニバーサルコンストラクタと呼ばれます。またこのセルオートマトンの中には、アラン・チューリングが提唱したどのようなアルゴリズムになれる能力がある万能コンピュータ（universal computer）も組み込まれました。一連の研究の後、彼は反共的な信念から軍事問題に熱中しセルオートマトンの研究には戻りませんでした。フォンノイマンは、1957年に癌で亡くなっています。また、ウラムはその後も研究を続け研究論文もいくつか発表しました。彼は1984年に亡くなっています。
1970年頃、イギリスケンブリッジ大学の数学者コーンウェイは最初非常に単純なパターンが大規模パターンに成長していき、なおかつどのパターンが成長するのかが決してわからないようなルールを試行錯誤しながら探していました。当時コンピュータ技術が未熟だったため、彼は紙に書いてシミュレーションをしていたということです。彼はこうやって探しあてたルールすなわち、ライフゲームを人気数学ライターであるマーチンガードナーに送りました。ガードナーはそれをScientific American誌に紹介したところ[Ga70,Ga71]、大きな反響を呼びました。ライフゲームは２次元２状態のセルオートマトンで、そのルールは自分自身と周囲のセルの状態数の和によって定義された非常に単純なものでしたが、非常に複雑で予測しがたいダイナミクスを有していました。その後、ライフゲームは万能コンピュータ（万能チューリング機械）であることが証明されています[Be82]。これは簡単に言えば、ライフゲームが原理的には計算機で実行可能なすべての計算過程を作り出せることを示しています。ただし、それらが効率のよいアルゴリズムになる保証はありません。
またガードナーはエドワード・フレドキンが発見したフォンノイマンのもの比べ非常に単純なルールで自己複製ができるセルオートマトンすなわちフレドキン・ルールを紹介しました[Ga71]。フレドキンはガードナーによって紹介される10年程以前にそのルールを発見していました。このルールは余りにも単純なので、多くの人が度胆を抜かれたここと思います。（フレドキンルールのJAVA-Appletによるデモはこちら）
セルオートマトンの次のブームは１９８０年代半ば、イギリスの天才児ウルフラムによってもたらされました。彼は１次元のセルオートマトンを徹底的に調べ上げました[Wo83]。また、それらを時間発展の仕方から定性的に以下の４つのクラスに分けました。[Wo84]
- クラス１：セル空間がすべて同じ状態のセルに覆われてしまい、変化しなくなる。
- クラス２：セルの時間発展が局所化され、周期的または定常的になる。
- クラス３：セル全体がランダムな時間発展をする。
- クラス４：セルの時間発展は複雑で、局所化されている。また長い過渡状態を持つ。
さて、ウルフラムに少し遅れてセルオートマトン研究で高い評価を得たのがラングトンです。彼は今では人工生命研究の創始者として高い評価を受けていますが、３０歳代後半にロスアロモス研究所にポスドクとして雇われるまでは不遇の日々を送っていました。ただし、ミシガン大学で遺伝的アルゴリズムの創始者ホランドと出会ったことは非常に幸運だったといえるでしょう。（この辺のくだりは、[Wa92]に詳しく書かれています。）彼はウルフラムが4つのクラスについて述べた論文から示唆を受け、クラス１，２の秩序状態から、クラス４の複雑な状態を経て、クラス３に至る相転移を調べている間に、相転移が起きる場合すなわちクラス４を引き起こすルールには共通の性質があることに気づきました。すなわち次の瞬間、ある任意のセルが０以外の状態になる確率がある数を超えると秩序からカオスに変化することがわかりました。この確率はλパラメータと名づけられました。また彼は、このセルオートマトンの相転移が現実の世界の２次の相転移に非常に似ていることに気がつきました。ラングトンはセルオートマトンが臨界λ値をもつ時、すなわち相転移点において生命に必要な計算能力がもっとも高くなり[La90]、そのため複雑な計算能力を有する生命は規則的な体制（regime）からカオス的な体制に変化する間際の状態（カオスの縁）に存在すると予測しました。
我々の脳は脳細胞が連結されてできています。もし、ある刺激がクラス３のように脳全体をカオス状態にしてしまうほど脳細胞の連結の度合いが強かったなら、複雑な計算はできません。また連結の度合いが非常に弱く、クラス２のように刺激が十分伝わらなくて空間的に局所化されたり、クラス１のように刺激の影響がすぐに消えてしまったりしても不都合です。すなわち、どうしてもクラス４のような程よい連結の強さが必要なのです。
このようにカオスの縁の予測は、定性的は納得できるものの、どうしてカオスの縁が自発的に現れるのかは説明されていません。このことについて、パッカードがセルオートマトンのルールを遺伝的アルゴリズムによって進化させてやるとルールがカオスの縁に近づくと主張しています[Pa88]。これは「カオスの縁への適応」と呼ばれています。カオスの縁の概念（すなわち計算能力と相転移の相関）、およびカオスの縁への適応という仮説を、カウフマンのように受け入れる者[Ka93]もあれば、ミッチェルのようにパッカードの解釈を再検証する[Mi93a,Mi93b]もいます。
ラングトンはまた、フォンノイマンが手掛けた自己再生セルオートマトンに対しても興味をもちました。彼は生命は必ずしもユニバーサルコンストラクタである必要がないと考え、自己再生能力のみを満足するセルオートマトンを提案しました[La84]。このセルオートマトンはループと呼ばれ現在でも人工生命の研究で議論されています（ループのアプレットはこちら）．ループでは、予め決められた初期状態を与える必要があり、自己組織化とは言えない部分があります。また空間全体の状態を同時に更新すること（同期性）なども気になります。これはループというよりはセルオートマトン全体の属性です。明らかに同期性がないとセルオートマトンでパターンを作るのが著しく難しくなります。ループだけでなく、ゲームオブライフのグライダーなどの興味深いパターンも明らかに同期性に依存しています。また、ループやその拡張版では保存則を無視して、”化学物質”が無からあらわれます。このように保存則を無視して生命現象を議論できるのかという疑問もあります。ラングトンの一連の研究から10年以上が過ぎましたが、生命現象とセルオートマトンの研究はまだまだ謎でいっぱいです。
以上のように、セルオートマトンは生命現象の知られざる秘密を探りたいという目的で提案され、発展してきましたが、現在は画像処理や流体力学等の実用分野でも使われるようになってきています。残念ながらこれら実用分野での歴史は私の知識の範囲を越えるため、割愛しましたのでご了承下さい。
参考文献
[Be82] Berlekamp, E., Conway, J., Guy, R. (1982). "Winning Ways for your Mathematical Plays", Academic Press.
[Ga70] Gardner, M. "Mathematical games", 1970 Sci. Am., 223 October,
120-123.
[Ga71] Gardner, M. "Mathematical games", 1971 Sci. Am., 224 February,
112-117.
[Ka93] Kauffman, S. A. "The origin of order", Oxford University Press (1993).
[La84] Langton, C. G. "Self-reproduction in cellular automata", Physica D, Vol. 10, 135-144(1984).
[La90] Langton, C. G. "Computation at the edge of chaos: phase transition
and emergent computation", 1990 Physica D, 42, 12-37.
[Mi93a] Mitchell M. et al. "Revisiting the edge of chaos: evolving cellular
automata to perform computations", Complex Systems, 7, 89-130, 1993. (online paper)
[Mi93b] Melanie Mitchell, James P. Crutchfield, and Peter T. Hraber; "Dynamics, Computation, and the ``Edge of Chaos'': A Re-Examination" In G. Cowan, D. Pines, and D. Melzner (editors), Complexity: Metaphors, Models, and Reality. Santa Fe Institute Stuides in the Sciences of Complexity, Proceedings Volume 19. Reading, MA: Addison-Wesley. (online paper)
[Ne66] von Neumann, J. "Theory of self-reproducing automata", edited
and completed by A. Burks, University of Illinois Press, Champaign, IL
(1966).
[Pa88] Packard, N. H. "Adaptation toward the edge of chaos", Dynamic
Patterns in Complex Systems, 293-301, Singapore, 1988. World Scientific.
[Po92] Poundstone, W. "Prisoner's dilemma", Bantam Doubleday Dell Publishing
Group, Inc. (1992). （松浦俊輔訳 ”囚人のジレンマ −フォン・ノイマンのゲームの理論” 青土社、 1995).
[Su99] Suzudo, T. "Crystallisation of two-dimensional cellular automata", Complexity International,Vol. 6 (1999). to download pdf-formatted file
[Su00a] 鈴土知明 ”２次元セルオートマトンの相転移と結晶化”，複雑系研究会６， (1999) （物性研究 vol. 74 no.1, 59 (2000/4）) (to download pdf-formatted file of the paper)
[Wa68] J. D. Watson "The double helix", Weidenfeld Publishers Ltd. London (1968). （江上不二夫他 訳 ”二重らせん”講談社文庫 1986）
[Wa92] M. Michell Waldrop "Complexity -The emerging science at the edge of order and chaos", (1992)（田中三彦，遠山峻征 訳 ”複雑系”，新潮社 1997）
[Wo83] Wolfram, S. "Statistical mechanics of cellular automata" , Rev.
Mod. Phys. 55 (1983), 601-644. (Online paper)
[Wo84] Wolfram, S. "Universarity and complexity in cellular automata", 1984 Physica D, 10, 1-35. (Online paper)
Last Modified on 22, June, 2004