ライフゲーム () は1970年にイギリスの数学者ジョン・ホートン・コンウェイ () が考案した生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームである。単純なルールでその模様の変化を楽しめるため、パズルの要素を持っている。生物集団においては、過疎でも過密でも個体の生存に適さないという個体群生態学的な側面を背景に持つ。セル・オートマトンのもっともよく知られた例でもある。我々が暮らす空間、さらには時間が連続的なものであるか、それとも非連続的なものであるのか、という問いはギリシア時代から思索の対象となってきた。セル・オートマトンはその問いに答えるものではないが、空間、時間が不連続であった場合、どのような世界が形成されるのかを示してくれる。セル・オートマトンは、四角形などのセルによって分割された空間において、時間に最小単位が存在する場合の計算モデルである。1940年代にジョン・フォン・ノイマンとスタニスワフ・ウラムによって考案された。当時はコンピュータが発明された直後であり、セル・オートマトンの研究は、方眼紙と筆記具によるものである。フォン・ノイマンの関心は自己複製機械にあり、2次元セル・オートマトンによる自己複製機械の例を1952年に示している。セル・オートマトンが研究者以外の興味をひくきっかけとなったのが、ライフゲームである。1970年10月の『サイエンティフィック・アメリカン』誌のマーチン・ガードナーのコラム上で紹介されたところ多くの反響を呼んだ。サイエンティフィック・アメリカン誌が読者からの手紙を中心とした記事を何度も組んだほどである。興味深いことにライフゲームはチューリング完全（万能チューリングマシンの働きをするパターンが構成可能）であることが証明されている。これは、ライフゲームで、計算機で実行可能な全ての計算について、対応するパターンを作ることができるということを表している。ライフゲームの考案後すぐに、移動物体であるグライダーパターンと、長寿型のR-ペントミノパターンが発見された。当時は、このようなゲームの研究を目的として、コンピュータを利用できたのは限られた人々であったが、それらの人々の間にライフゲームは流行した。夜間あるいは未使用のコンピュータ上でライフゲームのプログラムが動かされることとなり、興味深いパターンが多数発見された。後にマイクロコンピュータの普及により、一定の人気を持つアプリケーションとして現在に至っている。その後、セル・オートマトンの研究はライフゲームのような2次元のタイプではなく、1次元を中心に進んだ。1980年には、スティーブン・ウルフラムによって1次元セル・オートマトンの4分類が完成し、クリストファー・ラングトンによって「カオスの縁」と呼ばれる概念が確立した。3次元以上のセル・オートマトンも研究対象となっている。ライフゲームでは初期状態のみでその後の状態が決定される。碁盤のような格子があり、一つの格子はセル（細胞）と呼ばれる。各セルには8つの近傍のセルがある (ムーア近傍) 。各セルには「生」と「死」の2つの状態があり、あるセルの次のステップ（世代）の状態は周囲の8つのセルの今の世代における状態により決定される。セルの生死は次のルールに従う。下に中央のセルにおける次のステップでの生死の例を示す。生きているセルは■、死んでいるセルは□で表す。ライフゲームでは世代を経ることで最終的に死滅する図形もある。生き延びる場合の変化は4パターンに分類することができる。コンウェイは「生きたセルの数が無限に増えつづけるパターンはありうるか」という問題に50ドルの懸賞金をかけた。コンウェイ自身は、そのようなパターンとして「周期的だが次々にグライダーを打ち出すもの」や「移動しながら通過した後に破片を残すもの」の存在を予想し、前者を「グライダー銃」、後者を「シュシュポッポ列車」と呼んだ。1970年11月、らは、初めてグライダー銃の具体例を挙げて賞金を獲得した。後にシュシュポッポ列車の具体例も与えられている。繁殖型としては、移動しながらグライダーを打ち出す「宇宙の熊手」(space rake) と呼ばれるものや、四方に向かって成長する「マックス」と呼ばれるものなど、様々なパターンが見付かっている。4つの分類における単純な例を以下に示す。周期が2で発生しやすい振動子には以下のようなものがある。周期が3以上のものでは、以下のようなものがある。繁殖型の中には時間の2乗に比例した増加を示すパターンがありそれらは「ブリーダー」と呼ばれる。これもゴスパーにより発見された。繁殖型には後にもっと単純なものが見つかっている。次の3つはいずれも、無限に増え続けるパターンに成長する初期配置である。1つ目のパターンは初期配置ではわずか10個のセルしか生きておらず（これが最少であることが証明されている）、2つ目のパターンは5×5に収まっている。3つ目のパターンはわずか1列である。（いずれも「スイッチ機関車」をベースとしたパターンになる。初期配置は小さいが、成長過程は単純ではない）成長過程が単純なものとしては、以下のようなシュシュポッポ列車がある。このパターンは、後方にブリンカーを残してゆく（図では2列が既に現れている）。非常に長い間変化を続ける長寿型（メトセラ）と呼ばれるパターンがある。「ダイハード」は130世代後に死滅するパターンであり、「ドングリ」(acorn) は13個のグライダーを生み出すのに5206世代かかるパターンである。オリジナルのライフゲーム以外にも様々な新しいルールを考えることができる。周囲に3つの隣人がいれば生命が誕生し、周囲に2つか3つの隣人がいれば生き残りそれ以外の場合では死ぬというルールである標準のライフゲームを23/3と表す。最初の数 (2,3) は生き残るために必要な数を表し、次の数 (3) は生命の誕生に必要な数を表す。従って16/6は、「6つの隣人がいればセルが誕生し、1つあるいは6つの隣人がいれば生き残る」ことを意味する。バリエーションの中では、23/36が有名である。と呼ばれ、オリジナルのルールに加えて、6つの隣人がいれば誕生するというルールを付け加えたものである。また、一般的なライフゲームでうまくいかない点を研究するために、3-4Lifeなどの変則ルールが多数作られている。また、「2次元平面とムーア近傍」以外の空間における、類似したルールによるセル・オートマトン、といったものも考えることができる。ライフゲームはチューリング完全であり、チューリングマシンと同等の計算能力を持つ。これは、ライフゲームのパターンで計算機を形成し、その上でプログラムを実行する事が可能である事を示している。計算機を構成するために必要な要素として、グライダーなどのパターンの組み合わせでAND、OR、NOTなどの論理ゲートを構築できる。グライダーを利用することで他のオブジェクトとの相互作用を得られる。例えばブロックを近くに運んできたり遠くへ移動させたりすることができる。この移動機構はカウンタとして利用できる。他にも様々な計算能力を持つパターンが発見されている。素数/乱数生成器や、ライフゲームを用いてライフゲームを計算する "Unit cell" などは、実際に動作する計算機としてのライフゲームの例である。

出典:wikipedia