nx_search_governor.nx

nx_search_governor.nx -- the PRINCIPLE the team learned, made reusable (so the team UNDERSTANDS it, not just one multiply function). Every "find the shortest program for X" the team does -- multiply-by-constant, boolean circuits, future spaces -- is the SAME thing: computing a length- and time-BOUNDED KOLMOGOROV COMPLEXITY over some op set, and deciding whether the shortest program found is worth using over a baseline. The unbounded "shortest program" is uncomputable (Berry/halting); we escape that ONLY with loop-free, total, length-capped ops. The principled way to keep ANY such search reasonable is LEVIN's universal search: order shortest-first and bound by length AND cost (Kt = |program| + log time). This module is that judgment, op-set- agnostic, so the crew applies the same reasoning to every search space. Three reusable levers (the team's understanding, as code): sg_cost_cap -- the LEVIN cost bound: the longest program worth searching for is the one that still beats the baseline. cap = floor(baseline_cost / op_cost). Never search deeper -- a longer program can't win, so it's wasted work (this is exactly why deepening past the cap hung on primes for no benefit). sg_reachable -- an admissible BRANCH-AND-BOUND prune (the THURBER bound, generalized): from a partial state of magnitude `cur`, with `rem` ops left each growing the magnitude by at most factor 2^growth_bits, the target is reachable only if cur << (growth_bits*rem) >= target. Complete: never prunes a real solution. sg_decide -- the COST SELECTION: use the found program iff one was found within the cap AND its cost (len*op_cost) <= baseline_cost; else use the baseline. This is the single judgment shared by multiply (chain vs imul) and boolean (circuit vs the compiler's sum-of-products) and anything else. Refs: Kolmogorov complexity (uncomputable); Levin universal search / Kt; Thurber 1999 (addition- chain branch-and-bound). license_tier: ORIGINAL