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.

  • 10
    $\begingroup$ If I understand your question correctly, you seem to have some misunderstanding about decidability. The statement that Post’s Correspondence Problem is undecidable means that no algorithm gives the correct answer to all pairs of lists. In other words, we cannot say “this instance of Post’s Correspondence Problem is undecidable” because decidability is a property of a problem, not a property of individual instances of the problem. $\endgroup$ – Tsuyoshi Ito Aug 12 '10 at 22:28
  • 2
    $\begingroup$ By the way, it seems to me that the “computability-theory” tag is more appropriate than “cs.cc.complexity-theory”, as we aren’t dealing with complexity matters here. $\endgroup$ – Antonio E. Porreca Aug 12 '10 at 23:14

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.

  • 4
    $\begingroup$ And more than just open problems, since in principle these might be decided eventually, you can find specific Post Correspondence problems such that the question of whether there is a matching is not provable in ZFC, or in whatever fixed theory $T$ you like. To see this, use the correspondence problem corresponding to the Turing machine that searches for a proof of a contradiction from $T$. If $T$ is consistent, then there will be no correspondence, but $T$ will not prove this. $\endgroup$ – Joel David Hamkins Aug 12 '10 at 23:36
  • $\begingroup$ I’m not sure I’ve ever met this argument before, thanks! $\endgroup$ – Antonio E. Porreca Aug 13 '10 at 0:42

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}$.

  • 3
    $\begingroup$ Dan, the point is that for a fixed instance of the problem, the answer is either Yes or it is No, and so one of the two algorithms "say yes" or "say no", will give the right answer. This is the point of Tsuyoshi's remark. $\endgroup$ – Joel David Hamkins Aug 13 '10 at 0:34
  • 1
    $\begingroup$ If you think of your problem at the end, however, as a general problem (given v's and w's, determine if the indices exist to make a matching), then this is equivalent to the Post Correspondence problem, and there will be no computable such algorithm to determine it. $\endgroup$ – Joel David Hamkins Aug 13 '10 at 0:37
  • 3
    $\begingroup$ I guess the point of confusion here is that, even when you’ve fixed a group G, you still have another input to give to the hypothetical algorithm (the “word” to check), and the same reasoning applies: you cannot find a specific “undecidable word”. A specific group having undecidable word problem and a specific “undecidable PCP instance” are two very different objects. $\endgroup$ – Antonio E. Porreca Aug 13 '10 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.