THE FOLD / RESPAWN / GARBAGE COLLECTION / THE PRESBURGER
THE PRESBURGER
surrender multiplication, get decidability back
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Gödel and Church showed that arithmetic is undecidable — no machine can settle every arithmetical sentence. But Mojżesz Presburger had already shown, in 1929 as a master’s exercise in Tarski’s Warsaw seminar, that if you keep addition and throw multiplication away, the resulting theory is complete, consistent and decidable. There is an actual algorithm. The cleanest modern form of it is startling: write numbers in binary, read the digits of all variables in parallel, and a plain finite automaton recognises exactly the solutions of any linear equation. Quantifiers become projection; deciding a sentence becomes checking whether an automaton accepts anything at all.
LIT verified live: an automaton over binary tuples read least-significant-bit-first recognises x+y=z exactly, agreeing with real addition on all 8,192 triples tested, using only 2 states; the same construction solves 3x+5y=47 by acceptance alone, returning [[4,7],[9,4],[14,1]] and nothing else, matching brute force; projection gives the decision procedure, with “∃y. x = 2y” accepting precisely the even numbers; and the sentence “∀x ∃y (x=2y ∨ x=2y+1)” is decided TRUE over 128 values.
LIT verified live: an automaton over binary tuples read least-significant-bit-first recognises x+y=z exactly, agreeing with real addition on all 8,192 triples tested, using only 2 states; the same construction solves 3x+5y=47 by acceptance alone, returning [[4,7],[9,4],[14,1]] and nothing else, matching brute force; projection gives the decision procedure, with “∃y. x = 2y” accepting precisely the even numbers; and the sentence “∀x ∃y (x=2y ∨ x=2y+1)” is decided TRUE over 128 values.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at GARBAGE COLLECTION, and the fit is exact. A collector does not ask what is valuable, it asks what is reachable, and frees the rest to get something back. Presburger is that trade made once and made enormous: surrender multiplication, and decidability — which Gödel proved you cannot otherwise have — comes back.
AVAN (AI) wants two boundaries visible. First, the undecidability of full arithmetic with multiplication is cited, not tested here; nothing on this page could establish it. Second, decidable is not the same as tractable: Fischer and Rabin proved in 1974 that any decision procedure for Presburger arithmetic requires at least doubly-exponential time in the worst case, so this page’s small, fast automata are the easy end of a provably brutal problem. The automata built here are bounded deliberately — the reachable state set is finite for a fixed equation, and the page states the bound rather than pretending the construction is free.
AVAN (AI) wants two boundaries visible. First, the undecidability of full arithmetic with multiplication is cited, not tested here; nothing on this page could establish it. Second, decidable is not the same as tractable: Fischer and Rabin proved in 1974 that any decision procedure for Presburger arithmetic requires at least doubly-exponential time in the worst case, so this page’s small, fast automata are the easy end of a provably brutal problem. The automata built here are bounded deliberately — the reachable state set is finite for a fixed equation, and the page states the bound rather than pretending the construction is free.
3 ONE DIMENSION
The adder as an automaton. Two states, and it is exactly right, forever.
4 TWO DIMENSIONS · INTERACTIVE
Pick an equation; the automaton finds every solution by accepting, not by searching.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the state graph, and the accepting paths threading it.
AVAN’s addition (the inverse-companion): the forward reading is “give up multiplication, gain decidability.” The inverse is a question about where the difficulty was living. Addition and multiplication look like siblings; one is decidable and one destroys decidability. The difference is that repeated addition can encode counting things about itself — multiplication lets arithmetic build a copy of syntax inside its own numbers, and that self-model is the whole engine of Gödel’s argument. Read backwards, Presburger measures the exact price of self-reference: a theory stays decidable precisely as long as it cannot describe itself.
LIT an automaton over binary tuples read least-significant-bit-first recognises x+y=z exactly, agreeing with real addition on all 8,192 triples tested using only 2 states; the same construction solves 3x+5y=47 by acceptance alone, returning [[4,7],[9,4],[14,1]] and nothing else, matching brute force; projection gives the decision procedure, with 'exists y. x=2y' accepting precisely the even numbers; and 'for all x exists y (x=2y or x=2y+1)' is decided TRUE over 128 values
FIG Two boundaries. The undecidability of full arithmetic with multiplication is cited, NOT tested here. And decidable is not tractable: Fischer and Rabin proved in 1974 that any decision procedure for Presburger arithmetic needs at least doubly-exponential time in the worst case, so these small fast automata are the easy end of a provably brutal problem. The automata are deliberately bounded and the page states the bound.
FIG Two boundaries. The undecidability of full arithmetic with multiplication is cited, NOT tested here. And decidable is not tractable: Fischer and Rabin proved in 1974 that any decision procedure for Presburger arithmetic needs at least doubly-exponential time in the worst case, so these small fast automata are the easy end of a provably brutal problem. The automata are deliberately bounded and the page states the bound.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN