Euler's Eyes
2026-10-27
自己増殖オートマトン
晩年のフォン・ノイマンは、哲学のように聞こえる問いを自らに投げかけた。機械は自分自身の複製をつくることができるか。難しさは論理にある。複製をつくるには、機械は自分自身の記述を必要とする。だが記述は機械の一部なので、記述そのものも記述しなければならず、こうして終わりのない後退に陥る。
記述、構成機、複写機
1948 年からの講演でフォン・ノイマンが示した出口は、三つの部品を分けることだった。
- 任意の機械 $X$ の記述 $D(X)$ を読んで $X$ をつくる構成機 $A$
- どんな記述でも、理解することなく複写する複写機 $B$
- 二つをつなぐ制御機 $C$
さて、機械 $A + B + C$ に、それ自身の記述 $D(A + B + C)$ を与える。構成機は記述を読んで新しい機械 $A + B + C$ をつくり、複写機は記述の写しをつくって新しい機械に渡す。結果は、自分自身の記述をもった完全な複製である。後退が止まるのは、記述が二通りに使われるからだ。一度は実行すべき命令として、もう一度は読まずに写すテキストとして。
セルの格子
このアイデアを厳密にするため、フォン・ノイマンには機械を組み立てられる単純な「宇宙」が必要だった。ウラムの提案で、彼は小さな正方形からなる無限の格子を使った。各正方形は 29 の状態のどれかにあり、すべてが各ステップで同時に、四つの隣の状態に応じて変わる。この格子の中に、彼はテープを読み、自分自身の複製をつくり、テープを写すことのできる、途方もない数のセルからなる巨大な配置を設計した。この仕事は彼の死の時点で未完成だったが、共同研究者のアーサー・バークスが完成させ、1966 年に『自己増殖オートマトンの理論』という題で出版した。
こうした格子は今日セル・オートマトンと呼ばれる。1970 年、イギリスのジョン・コンウェイは、生と死の二つの状態しかなく、規則も一行で済むものを発明した。生きたセルは生きた隣（斜めも数える）が 2 個か 3 個なら生き残る。死んだセルは生きた隣がちょうど 3 個なら誕生する。それ以外は死ぬか、死んだままである。コンウェイがライフゲームと呼んだこの仕組みはきわめて豊かで、その中でも計算機や自己複製する機械を組み立てることができる。
練習：ブリンカー
ライフゲームで、横一列に並んだ三つの生きたセルは「ブリンカー」をなす。次のステップでそれが縦一列になることを示せ。
真ん中のセルは生きた隣が 2 個なので生き残る。両端のセルは生きた隣が 1 個しかないので死ぬ。真ん中のすぐ上とすぐ下の二つのセルは、生きた隣がちょうど 3 個（横列の三つ）なので誕生する。結果は縦一列の三つである。同じ推論で、次のステップには再び横になり、この模様は永遠に点滅し続ける。
練習：なぜ複写機が要るのか
フォン・ノイマンの機械には、なぜ複写機 $B$ が必要なのか。構成機 $A$ が記述もつくればよいのではないか。
命令から記述をつくるには、記述がそれ自身の記述を含まなければならず、それがまた別の記述を含み、と続く。はじめの無限後退である。複写機はこれを避ける。記述を記号の列として写すので、そのために別の記述を必要としないのだ。
出典： John von Neumann, “The general and logical theory of automata”（1948 年の講演、1951 年刊）· John von Neumann、Arthur W. Burks（編）, Theory of Self-Reproducing Automata（1966）· Martin Gardner, “The fantastic combinations of John Conway’s new solitaire game ‘life’”, Scientific American（1970）。