多数派の問題

多数決問題、または密度分類タスクは、多数決投票を正確に実行する 1 次元セルオートマトンルールを見つける問題です。

ローカル遷移ルール​​を使用すると、セルはシステム内のすべての 1 の合計数を知ることができません。1 の数 (または、対称性により、0 の数) を数えるには、システムの合計サイズに対数ビット数が必要です。また、システムのサイズに線形の距離でメッセージを送信し、システムが非正規言語を認識する必要があります。したがって、この問題は、セルオートマトンシステムの計算能力を測定するための重要なテストケースです。

合計i + j個のセルを持つ 2 状態セルオートマトンの構成が与えられ、そのうちiはゼロ状態にあり、jは 1 状態にある場合、投票問題の正しい解決法は、 i  >  jの場合は最終的にすべてのセルをゼロに設定し、 i  <  jの場合は最終的にすべてのセルを 1 に設定する必要があります。 i  =  jの場合、目的の最終状態は指定されていません。

この問題は、0 と 1 の割合が 50% 以外のしきい値を超えているか下回っているかをテストするように一般化することもできます。この一般化では、しきい値 も与えられます。投票問題の正しい解決法は、 の場合に最終的にすべてのセルを 0 に設定し、 の場合に最終的にすべてのセルを 1 に設定する必要があります。 の場合、望ましい最終状態は指定されていません。 ${\displaystyle \rho}$${\displaystyle {\tfrac {i}{i+j}}<\rho }$${\displaystyle {\tfrac {j}{i+j}}>\rho }$${\displaystyle {\tfrac {j}{i+j}}=\rho }$

Gács、Kurdyumov、Levinは、多数決問題を常に正しく解くわけではないが、多くの場合正しく解くオートマトンを発見した。^[1]彼らの問題へのアプローチでは、セルオートマトンルールの品質は、正しく分類される可能性のある開始構成の割合によって測定されます。 ${\displaystyle 2^{i+j}}$

Gacs、Kurdyumov、Levin が提案した規則では、各セルの状態を次のように設定します。セルが 0 の場合、次の状態は、そのセル自体、そのセルのすぐ左隣のセル、そのセルの 3 マス左隣のセルの値の過半数として形成されます。一方、セルが 1 の場合、次の状態は対称的に、そのセル自体、そのセルのすぐ右隣のセル、そのセルの 3 マス右隣のセルの値の過半数として形成されます。ランダムに生成されたインスタンスでは、過半数を正しく決定する精度は約 78% です。

ダス、ミッチェル、クラッチフィールドは遺伝的アルゴリズムを使用してより良いルールを開発できることを示しました。^[2]

1995年にLandとBelew ^[3]は、セル数が十分に大きい場合（約4r / ρより大きい場合）、半径rと密度ρを持つ2状態ルールでは、すべての初期構成で投票問題を正しく解決できないことを示しました。

彼らの議論は、システムが決定論的であるため、0 または 1 で完全に囲まれたすべてのセルは 0 になる必要があることを示しています。同様に、完全なルールでは、1の比率が未満の場合に 1 の比率が を超えることはありません (またはその逆)。次に、仮定された完全なルールでは、比率を押し上げた孤立したルールが打ち消されるか、1 の比率が 未満の場合は、孤立したルールによって 0 のブロックに誤った 1 が導入され、1 の比率が より大きくなることを示しています。 ${\displaystyle \rho}$${\displaystyle \rho}$${\displaystyle \rho}$${\displaystyle \rho}$

2013年、Busic、Fatès、Marcovici、Mairesseは、決定論的細胞と確率論的細胞の両方とあらゆる次元に当てはまる、完全な密度分類器を持つことが不可能であることを示すより単純な証明を与えた。^[4]

Capcarrere、Sipper、Tomassini が指摘したように、^{[5] [6]}オートマトンが多数派を認識したとされる定義を緩和すれば、多数派問題は完全に解決できる可能性がある。特に、ルール 184オートマトンの場合、循環境界条件を持つ有限宇宙で実行すると、各セルが 2 ステップ連続して多数派状態にとどまる回数は無限に多く、2 ステップ連続して少数派状態にとどまる回数は有限にすぎない。

あるいは、ルール 184 を配列のサイズに比例するステップ数だけ実行し、各セルを自身とその近傍のセルの多数決に設定する多数決ルール (ルール 232) に切り替えるハイブリッド オートマトンでは、最終状態がすべて 0 かすべて 1 の標準的な認識基準で多数決問題を解決します。ただし、このマシン自体はセル オートマトンではありません。^[7]さらに、Fukś の複合ルールはノイズに非常に敏感で、ノイズの多い Gacs-Kurdyumov-Levin オートマトン (不完全な分類器) を、どんなレベルのノイズ (環境や動的ミスなど) でも上回ることはできないことが示されています。^[8]

タスクが、望ましい出力の定義に応じて不可能なものからかなり単純なものへと変化したことから、問題は次の定義に一般化されました。完全な密度分類オートマトンとは、開始構成の密度がしきい値を下回っているときに到達可能な構成の集合が、開始構成の密度がしきい値を上回るときに到達可能な構成の集合と完全に互いに素であるオートマトンとして定義されます。この定義を使用して、Capcarrere と Sipper ^{[9] は、} セルラーオートマトンが完全な密度分類器となるための 2 つの必要条件を証明することができました。(1) 初期構成の密度は時間の経過に伴って保存される必要がある、(2)ルールテーブルは0.5 の密度を示さなければならない (分類のしきい値が 0.5 と異なる場合でも)。最後の特性は、ルールの形式に関する条件をグローバルな動作に関連付けるという意味で非常にユニークです。