computer science - 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.