PCP undecidability

Question

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

https://en.wikipedia.org/wiki/Post_correspondence_problem

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.

Answer 1

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.

Answer 2

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.

Answer 3

The total number of tile pairs is finite, the reason is: The number of the states of Turing machine M, the length of its input string w and the number of the tape alphabet are all finite, thus the number of their combinations, which are basically the tile pairs, is finite.