arXiv cs.CL· Jose Pascual Gumbau Mezquita·· 3 天前AI 评分24
固定与递归自我改进系统的安全算法不可验证性
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