24

ウィキペディアの記事やここでの回答が何を言っているのか、頭を悩ませることはできません。だれかルール 110 を簡単に説明できますか? チューリングの完全性をどのように保証しますか?

4

4 に答える 4

8

簡潔で素人の用語説明の私の試み：

  • ルール 110 は基本的なセル オートマトンです。1 と 0 の有限パターンを 1 と 0 の別のパターンに変換するためのルールです。
  • ルール 110 が特定の入力ビット シーケンスに繰り返し適用されると、入力ビットで見つかったサブシーケンスに応じてパターンが出現します。十分な反復が行われると、次のことが起こります。
    • 元のサブシーケンスは、元の入力と同じ場所に表示されます。
    • 元のサブシーケンスは保持されますが、ビットフィールド内の別の場所に「移動」します。
    • 互いに向かって移動する 2 つのサブシーケンスは相互作用し、互いに「通過」します。
    • 2 つのサブシーケンスが結合して、新しいサブシーケンスが作成されます。
  • 異なるサブシーケンスには、サイクリック タグ システムの要素に対応する「1」、「0」、「クロック パルス」、または「生成規則」などの記号的な意味を与えることができます。
  • 慎重に構築された入力ビットフィールドでルール 110 を何度も繰り返すことで、サブシーケンスの相互作用が循環タグ システムの動作をシミュレートします。
  • サイクリック タグ システムを使用して、ユニバーサル チューリング マシンをシミュレートできます。したがって、サイクリックタグシステムはチューリング完全です。
  • ルール 110 は循環タグ システムをシミュレートできるため、これもチューリング完全です。
于 2013-02-18T23:27:02.370 に答える
7

詳しい説明をしてみましょう: 明らかに多くの詳細が省略されていますが、この記事ではすでに非常に複雑な証明の詳細を探しているとは思いません。

あなたが引用した記事から引用するには：ルール 110 オートマトンには次の一連のルールがあります..." (次のウィキペディアの表を参照)

データとして見ることはできますが、コードの表現として捉えることができます (コードをデータとして表現することは、チューリングの完全性を証明するために必要です。これはチューリングの元の結果に戻ります)、開始点は次のシーケンスです。 0 と 1 は、必ずというわけではありませんが、多くの場合、0 だけを含むセルで両側が囲まれています。規則 110 は、そのシーケンスがどのように進化するかを示しています。たとえば、1 つの行に 3 つの 1 のパターンがある場合、真ん中の 1 は次の行で「死ぬ」(0 に変わる) でしょう。その 2 つの隣人に何が起こるかは、パターンがそれらを超えてどのように拡張するかによって異なります。表示されている三角形の図は、元の状態からのオートマトンの進化をグラフィカルに表現したもので、1 を黒、0 を白としてコーディングし、上から下への進化を表しています。

チューリングの完全性の証明の 2 つの変わった特徴は、第一に、このような非常に単純なルールが、お気に入りのプログラミング言語で実行できるすべてのことを実行できる可能性が非常に低いことです。その魔法を働かせるには、無限に長く繰り返される背景が必要です。しかし、これについて根本的に不正なことは何も見当たりません。チューリングが最初に行ったように、潜在的に無限または半無限の空のテープを想定するのと同じです。

証明を適切に理解するには、開始パターンでデータ (および後でコード) がどのようにエンコードされるかを把握する必要があります。また、サイクリック タグ システムに精通していると、非常に役立つように見えます。私はそれらを説明する人ではありません。

コンウェイの「ライフ ゲーム」などの 2 次元セル オートマトンで状況を理解するのは難しいように思えるかもしれませんが、「グライダー」、「グライダー ガン」、「フグ列車」を研究して、そのゲームで遊ぶことは有益であることがわかりました。と他の面白い構造。(フグの列車はグライダー銃を構築し、グライダー銃はグライダーを発射します)。これらは、このオートマトンのチューリング完全性を確立するためにも使用できます。

また、トーク ページも参考になるかもしれません (要点を理解していないのはあなただけではありません。「写真は私には意味がありません..」で始まるエントリを参照してください)。

于 2013-02-18T18:32:05.240 に答える
6

1970 年にジョン・コンウェイがライフ ゲームを発明しました。

それ以来、ほぼすべてのプログラマーがその実装を書こうとしたと思います。確かに私はずっと前に書きましたが、とても楽しかったです。

このゲームは実際にはセルオートマトンであり、無限の 2 次元平面内のセルの世代間に単純なルールを設定します。たとえば、現在の世代のセルで生きている隣接セルが 2 つ未満の場合 (ビット値1)、次の世代の孤独で死ぬはずです。生きている隣人が 3 人以上いる場合、過密状態で死ぬはずです。空の (ビット値0、またはデッド) セルにちょうど 3 つの隣接セルがある場合、そのセルは生まれます ( になります1)。

それ以来、ライフ ゲームは驚くほど複雑であることがわかってきました。進化し続ける非常に複雑なパターンを多数生成することができます。また、チューリング完全であること、つまり、セルの組み合わせをプログラムとして開始し、結果として最終的な組み合わせを使用して、任意の複雑なアルゴリズムをエンコードできることが示されました。しかし、グライダーや銃のような複雑な形状を実際に生成する方法を見つけるのに数年かかりました。

さて、ルール 110 とは何かに戻りましょう。簡単に言えば、ルール 110 はライフ ゲームの一次元バリエーションです。

110 は、バイナリ文字列01101110の 10 進数表現です。これは、セル (ビット) の現在の世代が次のセル (ビット) にどのように変換されるかを表すルール システムの短い形式です。これは、ライフ ゲームの孤独または過密状態で死にかけているセルのルール システムと同様です。ちょうど3つの隣人を持つことから生まれました。

ライフ ゲームと同様に、ルール 110 がチューリング完全であることが証明されています。プログラムとして開始セル (ビット) の組み合わせを使用し、結果として最終ビットの組み合わせを使用して、任意の複雑なアルゴリズムをエンコードできます。

于 2013-02-19T07:24:01.767 に答える