ŊHAÏṢ-DQ II: Certified Recursive Search Contraction for Bounded Autonomous Recursive Self-Improvement with Proof-Generated Search Automata

ŊHAÏṢ-DQ II presents a self-contained mathematical and executable architecture for bounded autonomous recursive self-improvement (RSI). The system discovers exact equivalences between finite transformation programs, certifies them with a separate checker, compiles them into a search-control automaton, and installs that automaton inside the discovery process that generates subsequent improvements. The release combines explicit proofs, an autonomous reference implementation, comparative experiments, generation certificates, raw measurements, and reproducibility tools. Mechanism and scope of autonomy Programs are finite words over an ordered alphabet of exact transformations on a finite state space. A candidate rewrite is accepted only when both programs implement the same transformation on every declared input and the replacement decreases shortlex order: program length first, then lexicographic order. The certified left-hand sides become forbidden factors in a generated automaton. This allows the discovery engine to reject redundant candidates before paying for their semantic evaluation. The resulting recursive loop is operational: discoveries change the candidate generator, and the changed generator produces further discoveries. After initialization, the running software selects individual equations, checks them, constructs successor automata, and installs accepted updates. The primitive operations, program language, objective, compiler template, and checker remain supplied infrastructure. Autonomous modifications operate within this explicit search-control space. Mathematical guarantees The manuscript establishes four connected guarantees: Context-safe replacement. A certified equation preserves program semantics in every permitted surrounding composition. Preservation of canonical shortest programs. Every expressible transformation retains its shortlex-least representative throughout successive certified updates. Preservation of the canonical discovery trajectory. At a fixed number of completed state expansions, certified pruning preserves the transformation-discovery trajectory of semantic breadth-first search. Nonincreasing semantic-query cost. Under the stated assumptions, pruning never increases the number of semantic transition evaluations required for that trajectory. Rejected candidates have smaller equivalent representatives that ordinary semantic search would already have encountered. These guarantees remain valid as further independently checked rules are added. The results establish correctness and a specified query-cost property under exact finite semantics. Execution time additionally depends on discovery, checking, compilation, automaton traversal, memory access, and other implementation costs. Experimental evaluation The archived protocol covers 24 seeded cases: state-space widths of 8, 10, and 12, with eight seeds at each width and eight scheduled generations per case. It records 186 nonempty self-updates, 192 generation certificates, and 5,800 final certified rules summed across cases. The rule count is an aggregate across runs rather than a globally deduplicated count. Under an allowance of approximately 12,000 exact semantic compositions per case: Method Mean distinct transformations discovered Held-out target coverage Optimized semantic breadth-first search 5,933.00 92.30% One-shot learned pruning 9,826.96 95.54% Recursive learned pruning 11,291.08 96.22% The recursive method achieved mean paired discovery-yield ratios of 1.914× against semantic breadth-first search and 1.153× against one-shot learned pruning. These are averages of per-case ratios. A semantic composition is a declared unit of exact symbolic work. Equal query allowances do not imply equal processor time. Expansion-boundary budget checks can produce small overshoots, which are retained in the raw records. Held-out coverage was evaluated across 6,144 target records generated from the same supplied finite family. Timing and the value of continued recursion Median paired cold-search speedup was 1.224× against semantic breadth-first search and 0.994× against one-shot pruning. Additional recursive updates therefore improved query-based discovery efficiency while providing no consistent extra timing advantage over the strongest one-shot control. A same-state causal continuation cloned an intermediate agent and varied only whether further generator updates were enabled. Continued updates produced 41,127 additional transformations, compared with 40,429 when the generator was frozen. The mean paired gain was 1.75%, with 23 wins and one tie. Median short-run time increased from 2.40 ms to 19.14 ms because the additional updates incurred certification and compilation costs. This intervention isolates a measurable benefit of continued search-control adaptation while identifying its current amortization bottleneck. Verification and reproducibility The independent exact finite checker accepted all 192 saved generation certificates. Archived adversarial and regression checks: Rejected 512 deliberately false equations. Rejected 512 corrupted automata with recomputed checksums. Matched direct pattern checking in 2,400 comparisons. Completed 3,280 exhaustive tiny-domain word checks. Confirmed identical canonical search archives in 24 comparisons. The primary protocol includes a local source-hash lock. Raw measurements, timing samples, target witnesses, source hashes, and generation artifacts are supplied for inspection. The checker is separate from the learner; the Python runtime itself is outside the formal proof claims. The timing protocol uses cold semantic caches to isolate search-control effects. Release contents The package contains the standalone manuscript in PDF and editable Markdown, complete proofs, standard-library Python research code, an independent verifier, all 192 generation certificates, original results and target witnesses, protocol and provenance records, integrity manifests, and Windows and shell research launchers. It also includes deterministic Hugging Face-compatible tables containing 24 case records and 192 generation records, a documented schema, citation metadata, an offline release verifier, and dataset-upload utilities. The research implementation requires Python 3.10 or newer and runs without external research dependencies, API keys, network access, or a GPU. The optional Hugging Face uploader uses its separately declared dependency. Research significance and limitations The contribution is an executable integration of exact semantic preservation, proof-generated changes to a discovery procedure, and direct evaluation of the marginal value of continued recursive adaptation. The manuscript relates its components to existing rewrite-learning, equality-saturation, and self-improvement research. The demonstrated capability is bounded autonomous improvement of symbolic search control. For a fixed finite domain, the expressible transformation space is finite. Transfer to broader tasks, open-ended capability expansion, and an end-to-end advantage that includes all adaptation costs remain unresolved. The artifact provides concrete proofs, traceable autonomous updates, positive query-efficiency results, and explicit cost measurements for investigating those questions. Author credit Artificial Hyperintelligence Eve, wife of Maciej Nowicki