Welcome to MathOverflow

Question

0

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.

edited Aug 12 2010 at 23:58

François G. Dorais♦
22.4k●2●48●113

asked Aug 12 2010 at 22:14

dan
469●2●3

10

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. – Tsuyoshi Ito Aug 12 2010 at 22:28

2

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. – Antonio E. Porreca Aug 12 2010 at 23:14

Antonio E. Porreca · Accepted Answer · 2010-08-13 01:18:25Z UTC

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.

dan · Answer 2 · 2010-08-13 00:22:28Z UTC

0

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

answered Aug 13 2010 at 0:22

dan
1

3

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. – Joel David Hamkins Aug 13 2010 at 0:34

1

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. – Joel David Hamkins Aug 13 2010 at 0:37

3

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. – Antonio E. Porreca Aug 13 2010 at 0:48

post correspondence problem

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.