読者です 読者をやめる 読者になる 読者になる

どんなパターンもひたすら複製するセルオートマトン-フレドキンのパリティルール

 たまーに思い出したようにライフゲーム動画に見入って夜更かししてしまうことがある管理人です。

 もともとセルオートマトンは(現実世界の)機械による自己複製を研究するための道具として発明されたもので、(仮想的な世界である)平面格子上において自らと同じパターンを複製するような機械のモデルを作成できるかどうかが大きなテーマでした。先駆者であるノイマンによって29の状態を持つセルオートマトン上で動作する自己複製機械が示され、それはユニバーサルコンストラクタと名付けられました。
 具体的な内容についてはニコニコ動画に傑作動画がありますのでご覧になっていただきたいと思います。

リンク
 ライフゲームの世界 最終回【複雑系】 by はむくん 科学/動画 - ニコニコ動画

 今のようなコンピュータがない時代にこんなものを研究していたというのですから、全くとてつもない頭脳です;-o-)

 それはさておき、ここで紹介するのは、比較にならないほど単純なセルオートマトンです。フレドキンルールとして紹介されることもありますが、フレドキンズパリティルール、あるいは単にパリティルールと呼ばれることもあります。 
 このセルオートマトンはライフゲームと同様に2つの状態(生と死)しかなく、遷移のルールも次のように極めて単純なものです(いくつか類例がありますがもっとも簡単な例です)。

  • セルの上下左右にある計4つのセルのうち、生きているセルが1個または3個であれば、そのセルは次の世代において生きる
  • セルの上下左右にある計4つのセルのうち、生きているセルが0個,2個または4個であればそのセルは次の世代において死ぬ

 このセルオートマトンは、どんなパターンもそのまま複製します。セルオートマトン上で機械を設計する必要はなく、上記の遷移ルールだけで複製を実現します。

f:id:accs2014:20170107204053p:plain:right:w300

 Excelで実例を作ってみました。
 簡単なパターンを置いてスタートすると…


f:id:accs2014:20170107204052p:plain:right:w300

 怪しい模様が広がっていきますが;-o-)


f:id:accs2014:20170107204050p:plain:right:w300

 そのうち最初のパターンが4つになって現れます。この後も16個、64個…とどんどん広がっていきます。


f:id:accs2014:20170107204049p:plain:right:w300

 このようなパターンでも…


f:id:accs2014:20170107204048p:plain:right:w300

 まあ当然なんですが、複製の過程で交錯しつつ結局は最初のパターンが再び現れます。


f:id:accs2014:20170107204105p:plain:right:w300

 16倍に増殖した様子です。

 完全に遷移ルールに頼った形での増殖であり、自己複製の実現としては極端な例ですが、これはこれで興味深い一つの解答なのだろうと思います。