ダイナミクスと密度分類問題(多数決問題)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/12/11 22:20 UTC 版)
「ルール184」の記事における「ダイナミクスと密度分類問題(多数決問題)」の解説
上記のルールの説明から、ダイナミクスの2つの重要な特性が浮き出る。まず、ルール184は周期的境界条件を持つ任意の有限集合のセルに対して、0と1の数を変化させない。ルール184とその対称は、0と1の数を変化させない唯一のこのタイプのセル・オートマトンルールである。無限に続く配列でも1の割合(密度)が明確に定義されていれば、0と1の割合は不変である。また、ルール184は左右対称ではないが左右反転と同時に0と1を入れ替えると同じルールのセル・オートマトンとなる性質を持つ。 ルール184では、全体が左か右に1マスずつ移動するように見えるパターンで安定する。具体的には、初期状態の1の割合が50%未満であれば右に移動するように見えるパターンとなり、1のセル同士は2マス以上離れる。逆に、初期状態の1の割合が50%を超える場合は左に移動するように見えるパターンとなり、こちらでは0のセル同士は2マス以上離れる。初期状態の1の割合が50%であれば、左に移動しているように見えるパターンと右に移動しているようにみえるパターンが織り交ざったように見えるパターンで安定化する。 密度分類問題(多数決問題)は任意の有限集合上で実行されたとき、最大多数のセルが保持する値を計算するセル・オートマトンを構築する問題である。ルール184は、周期的境界条件を有する有限集合状のセル上で実行された場合、0と1の数が等しくない場合には各セルは多い側の状態が連続する場面に無限回遭遇するが、少ない側の状態が連続する場面には有限回しか遭遇しないという意味では解決できる。密度分類問題は最終的にすべてのセルが最大多数の状態に安定する必要があるが、ルール184は0と1の数を変化させないため、全てのセルを最大多数の状態にすることは不可能である。しかし、ルール184は最大多数のセルの状態を認識することが出来るという条件では解決している。
※この「ダイナミクスと密度分類問題(多数決問題)」の解説は、「ルール184」の解説の一部です。
「ダイナミクスと密度分類問題(多数決問題)」を含む「ルール184」の記事については、「ルール184」の概要を参照ください。
- ダイナミクスと密度分類問題のページへのリンク