arXiv cs.AI· Chien-Ping Lu·· 9 天前AI 评分24
自我改进智能体的相对可计算性理论
A Relative-Computability Theory of Self-Improving Agents
AI 导读
该研究提出一种 oracle 相对模型，用可变求解器、评估器和改进器刻画自我改进智能体，将自主改进、能力提升与计算范围扩大区分开来。在布尔规则获取的可构造模型中，学习到的求解器可在所有输入上摆脱教师，但仍处于同一可计算层；而从任意有效特征程序统一构造所需特征张成规范，已与相对停机问题同等困难。
正文 · 原文
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.
| Comments: | 20 pages, 3 figures, 1 table. Added diagrams of mutable-state simulation and certified teacher removal; clarified the introduction and discussion of relative computability as a foundation for evolving AI systems. Main results and proofs unchanged. Includes ancillary finite-check code |
| Subjects: | Computational Complexity (cs.CC); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2605.27381 [cs.CC] |
| (or arXiv:2605.27381v3 [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)
来源：arXiv cs.AI · arxiv.org