Undecidability of Post's Correspondence Problem

1. What is the Post's Correspondence Problem?

Imagine you have a collection of dominos. Unlike regular dominos with dots, these have strings written on their top and bottom halves.

The goal of the "game" is to find a sequence of these dominos (you can reuse any domino as many times as you like) and line them up so that the string you get by reading all the top halves is identical to the string you get by reading all the bottom halves. Such a sequence is called a match.

Let's see this in action.

Formal Definition

Formally, an instance of the Post's Correspondence Problem is a collection $P$ of "dominos." Each domino is a pair of non-empty strings.
$P=\left\{\left(\begin{array}{c}{t}_1\\ b_1\end{array}\right),\left(\begin{array}{c}{t}_2\\ b_2\end{array}\right),\dots ,\left(\begin{array}{c}{t}_k\\ b_k\end{array}\right)\right\}$
where $t_i$ is the top string and $b_i$ is the bottom string of the $i$-th domino.

A match for $P$ is a sequence of indices $i_1,i_2,\dots ,i_m$ such that the concatenation of the top strings equals the concatenation of the bottom strings:
$t_{i_1}{t}_{i_2}\dots t_{i_m}=b_{i_1}{b}_{i_2}\dots b_{i_m}$

The decision problem, PCP, is: Given a collection of dominos $P$, does a match exist?

2. The Undecidability of PCP

At first glance, PCP seems decidable. You could write a program to perform a breadth-first search on all possible sequences of dominos. If a match exists, you will eventually find it.

But what if a match doesn't exist? How do you know when to stop searching?

The problem is that the search for a match might go on forever. This is the same dilemma as the Halting Problem: we can confirm a "yes" answer (the TM halts, or a match exists) by observing it, but we can't always confirm a "no" answer.

This leads to the main result of this lesson:
Post's Correspondence Problem (PCP) is undecidable.

There is no algorithm that can take any arbitrary PCP instance and correctly report "yes" or "no" in a finite amount of time for all inputs.

3. How to Prove PCP is Undecidable

The proof is a beautiful application of the reduction technique you learned in the last lesson. We show that PCP is undecidable by reducing the Turing Machine Acceptance Problem, $A_{TM}$, to it.

$A_{TM}{\le }_{m}PCP$

The strategy is to build a constructor algorithm that takes an input for $A_{TM}$ (a Turing Machine $M$ and an input string $w$) and produces a PCP instance that has a match if and only if $M$ accepts $w$.

The core idea is to design the dominos such that the only possible match they can form is a sequence representing the accepting computation history of $M$ on $w$.

This is a multi-step proof, which we will only sketch. The full details are intricate, but the high-level concept is elegant and relies on two main steps:

1. Reduce $A_{TM}$ to a slightly easier version of the problem, called the Modified Post's Correspondence Problem (MPCP).
2. Reduce MPCP to the standard PCP.

The following document gives an excellent, clear overview of this proof strategy.

Step 1: Reduction from $A_{TM}$ to MPCP

The Modified PCP (MPCP) is the same as PCP, but with an additional rule: the match must begin with a specific, designated start domino.

To reduce $A_{TM}$ to MPCP, we construct a set of dominos from $⟨M,w⟩$ that simulates $M$'s computation.

1. Start Domino: The designated start domino is $\left(\begin{array}{c}\#\\ \#q_{0}w\#\end{array}\right)$. This sets up the initial configuration on the bottom string. The top string is "lagging behind."

2. Copying Dominos: For every tape symbol a, we have a domino $\left(\begin{array}{c}a\\ a\end{array}\right)$. These are used to copy the parts of the configuration that the TM head is not touching.

3. Transition Dominos: These are the heart of the simulation. They encode $M$'s transition function $\delta$.

   • For a right move, $\delta (q,a)=(p,b,R)$, we create a domino $\left(\begin{array}{c}qa\\ bp\end{array}\right)$. This tile matches qa (state q seeing symbol a) on the top string and puts bp (the new symbol b and new state p) on the bottom string.
   • For a left move, $\delta (q,c)=(p,d,L)$, we need to look at the symbol to the left. For every tape symbol a, we create a domino $\left(\begin{array}{c}aqc\\ pad\end{array}\right)$.

4. "Cleanup" Dominos: Once the simulation on the bottom reaches an accepting state $q_{accept}$, we need the top string to "catch up" so a match can be completed. We add special dominos that "eat" the symbols around the accepting state until the top and bottom strings are identical.

If $M$ accepts $w$, a sequence of these dominos can be assembled to form a match that corresponds to the accepting computation history. If $M$ does not accept $w$, no such history exists, and the tiles are constructed so that no other kind of match is possible.

Step 2: Reduction from MPCP to PCP

The final step is to show that if we can solve PCP, we can solve MPCP. This proves PCP is at least as hard as the (undecidable) MPCP.

The trick is to modify the MPCP instance so that the "special start domino" is the only one that can possibly begin a match, even without an explicit rule.

Given an MPCP instance $P=\{d_1,d_2,\dots ,d_k\}$ with start domino $d_1$, we construct a PCP instance $P^{\prime }$ as follows:

1. Introduce a new special symbol, *, that appears nowhere else.
2. For the start domino $d_1=\left(\begin{array}{c}{t}_1\\ b_1\end{array}\right)$, create a new domino $d_1^{\prime }=\left(\begin{array}{c}\ast t_1\\ \ast b_1\ast \end{array}\right)$.
3. For every other domino $d_i=\left(\begin{array}{c}{t}_i\\ b_i\end{array}\right)$ (for $i>1$), create a new domino $d_i^{\prime }=\left(\begin{array}{c}\ast t_i\\ b_i\ast \end{array}\right)$.
4. Add an extra copy of the modified start tile for use in the middle of a sequence: $d_1^{\prime \prime }=\left(\begin{array}{c}\ast t_1\\ b_1\ast \end{array}\right)$.
5. Add a final domino to end the match: $d_{end}=\left(\begin{array}{c}\ast \\ ϵ\end{array}\right)$ (or a similar construction to balance the *s).

In this new set $P^{\prime }$, the only domino whose top and bottom strings both begin with the same character (*) is $d_1^{\prime }$. Therefore, any match must start with $d_1^{\prime }$. We have effectively forced the MPCP start condition without needing a special rule.

This completes the reduction chain $A_{TM}{\le }_{m}MPCP{\le }_{m}PCP$, proving that PCP is undecidable.

Conclusion

Today, we've explored the Post's Correspondence Problem, a fascinating puzzle that bridges the gap between abstract Turing Machines and more concrete combinatorial problems. While it appears simple, its undecidability reveals a fundamental limitation of computation.

Key Takeaways:

• Post's Correspondence Problem (PCP) asks if a given set of dominos has a "match," where the top and bottom strings formed by a sequence of dominos are identical.
• PCP is undecidable. There is no general algorithm that can solve all instances of PCP.
• The proof of undecidability is a reduction from $A_{TM}$. The core idea is to construct a PCP instance where a match corresponds precisely to an accepting computation history of a Turing Machine.
• This result is important because PCP is a useful tool for proving other problems are undecidable, especially in the domain of formal languages and grammars.

Preview of the Next Lesson:
We will immediately put this new tool to use. In the next lesson, we will leverage the undecidability of PCP to prove that another fundamental problem is undecidable: determining whether two context-free grammars generate the same language ($E{Q}_{CFG}$). This will show how the limits of computation extend up through the Chomsky Hierarchy.