There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here:


I'll assume whoever will answer the question will be familiar with this proof.

I have seen this proof elsewhere and this kind of proof always mentions that if the $TM \ M$ halts we can solve the instance of the PCP. So far so good.

Now I was thinking about the case when the $TM \ M$ does not halt on input $w$. Then out total number of tuples/pairs ($\small{(a_i,b_i)}$, which get passed onto the PCP) should be countably infinite.

How can we even try to solve the PCP at this point ? Or do we implicitly think: "Thats impossible !" and say "There is no solution!" ?

This part confuses me very much because for the case that the TM halts we construct such a complex method and it seemed "cheap" to just throw the towel for the case when it would not halt.

I hope I could make my thoughts understandable, without much formality.

Any help is appreciated.

  • 1
    $\begingroup$ The total number of tile pairs is always finite. I suggest reading a formal account, for example in Sipser's textbook. $\endgroup$ – Yuval Filmus Aug 7 '18 at 19:22
  • $\begingroup$ @YuvalFilmus I actually have a copy of Sipser, do you mind giving a reference, because while I have not rigorously studied the proof in sipser I never saw anything about the case where the TM does not halt $\endgroup$ – zython Aug 7 '18 at 19:30

An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:

  • The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
  • The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
  • The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.

A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.

Let us denote the tiles by $(a_1,b_1),\ldots,(a_n,b_n)$. When $M$ halts on $w$, there exists a number $N$ and a sequence $i_1,\ldots,i_N \in \{1,\ldots,n\}$ such that $$ a_{i_1} a_{i_2} \ldots a_{i_N} = b_{i_1} b_{i_2} \ldots b_{i_N}. $$ When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an infinite sequence $i_1,i_2,\ldots$ such that $$ a_{i_1} a_{i_2} \ldots = b_{i_1} b_{i_2} \ldots, $$ where both sides are infinite words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.

  • $\begingroup$ thank you for answering; you understood my question. accepted ! $\endgroup$ – zython Aug 8 '18 at 8:06

Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.

I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.


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.