技术摘要：观察者、对称性与语言类的层级结构

问题陈述

经典的计算复杂度与形式语言理论传统上根据计算机器的计算能力（如有限自动机、下推自动机、图灵机）对问题进行分类，并假设输入是一个完全可访问且有序的符号序列。本文反转了这一视角，提出计算系统的局限性可能并非源于机器的处理能力，而是源于观察者的结构。

所解决的核心问题是：当一个计算系统无法获取完整的输入字符串，而只能获取其特定的投影或变换时，它能够识别哪些语言？ 本文研究了观察者函数 $O: \Sigma^* \to S$（将输入字符串映射到观察空间 $S$）的“盲目性”或“结构性局限”如何决定语言类的类别，且该类别独立于机器的计算模型。

方法论

本文引入了一个以“观察者”为核心概念的形式化框架：

1. 观察者定义： 观察者是一个将输入字符串 $x$ 转换为观察结果 $O(x)$ 的函数。计算系统 $(M, O)$ 接收 $O(x)$ 作为其输入，而非 $x$。
2. O-饱和性（O-Saturation）： 若一个语言 $L$ 的成员资格仅取决于观察结果 $O(x)$，则称该语言是 O-饱和的。形式化地，若 $x \sim_O y \implies (x \in L \iff y \in L)$。如果一个语言不是 O-饱和的，那么无论配备何种观察者 $O$ 的机器计算能力如何，都无法判定该语言。
3. 观察序（Observational Order）： 定义了一个关于观察者的偏序关系 $\preceq$：若 $O_1$ 可由 $O_2$ 导出（即 $O_1 = f \circ O_2$），则 $O_1 \preceq O_2$。这诱导出了一个语言类层级 $\mathcal{L}(O)$，其中 $O_1 \preceq O_2 \implies \mathcal{L}(O_1) \subseteq \mathcal{L}(O_2)$。
4. 典型观察者： 本文定义了特定的观察者以构建层级：
   • $O_\perp$：平凡观察者（将所有字符串映射为常数）。
   • $O_{len}$：长度观察者（映射为 $|x|$）。
   • $O_{par}$：奇偶观察者（映射为模 2 的计数）。
   • $O_{prof}$：轮廓观察者（映射为符号计数的向量，忽略顺序）。
   • $O_k$：子序列观察者（映射为长度 $\le k$ 的子序列集合）。
   • $O_\top$：完全观察者（恒等映射，$O(x) = x$）。

核心贡献与结果

1. 序盲自动机与置换封闭语言

本文刻画了序盲自动机（Order-blind automaton），这种机器处理的是字符串的轮廓（符号计数的多元集），而非序列本身。

• 定理 2.5： 一个语言可以被序盲自动机识别，当且仅当它是置换封闭的（在符号重排序下保持不变）。
• 该结果表明，状态的有限性并不是主要的约束；相反，观察者决定了语言类。即使是一个配备了平凡观察者的图灵机，也只能识别 $\emptyset$ 和 $\Sigma^*$。

2. 观察层级

本文基于典型观察者的观察能力构建了一个语言类的偏序结构。该层级呈现出特定的结构：

• 菱形轮廓子格（Diamond-Shaped Profile Sub-lattice）：
  • $O_\perp \prec O_{len} \prec O_{prof} \prec O_\top$ （长度分支）
  • $O_\perp \prec O_{par} \prec O_{prof} \prec O_\top$ （奇偶分支）
  • $O_{len}$ 与 $O_{par}$ 是不可比的。
• 无限子序列分支：
  • $O_\perp \prec O_1 \prec O_2 \prec \dots \prec O_\top$。
  • 该分支对应于 Simon 关于分段可测试语言（piecewise testable languages）的层级。
• 正交性： 轮廓子格（计数信息）与子序列分支（部分排序信息）是**正交（不可比）**的。$O_{prof}$ 与任何 $O_k$ 均不可比。

3. 与 Chomsky 层级的正交性

本文证明了观察层级与 Chomsky 层级（正则、上下文无关等）是严格正交（不可比）的。

• 存在属于正则语言但不满足 O-饱和性的语言（例如，$0^*1^*$ 不是 $O_{prof}$-饱和的）。
• 存在属于 O-饱和但不属于正则语言的语言（例如，$\{x \mid |x|_0 = |x|_1\}$ 是 $O_{prof}$-饱和的，但不是正则的）。
• 这确立了“结构性盲目”与“计算复杂度”是两个独立的维度。

4. 与 Simon 层级的联系

本文重新表述了 Simon 关于分段可测试语言的定理。

• 观察者族 $\{O_k\}$ 与 Simon 层级中的等价关系完全对应。
• 一个正则语言是分段可测试的，当且仅当它能被某个有限的 $O_k$ 判定。
• 轮廓类 $\mathcal{L}(O_{prof})$ 与分段可测试语言的并集 $\bigcup_k \mathcal{L}(O_k)$ 是不可比的。

5. 观察者参数化复杂度类 (PO 与 NPO)

该框架通过定义复杂度类 $PO$和$NPO$将其扩展至复杂度理论，其中复杂度是相对于观察大小$|enc(O(x))|$而非输入大小$|x|$ 来衡量的。

• 结构性坍缩（Structural Collapse）： 本文证明了 $PO_{prof} = NPO_{prof}$。
  • 意义： 这并非对 $P$ vs $NP$的解决。相反，这是一种**结构性坍缩**，发生于$O_{prof}$ 丢弃了所有组合结构（顺序）之后。在失去顺序的情况下，非确定性无法比确定性提供任何优势。
  • 严格包含关系： $PO_{prof} \subsetneq P$。类 $PO_{prof}$ 仅包含相对于轮廓大小可在多项式时间内计算的 $O_{prof}$-饱和语言。由于 $0^*1^*$ 属于 $P$ 但不属于 $O_{prof}$-饱和，因此该包含关系是严格的。
• 硬度与盲目性的独立性： 本文证明了计算硬度与观察可判定性是相互独立的。存在属于 $P$ 但不是 $O_{prof}$-饱和的语言，也存在属于正则可枚举（RE）类之外但属于 $O_{prof}$-饱和的语言（例如，由符号计数上的停机问题定义的语言）。

意义与主张

本文声称引入了一个用于分类形式语言和计算问题的全新且独立的轴线。其主要意义在于：

1. 解耦机器能力与观察者结构： 它确立了观察者的“弱点”可以使一个问题对于图灵机也是不可解的，而一个较弱的机器（如 DFA）在拥有更强观察者时却可以解决该问题。
2. 区分硬度与盲目性： 它正式分离了计算硬度（由于算法复杂度导致的困难）与结构性盲目（由于信息丢失导致的无法区分输入）。$PO_{prof} = NPO_{prof}$ 的坍缩被视为这两者截然不同的证据；这种坍缩之所以发生，是因为观察者移除了使问题变得困难的结构，而非非确定性本质上变弱了。
3. 物理阐释： 该框架提供了一个与统计力学相关的形式类比：宏观观察者（仅能看到温度或密度等聚合量）无法区分彼此互为置换关系的微观历史。这为将“热力学不可逆性”视为一种观察属性提供了数学基础。

本文总结道，观察层级提供了一个严谨的框架，用于分析信息本质上受限或被聚合的系统，并建议未来的研究应探索概率观察者、观察者的范畴化组合，以及观察复杂度与信息保存之间的定量关系。