1. ライフゲーム

1.1 ライフゲームとは

ライフゲームには，勝者も敗者もいません。 あらかじめ定められた簡単なルールに従って変化していく PC の画面をただ眺めているだけなのです。 だから， 例えていうなら 万華鏡 に近いです。 今日の授業は，画面上に現れる様々なパターンを眺めて楽しむことが目的です。

ライフゲームのルールは非常に簡単です。 画面上にはセルと呼ばれる一つ一つの区画が用意されています。 これが，2 次元上に配置されてライフゲームの世界を構成しています。 ライフゲームの画面は，それ自身が一つの世界なのです。 そこにはさまざまな現象が発生する，ある物理法則によって支配された世界です。

今回配布するライフゲームでは，青のセルが生命がいる状態を表わし， 白いセルが，そこの生命がいない状態を表します。 つまり，あるセルには生命がいるかいないかのどちらか，0 か 1 か， 存在か無か，オンかオフか，という 2 つの状態しかありません。 そして，時間の流れは一定で離散的です。 一つの時刻の単位を世代と呼ぶこともあります。 次の瞬間に，あるセルに生命が産まれるか否かは，一つ前の状態に依存します。 つまり次の時間にどういう状態になるのかは，一つ前の状態から完璧に予測できるのです。 それにもかかわらず，予想もしなかったような複雑な未来を観察することができます。 スローガン的に書けば 「単純な法則から複雑な結果が生じる」 ということになります。

1.2 ラプラス的宇宙観の崩壊

18 世紀のフランスの数学者ラプラスは， この宇宙を創造した全知全能の神は宇宙の全ての原子の詳細を知っていると考えました。 この宇宙を支配する物理法則と宇宙を構成する原子の全情報が分かれば， 全知全能の神は，未来を予知でき，過去を再構成できると考えました。 このような世界観には，不仮定な要素は一切存在しません。 全知全能の神にはすべてのことは予測可能だというのです。 別の言い方をすれば，ラプラスは，この宇宙を一つの巨大な機械だと考えていました。

しかし， このような考え方は，19世紀の終わりから始まる，量子論と相対論によって瓦解してしまいます。 量子論は不確定性を含みます。物理学者よれば，量子の世界では宇宙は非決定的なのです。 量子論によれば，ある電子のふるまいを確実に予測することは不可能なのですから， 未来の予測もまた不可能であるということになります。

さらに20世紀に入ると， 「単純な法則から複雑な結果が生じる」を具現化する現象がつぎつぎに発見されました。 今日「カオス」「複雑系」と呼ばれる現象（あるいはその研究分野）においても， 単純な法則からほとんど予測不可能な複雑な結果が生じることがあることが繰り返し確認されています。

ライフゲームもそうした単純な法則，複雑な結果を具現化したデモンストレーションなのです。

1.3 ライフゲームのルール

では，ライフゲームのルールを説明しましょう。 どのセルにも 8 個の隣接するセルがあります（ムーア近傍と呼ばれたりします）。 どの時刻においても，この近傍のセルがオンであるかオフであるかによって， 次の時刻でそのセルがオンになるかオフになるかが決まります。

• セルの状態がオンのとき：8 個の近傍のセルのうち，2 つあるいは 3 つのとき，そのセルは次の世代でもオンになります。
• 一方，8 個の近傍のセルがそれ以外のとき（0,1,4,5,6,7,8）は，次の世代でオフになってしまいます。
• セルの状態がオフのとき：8 個の近傍のセルのうち 3 つがオンのとき， 次の世代でそのセルはオンになります。
• 一方，それ以外のとき（0,1,2,4,5,6,7,8），次の世代もオフであり続けます。

ライフゲームのルールはこれだけです。

これをなぜライフゲームと呼ぶのかについてですが， ライフゲームの開発者であるコンウェイは，バクテリアなどの単純な生命体が培養器の中で増殖するパターンをシミュレートしたかったかららしいです。 このたとえでいけば，ライフゲームのルールは次のように解釈できます。 すなわち，周囲に 2 個未満しか仲間がいないセルは孤独のため死んでしまう。 逆に周囲に 4 個以上仲間がいるセルは，過密のため（栄養状態の不足など）にやはり死んでしまう。 周囲に 2 個または 3 個の仲間がいる状態が，過疎でも過密でもない健全な状態だと考えるわけです。 また，そのセルが空の場合，周囲に 3 個の仲間がいると性交によって新しい生命が誕生する， と考えられます。

ライフゲームの開始時に，プレーヤーがすべきことは，初期状態を決めることです。 一旦ゲームがスタートしてしまえば，あとは何もすることがありません。 ただ画面を眺めているだけです。

1.4 ライフゲームの遊び方

1.4.1 画面の説明

画面の大半を占める部分には，2 次元上のセルが見え，その下にメニューがあります。

左から「スタート」「ストップ」「クリア」「セーブ」「ロード」という 5 つのボタンであり， 一番右はチョイスボタンになっており， 「ノーマルマージン(Normal Margin)」か「惑星ワトール(Planet Wator)」かを， 選べるようになっています。

注意：Windows でこのライフゲームを動かすとボタンの文字が表示されないというバグがあります。 原因は，調査中ですが，まだ理由は分かっていません。 したがって，Windows でプレイする場合，ボタンの順序が 左から「スタート」「ストップ」「クリア」「セーブ」「ロード」であることを 覚えておいてください。ボタンの文字が表示されないだけであって， 各ボタンをクリックするば，そのとおりの動作はします。 また，Windows のコマンドプロンプトから，java LifeGame で起動した場合， 終了できないというバグも取りきれていません。 終了するには，コマンドプロンプトのウィンドウに戻って，コントロールキーを押しながら C をタイプしてください。

チョイスボタンの「ノーマルマージン」と「惑星ワトール」について説明します。 ライフゲームは本来，無限に広がる 2 次元状の世界を扱います。 ですが実際のコンピュータでは表示に限界があるため，端の扱いが問題になります。 「ノーマルマージン」とは，最端のセルの外側には何もないように振る舞うことを意味します。 一方「惑星ワトール」を選ぶと， 一番右端のセルの隣りに一番左端のセルがつながっているように動作します。 同様にして，一番上のセルのさらに一つ上は，一番下のセルにつながっています。 したがって，「惑星ワトール」を選択した状態で， 画面を右から左に移動するパターンがあったとすると， そのパターンは一番左までくると，次の時刻に，突然右端から現れます。 「ノーマルマージン」ではそのようなことはありません。

1.4.3 初期状態の入力

画面上のセルをマウスでクリックすれば，セルは青くなります。 もう一度そのセルをクリックすれば，白に戻ります。 青がオンの状態を現し，白がオフです。 セルのいくつかをクリックして初期状態を決めれば，後は「スタート」ボタンを押すだけです。

動作を中止したければ，「ストップ」ボタンを押し， 次に「クリア」ボタンを押せば全てがオフの状態に戻ります。

1.4.4 データの読み込みと保存

実習で用いる代表的なパターンはあらかじめ data というディレクトリに保存されています。 「ロード」ボタンを押すと別ウィンドウが開いてデータを読み込むことができます。 また，自分で作成した初期状態は，「セーブ」ボタンで保存しておくことができます。

なお，読み書きされるデータファイルは csv 形式ですので，エディタ，ワープロ， スプレッドシートなどで読み書きすることもできます。0 がオフで 1 がオンとなっています。

2 生命とは何か

ここでライフゲームからちょっと離れて，生命とはなにかについて考えてみましょう。

生命とは何か？と問われれば，究極的には， 自己複製することができる機械 ということになると言われています (結婚に失敗してしまった私は今のところ自己複製する見込みが無い壊れた機械ですなーT_T) 。 このこと， すなわち自分自身と同じものを創り出すことができる能力を持った人工生命体を作ろうという試みを紹介しましょう。 イギリスの進化遺伝学者，ジョン・メイナード＝スミスは生命のことをこう語っています。 「増殖すること，多様性を持つこと，形質の継承をそなえたものが生きているものであり， これらの性質のうち，一つでも欠けているものは生命とはいえない」 多様性と形質の継承についてはのちほど考えます。 彼はまた「遺伝的なプログラムを持つかどうかが，生命とそうでない物質との絶対的な違いだ。 生気のない世界の中で，これに相当するものはない。人間の作ったコンピュータをのぞいては」 とも書いています。

ご存知のとおり，地球上のほとんどあらゆる生物は遺伝子 DNA を持っていますが， この DNA に書き込まれた情報が， 親から子へと遺伝することで生命が紡ぎ出されています。 ということは DNA に書き込まれている情報が解読できれば生命の不思議 （の少なくともある部分）は解明されたと言って良いでしょう。 これが分子生物学の基本的発想ということはよく知られているとおりですね。

これもよく知られているとおり， DNA の中の塩基配列と呼ばれる部分は，4種類しかありません。 アデニン，チミン，シトシン，グアニンという 4 種のヌクレオチドを意味する 4 文字のアルファベット A, T, C, G の配列です。 生きている細胞はゲノムの情報を伝達するために二重らせん構造の DNA を用いています。 すなわち遺伝情報はこの 4 文字のアルファベットによって書かれていることになります。 ちなみに，人間の DNA 配列は約 60 億対あります。 ちょっとした雑学的知識ですが， 万物の霊長たる人間の　DNA　より，イモリの　DNA　の量の方が多いのです（知ってました？）。 そのイモリよりもさらに百合の方が DNA の量は多いです。 人間→天使→神を頂点とする中世キリスト教的生命観は， ここでも脆くも崩れ去ります。 天動説や進化論なども中世キリスト教的世界観を打ち壊してきましたよね。

遺伝情報が 4 文字のアルファベットで書かれているとすれば， （つまり遺伝情報は 30 億年前の生命誕生以来，アナログではなくデジタルです） この情報はデジタル表現が得意なコンピュータ上でも表現できるわけです。 親の持っている情報を複製し， 再生産するメカニズムだけを取り出してプログラムしてやろうというのが人工生命ということになります。 マダムタッソウのロウ人形のように，忠実に詳細を再現しても，動けなければ生命ではありません。 たとえ，それが動いたとしてもゼンマイ仕掛けでは，自己複製はできません。 こう考えてくると，生命の実際の形態を模倣するよりも， いかにして自己複製する機構を創り出すのかという方が重要だろうという発想です。 これが人工生命に関する研究なのです。

人工生命の研究自体は 20 世紀半ばから（ジョン・フォン・ノイマンにより始められました。 彼は，ハンガリー生まれの数学者であり，コンピュータの生みの親でもあります。 現在広く使われているコンピュータのことを，彼の名前をとってノイマン型と言ったります。 またアメリカの原子爆弾開発計画に関与したことでも知られています）あり， さらに 1970 年に非常に簡単なプログラムが考案されブームとなりました。 そう，このゲームがライフゲームというわけです。

2.1 オートマトン

オートマトンとは，本来自動人形の意味というです。 意志をもたず，過去および現在に受けた刺激だけで行動が決定される自動機械あるいは生物をさします。 オートマトンを数学的に記述する場合， 入力信号と出力信号とを結ぶ媒介として内部状態という概念を用います。 内部状態は有限個で，入力信号により内部状態が変わり， また出力信号は内部状態の関数として定まります。 これらの対応関係を表わす関数は明確な形で構成的に定義されます。 この対応関係を論理式あるいはこれを拡張したものによって定式化したり， 具体的な基本要素の組み合わせとして与えられた条件に適するオートマトンを構成することなどが，オートマトン理論の目標となります。 数学的には準群の理論を用いて研究されています。 オートマトンの理論は不連続な入出力に対する回路論， フィードバック理論に相当するものとも考えられます。

2.2 セルオートマトン（セルラオートマタ cellular automata)

空間を微小な格子に分けて各格子（セル）に離散的な値をとる何らかの量を定義し， さらに時間も離散化して，各量の変化を決める規則を導入することにより， 空間的な構造の時間発展を研究する理論体系をセルオートマトンと呼びます。 i 番目の格子における n ステップ目の時刻での量を u_i⁽ⁿ⁾ と表わすと， この規則は，

と表わされます。時刻 n+1 での量 u は，一時刻前 n の状態によって定まるとするわけです。 ただし，j は u_i の変化にかかわるすべての格子をさすものとします。 この式は，現実の複雑な挙動を，簡単なモデルによって研究するときにしばしば用いられます。 規則を表わす関数 F_i はすべての i に共通のものを採用し， j も i も近接する格子に限る場合が多いです。ライフゲームもそうですね。 セルラオートマタは，数学の分野でいう離散力学系の一種です。

セルラオートマタは，セルによって分割された空間において， 時間に最小単位が存在する場合の計算モデルです。 1940 年代にジョン・フォン・ノイマンとスタニスワフ・ウラムによって考案されました。 当時はコンピュータが発明された直後であり，セルラオートマタ（セルオートマトンともいう）の研究は，方眼紙と筆記具によるものでした。 フォンノイマンの関心は 自己複製機械 にあり， 2 次元セル・オートマトンによる自己複製機械の例を 1952 年に発表しています。 セル・オートマトンが研究者以外の興味をひくきっかけとなったのが， ライフゲームというわけです。 1970 年 10 月のサイエンティフィック・アメリカンという雑誌に， マーチン・ガードナーが紹介したことで反響を呼びました。 サイエンティフィック・アメリカン誌が読者からの手紙を中心とした記事を何度も組んだのだそうです。 興味深いことに， ライフゲームは 万能チューリングマシン であることが証明されています。 これは， ライフゲームは計算機で実行可能な全てのアルゴリズムを作ることができるということを表しています。 サイエンティフィック・アメリカン誌の出版後すぐに， グライダーパターンとR-ペントミノというパターンが発見されました。

これらのパターンの発見やコンピュータの普及によってライフゲームは流行しました。 夜間あるいは未使用のコンピュータ上でライフゲームのプログラムが動かされることとなり， 興味深いパターンが多数発見されました。 その後、セル・オートマトンの研究はライフゲームのような 2 次元のタイプではなく， 1 次元を中心に進みます。 1980 年には， スティーブン・ウルフラムによって 1 次元セル・オートマトンの 4 分類が完成し， クリストファー・ラングトンによって 「カオスの縁」 と呼ばれる概念が確立しました。 また，3 次元以上のセル・オートマトンも研究対象となっています。

3 生成されるパターンの多様性

コンウェイは，動作の振る舞いが予測不可能であり，かつ，状態遷移ルールが できるだけ単純なオートマトンを探してきました。 すなわち，物理現象がわずかな基本的な法則に凝縮される宇宙のモデルです。 物理学者は未だ，そういった基本的な法則を見つけ出していませんが， もしこのような法則があるとすれば， 化学，生物学，心理学の最も複雑な構造さえも説明するものでなければならないはずです。 もし，物理学者がそのような基本法則（後ほどこの問題に立ち返ります ） を導くことに成功したとしても， 現実の世界同じように神秘的であり続けることをライフゲームは示しているのです。

3.1 一列に並んだセル

たとえば，一列に並んだセルを初期状態としてスタートさせた場合， 何が起こるか見てみましょう。 先述のとおり，何が起こるかは，最初に並べたセルの長さによって決定論的に定まっています。 ですが，セルの長さの違いによる振る舞いの変化には目を見張るものがあります。 是非各自実行してみてください。

• 一列に並んだ 3 つのセルは「信号点滅機 blinker」と呼ばれます。 blinker は永遠に点滅を繰り返す最小のパターンです。
  
  信号点滅機 blinker
• 4 つの場合は，「蜂の巣 beehive」に変化します。
  
  蜂の巣 beehive
• 5 つの場合には，4 つの「点滅信号機 blinker」に変化します。
• 6 つの場合，12世代かけて消滅していきます。
• 7 つの場合には，爆発して4つの「蜂の巣 beehive」になります。
• 8 つの場合，最終的に 4 つの「ブロック block」と 4 つの「蜂の巣 beehive」に変化します。
  
  ブロック block
• 9 つの時には，8つの「信号点滅機 blinker」になります。
• 10 個のセルのときにできるパターンは「ペンタデカスロン pentadecathlon」という 15　回ごとに元の形に戻るパターンです。
  
  ペンタデカスロン
• 11 個のときには，2 つの「点滅信号機 blinker」に縮退します。 これは13 個のときにも同じ結果になります。
• 12 個の並んだセルの時には 2 つの「蜂の巣 beehive」になります。
• 14 個と 15 個の時には引き延ばされる形で，最終的に消滅します。
• 16 個の時には，8 個の「点滅信号機 blinker」からなる「交通信号 traffic light」という動き続けるパターンになります。
• 17 個の時には，4 つの「ブロック block」へと変化します。
• 18 個の時と 19 個の時には消滅してしまいます。
• 20 個の時には 2 つの「ブロック block」になります。

これらの全てに共通する法則は未だに誰も知りません。 まさにこれこそが，コンウェイがライフゲームを楽しんだ理由なのでしょう。

3.3 無限に増殖するパターン

また，コンウェイは，無限の成長を続けるパターンがあるのかを問題としました。

ただし，この問題はただコンピュータを眺めているだけでは絶対に解くことができません。 スクリーンを越えて広がっていくパターンを思いつくだけでは不十分で， その成長が永遠に続くものであることを証明しなければなりません。 つまり，数百万世代経ても消滅することのないことを証明する必要があるのです。 次の図の，r-ペントミノ r-pentomino やドングリ acron の成長パターンが無限であることを示すことは， 簡単に手に負える類いの問題ではないことを示しているように思われます。

3.4 さまざまパターンの例

ライフゲームでは世代を経ることで最終的に死滅する図形が多いです。 生き延びる場合の変化は 4 パターンに分類することができると言われています。

1. 固定型は世代が進んでも同じ場所で形が変わらないものを指します。
   
   固定型の例。左からブロック，蜂の巣，ボート，船，池と呼ばれます。
        
   固定型の例。左から，はしけ barge，へび snake，イーター eater，標識
2. 振動型はある周期で同じ図形に戻るものを指します。
   
   振動型の例。左からブリンカー，ヒキガエル，ビーコン，時計，と呼ばれます。
3. 移動型は一定のパターンを繰り返しながら移動していくものを指します。 グライダー glider と呼ばれるものが有名です。
   
   移動型の例。左からグライダー，軽量級宇宙船，中量級宇宙船，重量級宇宙船，と呼ばれます。
4. 繁殖型はマス目が無限であれば無限に増え続けるパターンであす。

   先述のとおりコンウェイは「無限にセルの数が増えつづけるパターンはありうるか」 という問題に懸賞金をかけ，1970 年 11 月にゴスパー (Bill Gosper) により解かれました。 30　世代毎にグライダーを打ち出す「グライダー銃」と呼ばれるパターンです。

   
   グライダーガン

   繁殖型には他にも， 本体が通過した後に破片を残していく「シュシュポッポ列車」 (puffers) や， 宇宙船が集まって移動しながらグライダーを発射していく「宇宙艦隊」と呼ばれるものを含め様々なパターンが見つかっています。

   また，繁殖型の中には時間の2乗に比例した増加を示すパターンがあり， それらは「ブリーダー」と呼ばれています。これもゴスパーにより発見されました。 繁殖型には後にもっと単純なものも見つかっています。 次の3つはいずれも無限に増え続けるパターンです。

    
   
   ブリーダー

   1 つ目のパターンは初期配置ではわずか 10 個のセルしか生きておらず（これが最少であることが証明されている）， 2 つ目のパターンは 5×5 に収まっています。 3　つ目のパターンはわずか 1 列です。

3.5 長寿型

非常に長い間変化を続ける長寿型（メトセラ）と呼ばれるパターンがあります。 「ダイハード」は 130 世代後に死滅するパターンであり， 「ドングリ」(acorn)は 13 個のグライダーを生み出すのに 5206 世代かかるパターンです。

グライダーを利用することで他のオブジェクトとの相互作用を得ることができます。 例えばタイミングよくいくつかのグライダーを打ち出すことでブロックを近くに運んできたり遠くへ移動させたりすることができます。 移動機構はカウンターをシミュレートしていると考えることができます。 グライダーなどのパターンの組み合わせで AND，OR，NOT ゲートを構築することができます。 現在に至るまで他にも様々な性質を持つパターンが発見されていて， グライダー銃による論理ゲート以外にも，素数生成器や大規模でゆっくりとした速度でライフゲーム をエミュレートする unit cell などが発見されています。

ライフゲームのパターンは チューリング完全 であり， ライフゲームはチューリングマシンと同等の計算能力を持つ ことが示されています。 つまりライフゲームの計算能力は昨今のコンピュータと同等なのです。 ライフゲームはパターンで表現されたプログラムを実行するコンピュータであると言うことができるのです。

7 参考文献

1. ウィリアム・パウンドストーン/有澤誠訳. (1990). ライフゲイムの宇宙. 日本評論社.
2. カール・シグムンド/冨田勝監訳. (1996). 数学でみた生命と進化. 講談社ブルーバックス.
3. スティーブン・レビー/服部桂役. (1996). 人工生命. 朝日新聞社.