一关系半群的字问题 · 公开问题 12

问题

一关系半群（独异点）⟨X ∣ u = v ⟩ 的字问题：给定两个词，判定它们在 M 中是否相等。这是组合半群论的头号悬案：已知部分情形可判定——⟨X ∣ u = 1⟩ 带 u 左循环（Adian）、一关系群（Adian 的 Magnus 后续机器）——一般情形自 Markov–Post 时代以来无实质推进。问题的精确形式 «半群的不可判定性从几个关系开始»：两个关系即可编码图灵机（Markov–Post），一个关系是否永远安全，是 «有限呈现理论的精细边缘» 的试金石。

主要概念

Adian 的组合机器

Adian 对一关系呈现发展了 «重写图» 技术：以关系词 u 的 «自重叠结构» 为参数，把可能的推导组织成 «图上行走»；当 u（或 v）是左循环（自重叠受控）时图有限、字问题可判定。机器同时产出：一关系独异点的 «可消去性判定»、共轭结构等。一般词形（两词的重叠模式任意复杂）使图无限——机器失速的精确位置已知，但没有别的机器接棒。

周期关系与可判定谱

最简单的一关系族 ⟨a ∣ a^p = a^q⟩（单生成元）的独异点是完全可分析的（命题 1）；多生成元的 «周期化» 关系（如 uⁿ = vⁿ）与自由 Burnside 半群（19 号）接壤。不可判定性一侧：Markov–Post 的 «两个关系即图灵完备» 是经典（半群的词问题不可判定性最早的构造），«一个关系是否安全» 是精确的开放谱。

主要命题与证明

命题 1（单生成元周期独异点的字问题；完整证明）　M = ⟨a ∣ a^p = a^q⟩（0 < p < q）中，两词 a^m, aⁿ 相等 ⟺ m = n，或 m,n ≥ p 且 m ≡ n（mod d），其中 d = q−p。字问题以线性时间可判定。

证明　关系 ⟺ a^p = a^p+d，归纳得 a^p+t = a^p+t+d 对一切 t ≥ 0（a^p+t+2d = a^d·a^p+t+d = a^d·a^p+t = a^p+t+2d…，用交换性——单生成元独异点交换）。等价类：{1,…,a^p−1} 各自单点（< p 的幂两两不等——任何推导保持 «幂指数低于 p 时不可再应用关系»，关系的两边指数 ≥ p，故小指数词是 «冻结» 的）；≥ p 的幂按 mod d 合并且以 a^{p+(r mod d 的代表)}…为 representative：M ≅ {1, a,…,a^p−1} ∪ {p 个循环类}（p+1 到 p+d−1 加幂等元结构——单生独异点的标准形状：指数 ≥ p 的类共 min(d,∞) 个，每个类是 «循环群式» 的旋转）。判据推导：a^m = aⁿ（m ≤ n）⟺ n = m 或（m ≥ p 且 m ≡ n（mod d））——«⟸» 用上述关系链；«⟹» 由标准形（每类取代表 a^p−1+r…）的良定义性。□

命题 2（Markov–Post 不可判定性基线；陈述与机制）　存在两个关系的半群其字问题不可判定（Markov–Post，1947）：把图灵机的 «格局» 编码为词、 «转移» 与 «格局延续» 编码为两条关系，机器不停机 ⟺ 词问题非平凡的实例存在。因此 «关系数 → 不可判定» 的阈值在 2 与 1 之间——12 号问题正是这个唯一空档。

机制说明　Markov–Post 编码的精细形态：两条关系分别模拟 «读–写–移位» 与 «停机吸收»；Boone–Novikov 的群版本需要更多关系（后减到若干个），半群的 «两关系阈值» 至今无法压到一。一关系侧的一切已知可判定性都依赖 «关系词的自重叠结构»（Adian 机器），而图灵完备编码需要的关系恰有 «不可控重叠»——这说明阈值若存在，其机制应是 «重叠复杂度» 而非单纯关系数；把这一直觉变成定理是问题的核心困难。□

命题 3（Adian 可判定谱；陈述）　⟨X ∣ u = 1⟩（或 u = v）中 u 左循环（自重叠受控）时字问题可判定（Adian 1967）；一关系群 ⟨X ∣ u = 1⟩ 的字问题可判定（Magnus 1932 的 Freiheitssatz 机器，Adian 与后续工作给出结构细化）。一般一关系独异点：无证明亦无反例；与 11 号（嵌入猜想）技术上同源。

现状说明　Magnus 机器（群侧）与 Adian 机器（半群侧）的差别：群中有逆元 «倒带»，推导图可双向；半群推导单向， «不可逆的碰撞» 是机器失速处。近年（2010 年代）的进展（如 «一关系独异点的可消去子结构»、自动性部分结果）都在 «绕开碰撞» 的路线上，尚无正面突破。□

进展与文献

Markov–Post（1947，两关系不可判定）；Magnus（1932，一关系群）；Adian《The Burnside Problem and Identities in Groups》（1979）；Kobayashi、Gray–Steinberg 等的部分可判定结果（2000 年代起）。开放核心：一般一关系独异点的字问题；«重叠复杂度» 阈值的定理化；一关系半群的自动性谱（48 号接口）。