⚡ electrical engineering

Decentralized Decision-Making for Finite-State Systems over Finite Alphabets is Undecidable

この論文は、非単調な融合規則（XORなど）を使用する場合、有限の通信アルファベットの下では、有限状態システムに対する分散決定問題が決定不能になることを示しており、これは単調な規則に基づいた古典的な結果とは対照的である。

原著者： Xiang Yin

公開日 2026-06-17

📖 1 分で読めます☕ さくっと読める

原著者： Xiang Yin

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

全体像：「はい」か「いいえ」のゲーム、そこに隠された仕掛け

巨大で複雑な機械（工場のロボットや交通システムなど）を、2人の別々の警備員が監視している場面を想像してください。これらの警備員は互いに会話することはできず、機械の一部しか見ることができません。

警備員1 は、特定のライトのセットを見ています。
警備員2 は、別のライトのセットを見ています。
ボスは、コントロールルームに座っています。彼は機械を直接見ることはできません。彼は各警備員から送られてくる、たった一つの「はい」または「いいえ」という信号だけを受け取ります。
目的： ボスは、機械が現在「グッド（良好）」な状態（ルールに従っている）か、「バッド（不良）」な状態（ルールを破っている）かを知る必要があります。

ボスは、警備員たちの答えを組み合わせるための特別なルールを持っています。彼は XOR（排他的論理和） と呼ばれる論理ゲートを使用します。

もし警備員1が「はい」と言い、警備員2が「いいえ」と言った場合、ボスは 「グッド」 と判断します。
もし警備員1が「いいえ」と言い、警備員2が「はい」と言った場合、ボスは 「グッド」 と判断します。
もし二人が共に「はい」と言った場合、あるいは共に「いいえ」と言った場合、ボスは 「バッド」 と判断します。

問い： 警備員たちがそれぞれのライトを見て、正しい「はい／いいえ」の信号を送るようにプログラムすれば、ボスは機械が「グッド」な状態にあるときを常に正確に把握できるでしょうか？

本論文の主要な発見：「不可能なパズル」

数十年にわたり、研究者たちは、もし警備員に単純なルール（例：「どちらかが赤信号を見たら『止まれ』と言え」など）を与えれば、その問題を解決するためのプログラムを必ず作成できると考えてきました。

しかし、この論文はそれが真実ではないことを証明しています。

著者である Xiang Yin 氏は、もし XORルール（ボスが「グッド」と判断するために、警備員同士が「食い違う」必要があるルール）を使用する場合、解決策が存在するかどうかを知ることは 数学的に不可能 になることを示しました。どんなに強力なコンピュータであっても、あらゆる種類の機械に対してこのパズルを解くことは決してできません。

比喩：「単語の入れ替え」ゲーム

著者はどのようにしてこれを証明したのでしょうか？彼は、この機械の問題を、有名な解けない単語ゲームである 「トゥエの単語問題（Thue Word Problem）」 に置き換えました。

単語の中の文字を入れ替えるための、魔法のようなルールがいくつかあると想像してください。

ルール1：「AB」を「BA」に入れ替えることができる。
ルール2：「C」を「BB」に入れ替えることができる。

あなたは 「ABC」 という単語からスタートします。

「AB」を入れ替えて 「BAC」 にすることができます。
それをさらに「C」を入れ替えて 「BABB」 にすることができます。

問い： これらのルールを使って、単語 「ABC」 を単語 「BABB」 に変えることはできるでしょうか？

数学の世界において、これは既知の 解けない問題 です。あらゆる単語やあらゆるルールのセットに対して、「はい」か「いいえ」に答えるための一般的な手法は存在しません。

このつながり：
著者は、この単語ゲームと全く同じように機能する「機械（有限状態システム）」を構築しました。

アイデンティティ・ブランチ（同一性分岐）： この機械は、両方の警備員に同じように見える単語を生成します。これにより、警備員は一致した回答（同じ信号を送る）を強制され、ボスは「バッド」と判断します（XORは食い違いを必要とするため）。これにより、基準となる「真実」が確立されます。
リライト・ブランチ（書き換え分岐）： この機械は、警備員が同じ単語の異なるバージョンを見ているような状況（例：「ABC」対「BABB」）を生成します。機械のルールにより、警備員は再び一致することを強制されます。つまり、入れ替えが行われた後でも、単語の「真実」は変わらない必要があります。
マークト・ブランチ（印付き分岐）： この機械は、特定の「グッド」なシナリオ（ターゲットとなる単語）を生成します。ここでは、ボスは警備員が「食い違う」ことを必要としています。

罠：
もし単語ゲームにおける2つの単語が実際に等価である場合（一方をもう一方に変えることができる場合）、機械のルールは警備員に一致することを強制します。しかし、「グッド」のシナリオでは、彼らが食い違うことが求められます。ここに矛盾が生じます。
もしそれらが等価でない場合は、警備員が食い違うようにプログラムすることが可能です。

「単語の入れ替え」ゲームが解けない以上、「機械の警備員」のゲームもまた解けないのです。

なぜこのようなことが起こるのか？（「単調」対「カオス」のルール）

本論文は、これまでの成功した手法が 単調（Monotone） なルール（順序を保存するもの）に基づいていたことを説明しています。

AND/OR ルール： 情報が増えても、答えが激しく変動することはありません。それは委員会の投票のようなものです。より多くの人が「賛成」に投票すれば、結果も「賛成」になる可能性が高まります。このような構造があるからこそ、コンピュータは解決策を見つけることができます。
XOR ルール： これは 非単調（Non-Monotone） です。それは「ジャンケン」のロジックのようなものです。両方の警備員が考えを変えると、結果は完全に逆転してしまいます。この「安定した秩序」の欠如が、通常これらの問題を解くために使われる数学的ツールを破壊してしまうのです。

他の問題については？

この論文は、この「不可能であること」が、単にボスが機械の動作を推測できるかどうかという問題にとどまらず、他の現実世界の制御問題にも波及することを示しています。

分散制御： 機械の故障を防ぐように警備員をプログラムできるか？（いいえ、XORを使用する場合）。
故障診断： 部品が故障したことを警備員が知らせることができるか？（いいえ）。
故障予兆： 故障が起こる「前」に、警備員がそれを予測できるか？（いいえ）。

まとめ

設定： 2人の警備員が機械を監視し、ボスに対してバイナリ（はい／いいえ）の信号を送る。ボスは XOR ルール（食い違いを「グッド」とする）を使用する。
結果： これは 決定不能（undecidable） である。警備員への指示セットが存在するかどうかを判定できるアルゴリズムは存在しない。
理由： XORルールは、通常コンピュータがこれらのパズルを解くことを可能にする数学的な「構造（単調性）」を破壊する。この問題は、解けない「トゥエの単語問題」と数学的に等価である。
教訓： 非常に単純で制限された通信（2人からのわずか1ビットの情報）であっても、その答えを組み合わせる方法（XOR）の選択によって、システム全体をプログラムしたり分析したりすることが不可能になることがある。

技術要約：有限アルファベット上の有限状態システムにおける分散型意思決定の決定不能性

1. 問題の定式化

本論文は、厳格な通信制約下における有限状態遷移システム（離散イベントシステム：DES）の分散型意思決定に関する根本的な決定可能性を調査している。問題は、以下の要素を含む一般的な分散観測アーキテクチャの枠組みで構成されている：

プラント（Plant）: 決定性有限オートマトン $G = (Q, \Sigma, f, q_0)$ 。
ローカルエージェント: 2つのエージェントが、自然な射影 $P_1$ および $P_2$ を介して、互いに素なイベント集合 $\Sigma_{o,1}$ および $\Sigma_{o,2}$ を通じてプラントを観測する。
通信: 各エージェントは、自身の観測履歴のみに基づいて、有限アルファベット $\Delta$ からローカル意思決定記号を生成する。
融合センター（Fusion Center）: メモリレスな融合センターが、2つのローカル意思決定のペアに対して固定された規則 $F: \Delta \times \Delta \to \{0, 1\}$ を適用し、グローバルなバイナリ決定を生成する。

**「有限アルファベットを持つ分散観測問題」**と呼ばれる核心的な問いは、与えられた正則仕様言語 $K \subseteq L(G)$ を正確に再構成できるようなローカル意思決定写像 $S_i: P_i(L(G)) \to \Delta$ が存在するかどうかを判定することである。具体的には、すべての $s \in L(G)$ に対して、条件 $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$ が成立しなければならない。

2. 手法

著者らは、形式言語理論における古典的な決定不能問題である、有限個の双方向書き換え規則の下での2つの単語の等価性を扱うトゥエ（Thue）の単語問題からの帰着を通じて、この問題の決定不能性を確立している。

構成戦略:
トゥエの単語問題のインスタンス $(\Gamma, R, \alpha, \beta)$ が与えられたとき、著者らは以下の特性を持つ特定の分散観測インスタンス $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ を構築する：

制限されたアーキテクチャ: 通信アルファベットはバイナリであり（ $\Delta = \{0, 1\}$ ）、融合規則は**排他的論理和（XOR）**演算子（ $a \oplus b = 1 \iff a \neq b$ ）に固定されている。
プラント構造: オートマトン $G$ $G$ は、以下の3つの異なる分岐を持つように構築される：
1. 恒等分岐（Identity Branch）: 任意の単語 $w \in \Gamma^*$ をペアのシーケンスとしてエンコードする文字列を生成する。これは、2つのエージェントに対し、同一の基礎となる単語 $w$ に対して同一の意思決定値を割り当てることを強制する（出力がマークなしの文字列に対して0である必要があるため、 $x \oplus y = 0 \implies x=y$ となる）。これにより、グローバルな評価関数 $C(w)$ を定義することが可能になる。
2. 書き換え分岐（Rewrite Branches）: 各書き換え規則 $(\ell_j, r_j) \in R$ に対して、プラントは、エージェント1が $\ell_j$ を含むコンテキストを観測し、エージェント2が同じコンテキスト内の $r_j$ を観測する文字列を生成する。これらの文字列はマークなしであるため、XOR融合規則は $C(\dots \ell_j \dots) = C(\dots r_j \dots)$ を強制する。これにより、評価 $C$ がトゥエの書き換えステップに対して不変であることが強制される。
3. マーク付き分岐（Marked Branch）: エージェント1とエージェント2がそれぞれ観測した特定の単語 $\alpha$ と $\beta$ をエンコードする、一意のマーク付き文字列を生成する。融合出力が1（ $K$ のメンバーシップを示す）となるためには、エージェントは異なる値を割り当てなければならない： $C(\alpha) \neq C(\beta)$ 。

論理的帰着:
有効なローカル意思決定写像の存在は、トゥエ等価類上で一定であり（書き換え分岐による）、かつ $\alpha$ と $\beta$ を区別する（マーク付き分岐による）評価 $C$ の存在を意味する。このような評価が存在するのは、 $\alpha \not\equiv_R \beta$ である場合のみである。トゥエの単語問題は決定不能であるため、そのような写像の存在を判定することもまた決定不能である。

3. 主な貢献と結果

XOR下での決定不能性: 本論文は、意思決定アルファベットがバイナリであり、融合規則がXORに固定されている場合であっても、分散観測問題が決定不能であることを証明している。これは、極めて制限された情報アーキテクチャ（2つのエージェント、有限アルファベット、メモリレス融合）においても成立する。
単調性の役割: 既存のアーキテクチャ（例：連言ANDまたは論理和ORの規則）の決定可能性は、根本的にそれらの融合規則の単調かつ順序保存的な性質に依存していることを、本結果は浮き彫りにしている。XOR規則は本質的に非単調であり、古典的な設定において構成的合成と決定可能性を可能にする構造的特性を打破するものである。
制御および診断への拡張: 著者らは、分散観測問題が以下の問題に帰着できることを示している：
- 分散型監視制御（Decentralized Supervisory Control）: 仕様を強制するためのローカル監視器の存在判定。
- 分散型故障診断（Decentralized Fault Diagnosis）: 故障を遅延なく、かつ誤報なしに検出するためのローカル診断器の存在判定。
- 分散型故障予測（Decentralized Fault Prognosis）: 故障が発生する前に故障を予測するためのローカル予測器の存在判定。
  したがって、これらすべての問題は、バイナリ意思決定アルファベットとXOR融合規則の下で決定不能であることが示される。

4. 意義と主張

本論文は、分散型意思決定アーキテクチャにおける根本的な限界を明らかにしていると主張している。従来の文献は、表現力を高めるために意思決定アルファベットを豊かにしたり、洗練された融合規則を設計したりすることに焦点を当ててきたが、本研究は、融合規則の選択が合成問題自体の決定可能性を根本的に変え得ることを示している。

著者らは、自らの結果が（無限の通信アルファベットを伴うような）先行する決定不能性の結果よりも厳密に強いものであることを強調している。なぜなら、決定不能性は、通信アルファベットが有限（バイナリ）であり、融合規則が固定されている場合でも持続するからである。決定不能性の本質的な原因は、通信アルファベットのサイズではなく、独立した観測が非単調な融合規則と相互作用することによって誘発される分散型情報構造にあると特定されている。

論文は、一般的な問題は決定不能であるが、ローカルエージェントにおけるメモリが制限されている実用的なアプリケーションでは、全探索を通じて合成問題が決定可能になる可能性があることを述べ、限定的な合成技術への将来の研究方向を示唆して、控えめに締めくくられている。