私は最近、人工生命について読んでいて、 「コンウェイのライフ ゲームは、普遍的な機械として分類されるのに十分な複雑さを示している」という記述に出くわしました。私はユニバーサル マシンとは何かについて大まかにしか理解していませんでした。ウィキペディアは、ウィキペディアがかつてないほど理解に近づいただけでした。誰かがこの非常にセクシーな声明に光を当てることができるのだろうか?
コンウェイのライフ ゲームは、私には、いくつかの途方もない含意を伴う素敵な気晴らしのように思えます。それは私がすべき飛躍ですか？
Paul Rendellは Life でチューリング マシンを実装しました。グライダーは信号を表し、それらの間の相互作用は、チューリング マシンを実装するより大きなコンポーネントを一緒に作成できるゲートとロジックです。
基本的に、AND、OR、および NOT を実装できる自動機械は、チューリング完全になるのに十分な複雑な方法で組み合わせることができます。これは計算に役立つ方法ではありませんが、基準を満たしています。
Conway の人生からチューリング マシンを構築することはできますが、それはかなり恐ろしいことです。
キーはグライダー(および関連するパターン) にあります。これらは競技場に沿って (ゆっくりと) 移動するため、ビットの流れを表すことができます (1 の場合はグライダーの存在、0 の場合は存在しません)。グライダーの 2 つのストリーム (直角) を取り込み、元の 2 つのストリームの AND/OR/etc に対応する別のビット ストリームを放出するように、他のパターンを構築できます。
編集: これについては、LogiCell の Web サイトに詳細があります。
Conway の「Life」はさらに進化します。Universal Turing Machine を実装する Life パターンを構築できるだけでなく、Von Neumann の「Universal Constructor:」http://conwaylife.com/wiki/Universal_constructorも構築できます。
「ユニバーサル コンストラクター」は、それ自体のコピーを含む任意のパターンのセルを構築するようにプログラムできるため、コーウェイの「ライフ」は、ユニバーサル計算だけでなく、「自己複製」が可能です。
Poundstone の The Recursive Universe という本を強くお勧めします。絶版ですが、おそらく良い図書館でコピーを見つけることができます. それはほとんどすべて、コンウェイの生命の力と、その一連の自然法則を備えた宇宙に存在できるものに関するものです。これには、自己複製エンティティと IIRC、ダーウィンの進化が含まれます。
そして、ポール・チャップマンは、「ユニバーサル・ミンスキー・レジスター・マシン」を構築することにより、実際にゲーム・オブ・ライフを備えたユニバーサル・チューリング・マシンを構築しました: http://www.igblan.free-online.co.uk/igblan/ca/ .
パターンは、30x30 の正方形の格子上に構築されます。Lightweight Spaceships (LWSS) は、P60 ロジックを持つコンポーネント間の通信に使用されます (レジスターを除く - 以下を参照)。LWSS は、格子正方形を横切るのに 60 世代かかります。したがって、60 世代ごとに、コンポーネント間 LWSS (パルス) は、その正方形に対して同じ位置にあり、回転を可能にします。
.