SKEDSOFT

Post’s correspondence problem (PCP): At first glance, a PCP instance is a simple puzzle about finite sequences3 of pairs of strings of the form
01, 101, ε01, 01, 101. It is customary to think of the above as “tiles” (or “dominoes”), with each tile at the respective index portrayed thus:

The question is: is there an arrangement of one or more of the above tiles, with repetitions allowed, so that the top and bottom rows read the same? Here is such an arrangement:

In obtaining this solution, the tiles were picked, with repetition, according to the sequence given by the indices 3,2,0,3,1:

Given a PCP instance S of length N (N = 4 in our example), a solution is a sequence of numbers i1, i2, . . . , ik where k ≥ 1 and each ij ∈ {0 . . .N − 1} for j ∈ {1 . . . k} such that S[i1]S[i2] . . .S[ik] has the property of the top and bottom rows reading the same. By the term “solution” we will mean either the above sequence of integers or a sequential arrangement of the corresponding tiles. Note that 3,2,0 is another solution, as is 3,1. The solution 3,1 is: