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.



post correspondence problem
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 many-one 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.


