aiqbench analysis
This paper establishes a formal oracle-relative framework to analyze the distinct properties of autonomous self-improvement in agents, specifically separating practical capability gains from expansions in computational reach. By modeling mutable solvers and evaluators, it provides rigorous bounds on query histories and identifies fundamental obstructions related to the relative halting problem that limit uniform construction of feature specifications. The work offers a theoretical foundation for understanding verified support removal and the assumptions required for recursive self-improvement without relying on external teachers.
A Relative-Computability Theory of Self-Improving Agents
arXiv:2605.27381v2 Announce Type: replace-cross Abstract: Agents increasingly modify the procedures by which they solve tasks and improve themselves. Autonomy over improvement, gains in practical capability, and enlargement of computational reach are distinct properties. We develop an oracle-relative model with mutable solvers, evaluators, and improvers. Uniform simulation keeps every total decision procedure produced by effective self-revision over $A$ within $\mathcal{C}(A)=\{D:D\leq_T A\}$; oracle joins account for additional access, while the relativized limit lemma separates limiting answers from effective completion. A worked model of Boolean rule acquisition makes the distinction constructive. For a known finite-dimensional feature language, we characterize exactly which answers a query history determines, obtain a sharp teacher-query bound, and give a terminating protocol that permits revisions to the query proposer. The learned solver can dispense with the teacher on every input while remaining in the same computability layer. However, uniformly constructing the required feature-span specification from arbitrary effective feature programs is already as hard as the relative halting problem. We also give a conditional criterion for strict ascent and distinguish it from finite behavioral evidence. The framework thus separates acquisition, certification, and computability ascent, identifying both a positive route to verified support removal and the assumptions on which it depends.
Abstract:Agents increasingly modify the procedures by which they solve tasks and improve themselves. Autonomy over improvement, gains in practical capability, and enlargement of computational reach are distinct properties. We develop an oracle-relative model with mutable solvers, evaluators, and improvers. Uniform simulation keeps every total decision procedure produced by effective self-revision over $A$ within $\mathcal{C}(A)=\{D:D\leq_T A\}$; oracle joins account for additional access, while the relativized limit lemma separates limiting answers from effective completion. A worked model of Boolean rule acquisition makes the distinction constructive. For a known finite-dimensional feature language, we characterize exactly which answers a query history determines, obtain a sharp teacher-query bound, and give a terminating protocol that permits revisions to the query proposer. The learned solver can dispense with the teacher on every input while remaining in the same computability layer. However, uniformly constructing the required feature-span specification from arbitrary effective feature programs is already as hard as the relative halting problem. We also give a conditional criterion for strict ascent and distinguish it from finite behavioral evidence. The framework thus separates acquisition, certification, and computability ascent, identifying both a positive route to verified support removal and the assumptions on which it depends.
18 pages, 1 figure, 1 table. Substantially revised and expanded; title changed. Added a mutable-agent model, explicit resource accounting, a certified capability-acquisition model, a uniform span-specification obstruction, and updated discussion of recursive self-improvement. Includes ancillary finite-check code
Computational Complexity (cs.CC); Artificial Intelligence (cs.AI)
arXiv:2605.27381 [cs.CC]
(or arXiv:2605.27381v2 [cs.CC] for this version)
Full text under the publisher's open licence · 246 words
