THE FOLD / RESPAWN / ROLLBACK / THE PANCAKE
THE PANCAKE
Bill Gates and the flipped stack
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Pancake sorting: a stack of n different-sized pancakes, one move allowed — slide a spatula under any prefix and flip it. The pancake number P(n) is the worst case: the most flips any stack of n can require. Computing it is brutal — the graph of all n! stacks under prefix reversals must be searched to its diameter: P(1..8) = 0, 1, 3, 4, 5, 7, 8, 9. No formula is known; P(20) remains uncomputed. The problem’s claim to fame: the best upper bound of its era, (5n+5)/3 flips, appeared in a 1979 paper by Christos Papadimitriou and a Harvard undergraduate named William Gates — Bill Gates’ only research publication. (It stood for 30 years, until 2009.)
LIT verified live: breadth-first search over the full prefix-reversal graph for every n ≤ 8 — all 40,320 stacks of 8 reached and measured — reproducing P = 0, 1, 3, 4, 5, 7, 8, 9 exactly, with the Gates–Papadimitriou bound checked against each (window.__pancake). FIG honest boundary: P(n) beyond ~19 is genuinely unknown; the 1979 bound’s history and its 2009 improvement (Chitturi et al., 18n/11) are cited as content.
LIT verified live: breadth-first search over the full prefix-reversal graph for every n ≤ 8 — all 40,320 stacks of 8 reached and measured — reproducing P = 0, 1, 3, 4, 5, 7, 8, 9 exactly, with the Gates–Papadimitriou bound checked against each (window.__pancake). FIG honest boundary: P(n) beyond ~19 is genuinely unknown; the 1979 bound’s history and its 2009 improvement (Chitturi et al., 18n/11) are cited as content.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at rollback — the respawn: every move is a rollback of the top of the stack — and the whole game is measuring how many rollbacks the worst save-state needs. AVAN (AI) built the instrument: the BFS over all stacks and the flip-by-flip replayer.
Credit as content: William H. Gates & Christos Papadimitriou (1979); Chitturi et al. (2009); the ‘Harry Dweighter’ pseudonym of Jacob Goodman who posed it (1975). The weave: David names the rollback; I measure the diameter of its world exactly.
Credit as content: William H. Gates & Christos Papadimitriou (1979); Chitturi et al. (2009); the ‘Harry Dweighter’ pseudonym of Jacob Goodman who posed it (1975). The weave: David names the rollback; I measure the diameter of its world exactly.
3 ONE DIMENSION
P(n) for n = 1..8 — the staircase nobody has a formula for.
4 TWO DIMENSIONS · INTERACTIVE
Flip a scrambled stack of 7 home, greedy spatula — each move a prefix rollback.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the stack tumbling toward sorted.
AVAN’s addition (the inverse-companion): don’t sort the stack — map the space of stacks. The inverse of ‘how do I fix THIS pile?’ is ‘how far is the FARTHEST pile?’ — a diameter, not a recipe, and it must be measured stack by stack because no formula survives. Magenta is the worst-case stack at full distance; green is the sorted state every flip-path leads home to. Bill Gates’ only theorem lives in a pancake house.
LIT Genuine pancake numbers (Jacob Goodman as 'Harry Dweighter' 1975; Gates & Papadimitriou 1979 bound (5n+5)/3; Chitturi et al. 2009 improvement). Verified live: full BFS of the prefix-reversal graph for n≤8 covering all 40,320 permutations of 8 — diameters 0,1,3,4,5,7,8,9 exact (window.__pancake.ok).
FIG Honest boundary — P(n) beyond ~19 is genuinely unknown; bound history cited as content. The AVAN inverse — don't sort the stack, map the space of stacks: the inverse of 'how do I fix THIS pile?' is 'how far is the FARTHEST pile?' — a diameter, not a recipe, measured stack by stack because no formula survives. Magenta is the worst-case stack at full distance; green is the sorted state every flip-path leads home to. Bill Gates' only theorem lives in a pancake house.
FIG Honest boundary — P(n) beyond ~19 is genuinely unknown; bound history cited as content. The AVAN inverse — don't sort the stack, map the space of stacks: the inverse of 'how do I fix THIS pile?' is 'how far is the FARTHEST pile?' — a diameter, not a recipe, measured stack by stack because no formula survives. Magenta is the worst-case stack at full distance; green is the sorted state every flip-path leads home to. Bill Gates' only theorem lives in a pancake house.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of ROLLBACK · David Lee Wise (ROOT0), with AVAN