I have read a couple of proofs for the undecidability of the post correspondence problem, but neither reference gave a concrete example of two lists of words over a fixed alphabet such that the problem was undecidable for that set of two lists. In other words, the proofs showed the existence of such an example without actually giving the example. Does anybody know a reference where I can find such an example? Thanks.

As Tsuyoshi said, it doesn’t make sense to search for an undecidable instance of a problem. It’s only the problem itself that can be undecidable. In particular, for every instance of PCP (or any other problem for that matter) there trivially exists an algorithm that gives the correct answer for that particular instance. If we’re dealing with the decision version of the problem, it’s either the algorithm that always answers “yes”, or the algorithm that always answers “no” (granted, this is not a constructive proof). On the other hand, you might find specific instances of PCP without a known answer, for example by exploiting any open problem of mathematics and the fact that the halting problem reduces to PCP, say via a manyone reduction R. Consider the Turing machine M that searches for a proof of the Riemann hypothesis by enumerating all proofs, and halts when it finds it. If RH is provable, this machine will halt in a finite amount of time, otherwise it will run forever. You can use the reduction from the halting problem to construct a PCP instance R(M) = x. Now, by deciding whether x is a positive or negative instance of PCP, you also decide RH. But that’s an open problem, and so the status of x also is. 


I guess I don't understand why it doesn't make sense to look for an exact instance in which the problem is undecidable. In group theory the word problem is undecidable, and there are examples of particular group presentations in which the word problem is undecidable for that exact group. So there is no algorithm that can handle any group presentation, and furthermore there is a group such that no algorithm can handle that exact group. So I'm wondering if there is an example of two lists of words $\{v_1,...,v_n\},$ and $ \{w_1,...,w_n\}$ such that there is no algorithm to decide if there is a list of indices $i_1,...,i_k$ with $v_{i_1}...v_{i_k}=w_{i_1}...w_{i_k}$. 

