nx_search_governor.nx source

1// nx_search_governor.nx -- the PRINCIPLE the team learned, made reusable (so the team UNDERSTANDS 2// it, not just one multiply function). Every "find the shortest program for X" the team does -- 3// multiply-by-constant, boolean circuits, future spaces -- is the SAME thing: computing a length- 4// and time-BOUNDED KOLMOGOROV COMPLEXITY over some op set, and deciding whether the shortest 5// program found is worth using over a baseline. The unbounded "shortest program" is uncomputable 6// (Berry/halting); we escape that ONLY with loop-free, total, length-capped ops. The principled 7// way to keep ANY such search reasonable is LEVIN's universal search: order shortest-first and 8// bound by length AND cost (Kt = |program| + log time). This module is that judgment, op-set- 9// agnostic, so the crew applies the same reasoning to every search space. 10// 11// Three reusable levers (the team's understanding, as code): 12// sg_cost_cap -- the LEVIN cost bound: the longest program worth searching for is the one 13// that still beats the baseline. cap = floor(baseline_cost / op_cost). Never 14// search deeper -- a longer program can't win, so it's wasted work (this is 15// exactly why deepening past the cap hung on primes for no benefit). 16// sg_reachable -- an admissible BRANCH-AND-BOUND prune (the THURBER bound, generalized): from 17// a partial state of magnitude `cur`, with `rem` ops left each growing the 18// magnitude by at most factor 2^growth_bits, the target is reachable only if 19// cur << (growth_bits*rem) >= target. Complete: never prunes a real solution. 20// sg_decide -- the COST SELECTION: use the found program iff one was found within the cap 21// AND its cost (len*op_cost) <= baseline_cost; else use the baseline. This is 22// the single judgment shared by multiply (chain vs imul) and boolean (circuit 23// vs the compiler's sum-of-products) and anything else. 24// Refs: Kolmogorov complexity (uncomputable); Levin universal search / Kt; Thurber 1999 (addition- 25// chain branch-and-bound). license_tier: ORIGINAL 26 27const SG_USE_BASELINE: i64 = 0 // sg_decide verdict: the baseline alternative wins (e.g. imul) 28 29// LEVIN cost cap: the longest program worth searching for. A program of length L over ops costing 30// op_cost each costs L*op_cost; it can only beat/tie the baseline while L*op_cost <= baseline_cost, 31// i.e. L <= baseline_cost/op_cost. Searching past this is provably wasted (the heart of why the 32// unbounded deepening was pointless). op_cost must be >= 1. 33func sg_cost_cap(baseline_cost: i64, op_cost: i64) -> i64 { 34 if op_cost <= 0 { return baseline_cost } 35 return baseline_cost / op_cost 36} 37 38// admissible reach prune (THURBER, generalized to a richer op set than +): is `target` still 39// reachable from magnitude `cur` in `rem` ops, when one op grows the magnitude by at most a factor 40// 2^growth_bits? Upper bound on reachable magnitude = cur << (growth_bits*rem). COMPLETE -- it 41// never rejects a state that could still reach the target, so pruning on its negation is safe. 42func sg_reachable(cur: i64, rem: i64, growth_bits: i64, target: i64) -> i64 { 43 if rem <= 0 { return 1 } 44 var t: i64 = target; if t < 0 { t = 0 - t } 45 var c: i64 = cur; if c < 0 { c = 0 - c } 46 let sh: i64 = growth_bits * rem 47 if sh >= 62 { return 1 } // bound beyond i64 range -> treat as reachable 48 if (c << sh) >= t { return 1 } 49 return 0 50} 51 52// COST SELECTION (the shared judgment): given the shortest program length found (found_len <= 0 53// means none within the cap), the per-op cost, and the baseline's cost, return found_len if the 54// found program is the cost-winner (cost <= baseline), else SG_USE_BASELINE (0). One decision, 55// every search space. 56func sg_decide(found_len: i64, op_cost: i64, baseline_cost: i64) -> i64 { 57 if found_len <= 0 { return SG_USE_BASELINE } 58 if found_len * op_cost <= baseline_cost { return found_len } 59 return SG_USE_BASELINE 60}