January 26, 2026
Stack tiles, stack opinions
The Post Correspondence Programming Language: Domino-oriented Programming (2015)
Domino coding: mind-blowing math trick or the nerdiest flex
TLDR: PCPL turns a domino-matching puzzle into a way to simulate any program, proving surprising power in a playful package. Commenters split between admiration for the elegance and skepticism about real-world use, trading pizza puns and 'Turing-complete' fatigue while debating whether beauty alone justifies a language no one will actually use.
Remember that time someone turned a dusty math puzzle into a “programming language”? That’s PCPL: line up dominos until the top and bottom rows match, and—boom—you’ve simulated computation. The demo shows it even nails least common multiple (LCM), and a wild example adds 1+11 by forcing a domino ‘run’ of machine steps.
The community mood? Split. One camp swooned over the elegance: a toy puzzle proving “you can compute anything” (that’s what Turing‑complete means). The other camp rolled their eyes: cute math art, but are we really coding with tiles? Cue pizza jokes and “domino effect” memes. Even dang noted it was only “discussed (a bit)” back in 2015—an under‑the‑radar cult gem resurfacing.
The drama centered on usefulness vs beauty: theorists cheered a teachable, visual way to explain machines; pragmatists asked for a compiler that doesn’t involve a coffee table. Some called it peak nerd flex; others saw classroom gold. A spicy sidebar: “Turing‑complete” fatigue—if everything is powerful in theory, what actually helps build apps?
Either way, the comments had fun. People imagined a cardboard REPL, code‑golfing with tiles, and “DominoLang 1.0” ship dates. Nerds argued, memes flew, and the dominos kept falling. Bottom line: it’s geeky, charming, and polarizing.
Key Points
- •PCP is presented as a programming language (PCPL) capable of encoding computations via domino matches.
- •A theorem shows that the shortest match in a specific PCP instance yields LCM(a, b), exemplified with a=4 and b=6 producing 12.
- •PCPL is asserted to be Turing-complete, with a proof referenced from Michael Sipser’s textbook.
- •The article compiles a unary addition Turing machine into a PCPL domino set that forces matches to begin with an input marker.
- •A worked example on input “1+11” yields an accepting computation history, demonstrating how PCPL simulates machine states and head movements.