nx_ncf_state_gate.nx source

1// nx_ncf_state_gate.nx -- X-AUT-NCF-001 RUNG 5: SYNTHESIZE A TWO-STATE LINEAR RECURRENCE -- the QUALITATIVE 2// jump the Fibonacci boundary revealed. Every prior construct (rungs 1-4) has ONE accumulator; this is the 3// first with TWO registers (a,b) updated in parallel each step: (a,b) <- (paa*a+pab*b, pba*a+pbb*b); return a. 4// That makes it small-PROGRAM synthesis, not curve-fitting -- it covers Fibonacci/Lucas/Pell (order-2 linear 5// recurrences) that NO single-accumulator loop can express. Decisive negative control: rung-4 quadratic-index 6// (the strongest single-accumulator construct) PROVABLY FAILS on Fibonacci -> two-state is NECESSARY. 7// T1 linear FAILS on Fibonacci. T2 rung-4 quadratic-index loop FAILS on Fibonacci -> two-state necessary. 8// T3 two-state SYNTHESIZES Fib = a=0,b=1; (a,b)<-(b, a+b); return a. 9// T4 MATERIALIZE+GOD-BUILD+run HELD-OUT {8->21, 9->34} -> 21034. T5 unified ncf_synth routes Fib (kind=5). 10// Construct ladder: linear < conditional < simple-loop < affine-index < quadratic-index < TWO-STATE. 11// expect_exit: 0 license_tier: ORIGINAL 12import "nx_ncf_synth.nx" 13import "nx_syscalls.nx" 14 15func main() -> i64 { 16 ncf_w("=== nx_ncf_state: SYNTHESIZE A TWO-STATE RECURRENCE (X-AUT-NCF-001 rung 5) -- Fibonacci, single-acc cannot ===\n" as *u8) 17 var pass: i64=0; var total: i64=0 18 19 // SPEC = Fibonacci: train x=0..7 {0,1,1,2,3,5,8,13} (over-determined), HELD-OUT {8->21, 9->34}. 20 let xs: *i64=sys_mmap(128) as *i64; let ys: *i64=sys_mmap(128) as *i64 21 xs[0]=0; xs[1]=1; xs[2]=2; xs[3]=3; xs[4]=4; xs[5]=5; xs[6]=6; xs[7]=7 22 ys[0]=0; ys[1]=1; ys[2]=1; ys[3]=2; ys[4]=3; ys[5]=5; ys[6]=8; ys[7]=13 23 let n: i64=8 24 25 let sp: *i64=sys_mmap(8) as *i64; sp[0]=0-1 26 let sfd: i64=sys_openat_wr(NCF_RESULT,420); if sfd>=0 { sys_write(sfd,sp as *u8,8); sys_close(sfd) } 27 28 // T1: linear FAILS. 29 let lin: i64=ncf_search_linear(xs,ys,n) 30 total=total+1; if lin==0 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } 31 ncf_w("T1 NEG-CONTROL: linear-only FAILS on Fibonacci, lin_found=" as *u8); ncf_n(lin); ncf_w("\n" as *u8) 32 33 // T2: rung-4 quadratic-index loop FAILS (strongest single-accumulator construct -- still can't, Fib is exponential). 34 let qform: *i64=sys_mmap(64) as *i64 35 let quad: i64=ncf_search_loop3(xs,ys,n,qform) 36 total=total+1; if quad==0 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } 37 ncf_w("T2 NEG-CONTROL: rung-4 QUADRATIC-INDEX loop FAILS on Fibonacci -> TWO-STATE necessary, quad_found=" as *u8); ncf_n(quad); ncf_w("\n" as *u8) 38 39 // T3: two-state recurrence SYNTHESIZES Fibonacci. 40 let form: *i64=sys_mmap(64) as *i64 41 let s: i64=ncf_search_loop4(xs,ys,n,form) 42 total=total+1; if s==1 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } 43 ncf_w("T3 SYNTHESIS: two-state FOUND a=" as *u8); ncf_n(form[0]); ncf_w(",b=" as *u8); ncf_n(form[1]); ncf_w("; (a,b)<-(" as *u8); ncf_n(form[2]); ncf_w("a+" as *u8); ncf_n(form[3]); ncf_w("b, " as *u8); ncf_n(form[4]); ncf_w("a+" as *u8); ncf_n(form[5]); ncf_w("b); return a for Fibonacci\n" as *u8) 44 45 // T4: MATERIALIZE -> GOD-BUILD -> run HELD-OUT -> verify (Fib(8)=21, Fib(9)=34 -> 21034). 46 var emitted: i64=0; if s==1 { if ncf_emit(5,form,8,9,1000)==0 { emitted=1 } } 47 var built: i64=0; if emitted==1 { if ncf_god_build(NCF_NAME)==0 { built=1 } } 48 let produced: i64=ncf_read(NCF_RESULT) 49 total=total+1; if produced==21034 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } 50 ncf_w("T4 MATERIALIZE+GOD-BUILD: synthesized two-state recurrence compiled (nx_cc->nxasm, no gcc) + ran HELD-OUT -> produced=" as *u8); ncf_n(produced); ncf_w(" (expect 21034 = Fib8*1000+Fib9)\n" as *u8) 51 52 // T5: the UNIFIED ncf_synth routes Fibonacci to the two-state construct (kind=5) = auto-widens the wiring. 53 let uform: *i64=sys_mmap(64) as *i64 54 let kind: i64=ncf_synth(xs,ys,n,uform) 55 total=total+1; if kind==5 { pass=pass+1; ncf_w(" [PASS] " as *u8) } else { ncf_w(" [FAIL] " as *u8) } 56 ncf_w("T5 UNIFIED: ncf_synth(Fibonacci) -> kind=" as *u8); ncf_n(kind); ncf_w(" (5=two-state recurrence) = the wiring now auto-routes Fibonacci (was the stable NOVEL->tutor boundary)\n" as *u8) 57 58 ncf_w("\n HONEST SCOPE: covers order-2 linear recurrences (Fibonacci/Lucas/Pell) -- two registers, linear update, coeffs in {0,1,2}. Order-3 (Tribonacci, needs three-state) + nonlinear-coupled (b'=a*b) + constants still escalate = the next rungs. Ladder: linear < conditional < simple-loop < affine-index < quadratic-index < two-state.\n" as *u8) 59 ncf_w("NCF-STATE verdict=" as *u8) 60 if pass==total { ncf_w("GREEN passes=" as *u8); ncf_n(pass); ncf_w("/" as *u8); ncf_n(total); ncf_w(" -- the team SYNTHESIZED + GOD-BUILT a two-state recurrence (small-program synthesis): X-AUT-NCF-001 rung 5\n" as *u8); sys_exit(0); return 0 } 61 ncf_w("RED passes=" as *u8); ncf_n(pass); ncf_w("/" as *u8); ncf_n(total); ncf_w("\n" as *u8); sys_exit(1); return 1 62}