Undecidable Dominoes

Post’s correspondence problem

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Post’s correspondence problem: line up dominoes so top and bottom match.
• It is undecidable: dominoes can simulate any Turing machine.
• Searching finds every match that exists, but can never prove that none does.

Steps

1. A puzzle with no algorithm
2. Make a match
3. A harder set
4. Spotting a dead end
5. Dominoes that compute
6. Just search!