CEGIS: Counterexample-Guided Program Synthesis

Program synthesis turns a specification into working code by searching a space of candidate programs and checking each one against the spec — the loop at the heart of modern AI-assisted, correctness-first code generation. This simulation makes the loop concrete and finite: the hidden spec is a linear program f(x) = a·x + b, the candidate space is every integer (a, b) on a 3D lattice, and each round a synthesizer proposes the first candidate consistent with every counterexample seen so far while a verifier probes the integer domain for a disagreement. Every counterexample it finds prunes the candidate lattice live in 3D, exactly like SMT-backed CEGIS tools (Sketch, Rosette) do over far richer program grammars, until the surviving candidate is provably equal to the hidden program.