Show HN: Posting Puzzle – A Game Made of Post's Correspondence Problem

2 pointsposted 11 hours ago
by mametter

1 Comments

mametter

11 hours ago

A small puzzle about sorting envelopes and stamps: Post's Correspondence Problem with a postal skin on top. Twelve stages. The first six can be solved by hand; the last six are instances taken from the literature, and cannot.

If you have not met the problem before, this is a way to get a feel for it: the rule is all there is to it, and it is undecidable in general.

Made to celebrate every instance of PCP[3,4] finally being resolved: https://github.com/Mojashi/pcp-3-4-proofs