Consider the following puzzle: We are given a set of domino-like tiles. Let's say we have dominoes of 4 types:
and there is an unlimited number of tiles of each type. Each tile has two words written on it – the top and the bottom one. The problem is: Can we arrange the tiles in a sequence so that the word spelled on the top is the same as the word on the bottom?
In our simple example, this is indeed possible, and we can arrange the tiles like this
so that both top and bottom row spells "bababaababb".
For the formalists: by "word" we mean a finite sequence of symbols. Each tile is a pair of words (top, bottom) and the problem is, given a set of tiles {(u1, v1), (u2, v2), ..., (uk, vk)}, is there a finite sequence i1,...,in such that ui1 ui2 ... uin = vi1 vi2 ... vin?
Our second example:
doesn't have solution (you can try it out by clicking buttons 1., 2., 3.).
We can only start with tile 1 producing an extra b at the top.
Then we can only continue with tile 2. There will be an extra c at the bottom, so we can only
continue with tile 3, but this will create an extra b at the top again.
So there will always be an extra letter at either top or bottom.
The problem is named after Emil Post, who introduced it in 1946, and proved it is undecidable, i.e., you cannot write a computer program that correctly solves any instance of problem.