⚡ 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生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是该论文的通俗化解释，使用了日常类比。

大局观：带有点睛之笔的“是非”游戏

想象一台大型、复杂的机器（比如工厂机器人或交通系统），有两个独立的保安在监视它。这两个保安无法互相交流；他们只能看到机器的一部分。

保安 1 看到一组特定的指示灯。
保安 2 看到另一组不同的指示灯。
老板坐在控制室里。他无法直接看到机器。他只能从每个保安那里接收到一个单一的“是”或“否”信号。
目标： 老板需要知道机器当前是在做“好”的事（遵守规则），还是在做“坏”的事（违反规则）。

老板有一个特殊的规则来组合保安们的答案。他使用了一个叫做 XOR（异或）的逻辑门。

如果保安 1 说“是”，而保安 2 说“否”，老板就说 “好”。
如果保安 1 说“否”，而保安 2 说“是”，老板就说 “好”。
如果他们两个都说“是”，或者两个都说“否”，老板就说 “坏”。

问题是： 我们能否编写程序让保安观察他们的指示灯，并发送正确的“是/否”信号，从而让老板始终能准确知道机器何时在做“好”的事？

论文的核心发现：“不可能完成的谜题”

几十年来，研究人员一直认为，如果你给保安一些简单的规则（例如“如果你们中任何一个人看到了红灯，就说‘停止’”），他们总能找到如何编写程序来解决问题的方法。

这篇论文证明了事实并非如此。

作者 Xiang Yin 表明，如果你使用 XOR 规则（即老板需要保安们通过“意见不一”来判定为“好”），那么判断是否存在解集将变得在数学上是不可能的。无论计算机多么强大，都无法解决这个谜题。

类比：“单词交换”游戏

作者是如何证明这一点的？他将机器问题转化为了一个著名的、无法解决的单词游戏——Thue 单词问题。

想象你有一套神奇的规则，用于交换单词中的字母：

规则 1：你可以将 “AB” 换成 “BA”。
规则 2：你可以将 “C” 换成 “BB”。

你从单词 “ABC” 开始。

你可以把它变成 “BAC”（交换 AB）。
然后你可以把它变成 “BABB”（交换 C）。

问题是： 你能否使用这些规则将单词 “ABC” 变成单词 “BABB”？

在数学世界中，这是一个已知的不可解问题。对于每一个可能的单词和每一套可能的规则，都不存在一种通用的方法来回答“是”或“否”。

其中的联系：
作者构建了一个“机器”（有限状态系统），它的运作方式与这个单词游戏完全一致。

恒等分支（The Identity Branch）： 机器生成的单词对两个保安来说看起来是一样的。这迫使保安们达成一致（发送相同的信号），从而让老板说“坏”（因为 XOR 要求他们不一致）。这建立了一个基准“真相”。
重写分支（The Rewrite Branch）： 机器生成的单词是同一个单词的不同版本（例如 “ABC” 与 “BABB”）。机器的规则迫使保安们再次达成一致。这意味着即使在交换之后，单词的“真相”也必须保持不变。
标记分支（The Marked Branch）： 机器生成了一个特定的“好”的情景（目标单词）。在这里，老板需要保安们产生分歧。

陷阱：
如果单词游戏中的两个单词实际上是等价的（即你可以通过规则把一个变成另一个），那么机器的规则会迫使保安们达成一致。但“好”的情景却要求他们产生分歧。这造成了矛盾。
如果它们不等价，则可以通过编程让保安们产生分歧。

因为“单词交换”游戏是无法解决的，所以“机器保安”游戏也是无法解决的。

为什么会这样？（“单调” vs. “混沌”规则）

论文解释说，之前的成功方法依赖于具有 单调性（Monotone）（保持顺序）的规则。

AND/OR 规则： 如果你增加更多信息，答案不会发生剧烈的翻转。这就像是一个委员会投票：如果更多的人投“赞成”，结果就更有可能倾向于“赞成”。这种结构允许计算机找到解决方案。
XOR 规则： 这是 非单调（Non-Monotone） 的。它就像是“剪刀石头布”式的逻辑。如果两个保安都改变了想法，结果会完全反转。这种缺乏稳定“顺序”的特性破坏了我们通常用来解决此类问题的数学工具。

关于其他问题

论文表明，这种“不可行性”不仅仅关乎老板是否能猜出机器是否在正常工作。它还扩展到了其他现实世界的控制问题：

分布式控制（Decentralized Control）： 我们能否通过编写程序让保安阻止机器损坏？（不能，如果我们使用 XOR）。
故障诊断（Fault Diagnosis）： 保安们能否告诉我们某个部件是否损坏了？（不能）。
故障预测（Fault Prognosis）： 保安们能否在故障发生之前预测到它的发生？（不能）。

总结

设定： 两个保安监视一台机器，并向使用 XOR 规则（需要意见不一才能判定为“好”）的老板发送二进制（是/否）信号。
结果： 这是不可判定的（Undecidable）。不存在一种算法能告诉你，是否存在一套针对保安的指令集来解决该问题。
原因： XOR 规则破坏了通常能让计算机解决此类谜题的数学“结构”（单调性）。该问题在数学上等同于无法解决的 “Thue 单词问题”。
启示： 即便是在通信非常受限（仅两人各发送 1 位信息）的情况下，通过选择如何组合这些答案（使用 XOR），也会导致整个系统变得无法编程或无法分析。

技术摘要：有限字母下有限状态系统的去中心化决策是不可判定的

1. 问题表述

本文研究了在严格通信约束下，有限状态转换系统（离散事件系统，DES）去中心化决策的基本可判定性问题。该问题在一个通用的去中心化观测架构内进行构建，该架构包含：

受控对象 (Plant)： 一个确定性有限状态自动机 $G = (Q, \Sigma, f, q_0)$ 。
局部智能体 (Local Agents)： 两个智能体通过不相交的事件集 $\Sigma_{o,1}$ 和 $\Sigma_{o,2}$ 观测受控对象，通过自然投影 $P_1$ 和 $P_2$ 进行观测。
通信： 每个智能体仅根据其观测历史生成一个来自有限字母表 $\Delta$ 的局部决策符号。
融合中心 (Fusion Center)： 一个无记忆融合中心对两个局部决策应用固定的规则 $F: \Delta \times \Delta \to \{0, 1\}$ ，以产生全局二进制决策。

核心问题被称为具有有限字母表的去中心化观测问题，即判定是否存在局部决策映射 $S_i: P_i(L(G)) \to \Delta$ ，使得融合中心能够精确重构给定的正则规范语言 $K \subseteq L(G)$ 。具体而言，对于所有 $s \in L(G)$ ，必须满足条件： $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$ 。

2. 研究方法

作者通过将该问题归约至 Thue 单词问题 (Thue word problem) 来证明其不可判定性。Thue 单词问题是形式语言理论中的一个经典不可判定问题，涉及两个单词在有限个双向重写规则下的等价性。

构造策略：
给定一个 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$ 被构造为具有三个不同的分支：
1. 恒等分支 (Identity Branch)： 生成将任意单词 $w \in \Gamma^*$ 编码为配对序列的字符串。该分支强制两个智能体对同一个底层单词 $w$ 分配相同的决策值（因为对于未标记的字符串，输出必须为 0，而 $x \oplus y = 0 \implies x=y$ ）。这允许定义一个全局估值函数 $C(w)$ 。
2. 重写分支 (Rewrite Branches)： 对于每个重写规则 $(\ell_j, r_j) \in R$ ，受控对象生成其中一个智能体观测到包含 $\ell_j$ 的上下文、而另一个智能体观测到包含相同上下文中 $r_j$ 的字符串。由于这些字符串是未标记的，XOR 融合规则强制要求 $C(\dots \ell_j \dots) = C(\dots r_j \dots)$ 。这确保了估值 $C$ 在 Thue 重写步骤下保持不变。
3. 标记分支 (Marked Branch)： 生成一个唯一的标记字符串，用于编码智能体 1 和智能体 2 分别观测到的特定单词 $\alpha$ 和 $\beta$ 。为了使融合输出为 1（表示属于 $K$ ），智能体必须分配不同的值： $C(\alpha) \neq C(\beta)$ 。

逻辑归约：
有效局部决策映射的存在性意味着存在一个在 Thue 等价类上为常数（由于重写分支）但在区分 $\alpha$ 和 $\beta$ 时表现不同（由于标记分支）的估值 $C$ 。当且仅当 $\alpha \not\equiv_R \beta$ 时，此类估值才存在。由于 Thue 单词问题是不可判定的，因此判定此类映射的存在性也是不可判定的。

3. 主要贡献与结果

XOR 下的不可判定性： 本文证明了即使在决策字母表为二进制且融合规则固定为 XOR 的情况下，去中心化观测问题也是不可判定的。这适用于高度受限的信息架构（两个智能体、有限字母表、无记忆融合）。
单调性的作用： 研究结果强调，现有架构（例如合取 AND 或析取 OR 规则）的可判定性从根本上依赖于这些融合规则的单调性和保序性。XOR 规则本质上是非单调的，破坏了那些允许在经典设置中进行构造性综合和实现可判定性的结构特性。
向控制与诊断的扩展： 作者展示了去中心化观测问题可以归约为：
- 去中心化监督控制 (Decentralized Supervisory Control)： 判定是否存在局部监督器以强制执行规范。
- 去中心化故障诊断 (Decentralized Fault Diagnosis)： 判定是否存在局部诊断器以在有限延迟且无误报的情况下检测故障。
- 去中心化故障预后 (Decentralized Fault Prognosis)： 判定是否存在局部预后器以在故障发生前进行预测。
  因此，所有这些问题在二进制决策字母表和 XOR 融合规则下都被证明是不可判定的。

4. 意义与主张

本文声称揭示了去中心化决策架构中的一个基本局限性。以往的文献侧重于通过丰富决策字母表或设计复杂的融合规则来增强表达能力，而这项工作表明，融合规则的选择可以从根本上改变合成问题的可判定性本身。

作者强调，其结果比以往的不可判定性结果（例如涉及无限通信字母表的结论）更为严格，因为即使在通信字母表有限（二进制）且融合规则固定的情况下，不可判定性依然存在。不可判定的内在来源被确定为由独立观测与非单调融合规则相互作用所引起的去中心化信息结构，而非通信字母表的大小。

论文最后做出了谦逊的总结，指出虽然一般问题是不可判定的，但对于局部智能体具有有限内存的实际应用，可以通过穷举枚举使合成问题变得可判定，这为未来研究受限合成技术提供了方向。