Post Correspondence problem provable instance
The smallest solution is


  0110011010010010110011001101001101001001101001001011000100101101010010010100100100101100110001010011010010011000100101100010010100100101001010011000100101


generated by the string


  bdcddbabdcdcddcddbaddbacdaacdddbabaaacdcdabaddbadaacdaacaacabadaac


where $a = (001,0)$, $b=(01,011)$, $c=(01,101)$, $d=(10,001)$.

This solution can be found by a simple pruning procedure:


Start with the list $L$ which contains a pair of empty strings.
At each iteration, attempt to add each of the four "pieces" to each of the pairs in $L$, and remove any pair for which no string is a prefix of the other.


Eventually $L$ will contain a pair of equal strings, in this case after 66 iterations.

As an example, here is the contents of $L$ in the first few iterations:


Iteration 1: (001,0), (01,011)
Iteration 2: (001001,00), (0110,011001)
Iteration 3: (011001,011001011), (011001,011001101)
Iteration 4: (01100101,011001011011), (01100101,011001011101), (01100110,011001101001)


The number of pairs of strings at every iteration fluctuates but generally increases, and after 66 iterations reaches 12081, one of which is the solution given above.