Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems
Jose Pascual Gumbau Mezquita
Why It Matters
What makes this one worth your time
Understanding the theoretical limits of AGI alignment is crucial for developing realistic safety measures and guiding future research in AI safety.
The paper identifies fundamental mathematical barriers to verifying AGI alignment.
Summary
The paper explores the mathematical limitations of aligning Artificial General Intelligence (AGI), presenting two impossibility theorems that highlight the structural unverifiability of AGI alignment. It argues that current engineering approaches cannot overcome these logical barriers, leading to a trilemma involving soundness, completeness, and tractability.
Key contributions
- Unverifiability Theorem of Alignment
- Theorem of Finite Structural Unverifiability of AGI Alignment
- Mapping theoretical bounds to practical AI engineering challenges
Notable insights
- The paper introduces the concept of Trakhtenbrot's Wall as a boundary for AGI alignment verification.
- It presents a trilemma involving soundness, completeness, and tractability, suggesting these cannot all be achieved simultaneously in AGI alignment.
Possible limitations
- Not stated in the abstract
Abstract
arXiv:2606.28639v3 Announce Type: replace-cross Abstract: We establish mathematical limits of algorithmic safety verification for Turing-complete self-modifying systems, the class in which recursive self-improvement takes place, both for a fixed system and across its own modification. Statically, no verifier is sound, complete and tractable: over unbounded domains by Rice's and G\"odel's theorems, over all finite configurations by Trakhtenbrot's theorem, and over succinctly described finite environments because verifying a policy against an adversary is coNP-complete and synthesising one is PSPACE-complete. Dynamically, we model one step of self-modification as a computable transformation of code and ask whether a safety property survives it. If the transformation depends only on behaviour, this is Rice's theorem one level up; if it reads the code, as self-modification does, the question is no longer semantic, yet the same s-m-n reduction works inside a class of behaviourally identical programs and inherits the halting degree. One step is never harder than the property; persistence along the whole trajectory can be $\Pi^0_2$-complete. Certification by a total algorithm is possible only for transformations of restricted expressivity, not merely for systems that stop changing. No tower of supervisors helps, and every total supervisor errs on an undecidable set of systems. For effectively pointwise properties, every faithful bounded scheme that certifies on finite behavioural evidence admits evolution traces certified at every stage while the property is violated. What survives is exact: a monitor that raises an alarm on violation semidecides it, and comparison against a frozen reference keeps the full theory.