A Relative-Computability Theory of Self-Improving Agents
Chien-Ping Lu
cs.CC
Apr 9, 2026 · v4
cs.AI
TL;DR
A Lean 4 project pinned to Mathlib machine-checks the acquisition protocol's termination, query bound, and all-input agreement, along with relative-computability model results.
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.
Problem
Self-improving agents can acquire a solver from a teacher, but it is unclear when the teacher can be removed with a guarantee that the solver is correct on every future input. The paper separates learning a solver from certifying that it no longer depends on the teacher.
Approach
An oracle-relative computability model of evolving agents is extended with explicit acquisition and completion contracts. For a known finite-dimensional Boolean feature language over F_2, a guarded query protocol lets the query proposer be revised while it learns the target, and a finite-family extension uses a supplied separating specification. Halting reductions show which specifications cannot be extracted uniformly. A Lean 4 project with pinned Mathlib checks the finite-family procedure, the finite-list reduction behind the lower bound, and relative-recursive closure results.
Results
The protocol terminates using the optimal rank number of teacher calls, and the resulting solver stays in the baseline computability layer. No baseline-effective procedure can uniformly produce the span or separating specification from arbitrary total programs, even in one feature dimension or with two candidate descriptions. Controlled experiments separate exact teacher removal from low-risk stopping.