自我改进智能体的相对可计算性理论
A Relative-Computability Theory of Self-Improving Agents
AI 导读
arXiv 论文提出自我改进智能体的相对可计算性理论，通过获取与完成契约区分“学会求解器”和“证明其可脱离教师独立工作”。受保护协议保证以最优教师调用次数完成学习，所得求解器可在无教师情况下回答所有输入并停留在基线可计算层；但完成规范无法从任意全程序中统一提取，即使单个特征维度与两个候选描述也不行。工作包含受控实验与部分 Lean 形式化。
正文 · 原文
Abstract:Self-improving agents can acquire a procedure without knowing when its supporting teacher can safely be removed. We extend an oracle-relative model of evolving agents with explicit acquisition and completion contracts, separating learning a solver from certifying its independence. For a known finite-dimensional Boolean feature language, a query history determines exactly the answers in its feature span. A guarded protocol permits query-proposer revision while guaranteeing completion with the optimal number of teacher calls, and a supplied separating specification gives a finite-family extension. The resulting solver answers every input without its teacher and remains in the baseline computability layer. The central obstruction concerns supplying the completion specification: no baseline-effective procedure can extract a valid span or separating specification uniformly from arbitrary total programs, already in one feature dimension or with two candidate descriptions. Classical relative computation and limiting-revision results locate these claims without imposing a ceiling on practical improvement. Controlled experiments distinguish exact teacher removal from low-risk stopping and measure adaptation benefits and costs against a stronger greedy baseline. The framework makes the information required to acquire, certify, and deploy a capability explicit.
| Comments: | 31 pages, 5 figures, 3 tables. Revised around certified acquisition and completion-specification obstructions; expanded controlled experiments and assistance analysis; detailed proofs in appendices. Includes reproducible research artifacts and partial Lean formalization with explicit open obligations |
| Subjects: | Computational Complexity (cs.CC); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2605.27381 [cs.CC] |
| (or arXiv:2605.27381v4 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.27381 arXiv-issued DOI via DataCite |
Submission history
From: Chien-Ping Lu [view email]
[v1]
Thu, 9 Apr 2026 22:56:56 UTC (17 KB)
[v2]
Wed, 7 Oct 2026 06:14:45 UTC (25 KB)
[v3]
Thu, 8 Oct 2026 12:24:07 UTC (26 KB)
[v4]
Fri, 30 Oct 2026 14:20:26 UTC (315 KB)
来源：arXiv cs.AI · arxiv.org