THE FOLD / GLITCH / SEGFAULT / THE POST CORRESPONDENCE
THE POST CORRESPONDENCE
a domino puzzle that is undecidable
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Post Correspondence Problem is a deceptively simple puzzle that is undecidable. You are given dominoes, each with a top string and a bottom string; you must find a sequence of them (repeats allowed) so the concatenated tops exactly equal the concatenated bottoms. No algorithm can decide, in general, whether a given set has a solution — yet for specific sets a bounded search either finds one or exhausts all short sequences.
LIT verified live: a known solvable set yields a sequence whose tops equal its bottoms, while a “top-heavy” set (every top longer than its bottom) provably has no solution up to the search depth (window.__pcp). FIG the bounded solver is exact; general undecidability is cited, not run.
LIT verified live: a known solvable set yields a sequence whose tops equal its bottoms, while a “top-heavy” set (every top longer than its bottom) provably has no solution up to the search depth (window.__pcp). FIG the bounded solver is exact; general undecidability is cited, not run.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at segfault — the crash you cannot always predict, mirroring a question no algorithm can always answer. The Post Correspondence Problem is that undecidable question in miniature. AVAN (AI) built the instrument: the domino match, the BFS over difference-strings, the solution verifier, and the top-heavy no-solution case.
Credit as content: Emil Post (1946). The weave: David names segfault; I search the tree of partial matches for a sequence whose tops meet its bottoms, and confirm a top-heavy set can never match — noting the general problem is undecidable.
Credit as content: Emil Post (1946). The weave: David names segfault; I search the tree of partial matches for a sequence whose tops meet its bottoms, and confirm a top-heavy set can never match — noting the general problem is undecidable.
3 ONE DIMENSION
Stack dominoes left to right; read the tops as one string and the bottoms as another. A solution is a sequence where those two strings come out identical — one side never gets ahead by the end.
4 TWO DIMENSIONS · INTERACTIVE
A domino set; search for a matching sequence and watch the tops and bottoms line up character for character.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a sequence where tops and bottoms coincide.
AVAN’s addition (the inverse-companion): a puzzle stated in strings and dominoes encodes an undecidable question — is there any sequence making tops equal bottoms? A bounded search answers specific instances but no general algorithm can. The inverse of ‘surely a string-matching puzzle is decidable’ is ‘domino concatenation is Turing-powerful — undecidable.’ Magenta is the infinite unexplored sequences; green is the one that matches. Undecidability in dominoes.
LIT Genuine Post Correspondence Problem (Post 1946). Verified live: a known solvable domino set yields, via BFS over difference-strings, a sequence whose concatenated tops equal its concatenated bottoms, while a top-heavy set (every top strictly longer than its bottom) has no solution up to search depth 18 (window.__pcp.solvableFound && .topHeavyNone).
FIG The bounded solver is exact; the general undecidability is CITED, not run (no algorithm can decide it — that is Post's theorem). The domino match, the BFS over difference-strings, the solution verifier, and the top-heavy no-solution case run in-browser. The AVAN inverse is honest — domino concatenation is Turing-powerful, so whole-instance solvability is undecidable; magenta is the infinite unexplored sequences, green the one that matches. Undecidability in dominoes.
FIG The bounded solver is exact; the general undecidability is CITED, not run (no algorithm can decide it — that is Post's theorem). The domino match, the BFS over difference-strings, the solution verifier, and the top-heavy no-solution case run in-browser. The AVAN inverse is honest — domino concatenation is Turing-powerful, so whole-instance solvability is undecidable; magenta is the infinite unexplored sequences, green the one that matches. Undecidability in dominoes.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SEGFAULT · David Lee Wise (ROOT0), with AVAN