arXiv：cs.CL· Jose Pascual Gumbau Mezquita·· 6 小时前
固定与递归自改进系统的安全性的算法不可验证性
Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems
AI 导读
一项理论研究探讨了自修改系统（能重写自身代码、递归自我改进的智能体）的安全性是否可被提前证明在自我改写后依然成立。论文将一步自我修改建模为代码的可计算变换：若变换仅依赖行为，安全性保持可归结为 Rice 定理；若读取代码，则其难度至少等同于停机问题；沿整条轨迹的持续性还可能高出一个算术层级。
正文
Abstract:Existing impossibility results for AI verification concern a fixed system. Self-modifying systems (agents that rewrite their own code, recursive self-improvement loops) raise a different question: can a safety property that holds now be certified, in advance, to keep holding after the system rewrites itself? We model one step of self-modification as a total computable transformation of code, and preservation as 'safe now and safe after the step'. If the transformation depends only on behaviour, preservation is Rice's theorem one level up; if it reads the code, as self-modification does, preservation is no longer semantic, yet at least as hard as the halting problem, by the same s-m-n reduction carried out inside a class of behaviourally identical programs. One step is never harder than the property; persistence along the whole trajectory can be one arithmetical level higher. No tower of supervisors lowers the problem; every total supervisor errs on a set of systems it cannot locate. Every faithful scheme certifying on finite behavioural evidence admits, for properties not settled by any finite set of inputs, an evolution trace it certifies at every stage while the property is violated. Statically, we record the classical limits (Rice, Goedel, Trakhtenbrot) and add the resource face: over succinctly described finite environments, verifying a policy against an adversary is coNP-complete and synthesising one PSPACE-complete. These limits do not say self-modifying systems are unsafe; they locate where algorithmic guarantees break, at the expressivity a general system needs: Turing-completeness and unrestricted self-modification. What survives is exact: a monitor detects the first violation of a safety property, and no sound procedure certifies all safe systems; certification requires restricting rewrites by design; and a frozen reference keeps the question well posed.
| Comments: | v4: restructured and shortened; static limits condensed into one context section; new remarks on properties that change and on positive/negative disruption; related work extended (Harrison-Ruzzo-Ullman, Cohen, Bonfante-Marion-Reynaud-Plantey, Wang et al., Cai-Shao-Vaynberg); supervision result restated; cites companion arXiv:2609.11326v3 |
| Subjects: | Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Computation and Language (cs.CL) |
| MSC classes: | 68T01, 03D35, 03D25, 68Q17, 68Q60 |
| ACM classes: | I.2.0; F.1.1; F.1.3; F.4.1; D.2.4 |
| Cite as: | arXiv:2606.28639 [cs.LO] |
| (or arXiv:2606.28639v4 [cs.LO] for this version) | |
| https://doi.org/10.48550/arXiv.2606.28639 arXiv-issued DOI via DataCite |
Submission history
From: Jose Pascual Gumbau Mezquita [view email]
[v1]
Fri, 26 Jun 2026 22:51:16 UTC (16 KB)
[v2]
Mon, 6 Jul 2026 12:56:49 UTC (29 KB)
[v3]
Wed, 23 Sep 2026 09:13:44 UTC (40 KB)
[v4]
Wed, 14 Oct 2026 12:00:07 UTC (68 KB)
来源：arXiv：cs.CL · arxiv.org