Proof that the Post Correspondence Problem is undecidable

277 Views Asked by At

The lecture of MIT professor Michael Sipser, available here and his book Introduction to the Theory of Computation, Third Edition, chapter 5, both contain essentially the same proof that there can be no machine that decides the Post Correspondence Problem. That is, no machine that, given a set of dominoes, will tell you whether or not they can be arranged (with duplication allowed) so that there is a match. By a match, it is meant that if you read the strings off of the top halves, all concatenated together, you get the same result that you get reading the strings off the bottom halves.

The proof is by reducing an undecidable problem, the Turing machine acceptance problem, to the Post Correspondence decision problem. I have no issue with the use of reduction. However, I have a problem with the way the reduction is performed. He explains how, given a Turing machine's description, one can construct a set of dominoes and an arrangement of those dominoes. He seems to say that the arrangement is a match if and only if the dominoes, taken together, match a computation history for the Turing machine.

As an example of a computation history, if the machine starts in $q_0$ with the string 01001, writes a 1, transitions to $q_1$ and moves to the right, then the beginning of the computation history would be

$\#q_001001\#0q_11001\#...$

I can see that there is a match if the machine accepts its input, but I cannot see that there is no match if the machine doesn't accept its input. There are a lot of dominoes and it doesn't seem that he is eliminating the chance of forming a match from some combination of them.

He doesn't give rules for the construction of the domino arrangement; he only gives an example. In some cases, it appears that there is more than one way to choose the next domino.

So, in summary my question is "given a case where the Turing machine rejects the string, how do we know that the set of matches is empty?"

1

There are 1 best solutions below

0
On

I cannot easily give an answer to the particular concern regarding your question, since I have not looked at the reference. But here is a pointer to a paper (also available on the arXiv) discussing a reduction (divided into several steps) of the halting problem to the Post correspondence problem. They cite the book by Sipser as one of their references, so some of the steps might just be taken from him. Most importantly however, the paper comes with the benefit that the complete proof has been checked by a proof-assistant, so there should be very much less doubts about the correctness.