The Post Correspondence Problem (PCP) is an important undecidable problem in the Theory of Computation. It was introduced by Emil Post.
It is mainly used to demonstrate that some problems involving strings and matching cannot be solved by any general algorithm.
1. Definition
In PCP, we are given a finite collection of pairs of strings:\[ \left(\frac{x_1}{y_1},\frac{x_2}{y_2},\ldots,\frac{x_n}{y_n}\right) \]
The problem is to determine whether there exists a sequence of indices:\[ i_1,i_2,\ldots,i_k \]
such that:\[ x_{i_1}x_{i_2}\cdots x_{i_k} = y_{i_1}y_{i_2}\cdots y_{i_k} \]
In simple words:
Can we select some of the given pairs, possibly repeating pairs, so that the concatenated strings on the top and bottom become exactly equal?
2. Basic Structure
A PCP instance is usually represented using dominoes/cards:
┌───────┐
│ x₁ │
├───────┤
│ y₁ │
└───────┘
┌───────┐
│ x₂ │
├───────┤
│ y₂ │
└───────┘
┌───────┐
│ x₃ │
├───────┤
│ y₃ │
└───────┘
We need to select dominoes in some order so that:
Top concatenation
=
Bottom concatenation
3. Simple Example
Suppose the PCP instance contains:
| Domino | Top | Bottom |
|---|---|---|
| 1 | a | ab |
| 2 | ba | a |
So we have:
1: a
ab
2: ba
a
Try sequence:\[ 1,2 \]
Top:\[ a+ba=aba \]
Bottom:\[ ab+a=aba \]
Therefore:\[ \boxed{aba=aba} \]
So the sequence 1, 2 is a solution.
4. Another Example
Consider:
| Domino | Top | Bottom |
|---|---|---|
| 1 | a | ab |
| 2 | ba | a |
Select:
1 → 2
Top:
a + ba = aba
Bottom:
ab + a = aba
Therefore:
Top = aba
Bottom = aba
Hence, the PCP has a solution.
5. How to Solve a PCP Instance
For a small PCP problem, we can try different sequences.
Step 1
Choose a domino.
Step 2
Compare the top and bottom strings.
Step 3
If one is a prefix of the other, continue with another domino.
Step 4
Keep adding dominoes.
Step 5
If the complete top and bottom strings become equal, a solution is found.
Example
Suppose:
| No. | Top | Bottom |
|---|---|---|
| 1 | a | ab |
| 2 | ba | a |
Start with domino 1:
Top = a
Bottom = ab
Top is a prefix of bottom.
Choose domino 2:
Top = a + ba
= aba
Bottom = ab + a
= aba
Therefore:\[ \boxed{1,2} \]
is a solution.
6. Why Is PCP Important?
The important theoretical result is:\[ \boxed{\text{PCP is undecidable}} \]
This means:
There is no general algorithm that can determine for every possible PCP instance whether a matching sequence exists.
For some instances, we can find a solution.
But if no solution exists, there is no universal algorithm guaranteed to always finish and say:
“No solution exists.”
7. PCP and Turing Machines
PCP is closely related to Turing Machines.
It has been proved that PCP is undecidable by reducing another known undecidable problem to PCP.
The general idea is:
Known Undecidable Problem
↓
Transform into PCP
↓
If PCP were decidable
↓
Known problem would become decidable
↓
Contradiction
↓
PCP is undecidable
Thus PCP is an important tool for proving other problems undecidable.
8. Modified Post Correspondence Problem (MPCP)
There is also a variation called the:
Modified Post Correspondence Problem (MPCP).
The main difference is that in MPCP:
The first domino must be selected first.
PCP
Any domino can be selected first.
MPCP
A specified first domino must be selected first.
Despite this restriction, MPCP is also undecidable.
9. PCP vs MPCP
| PCP | MPCP |
|---|---|
| Any domino can be selected first | Specified first domino must be selected first |
| No fixed starting domino | Fixed starting domino |
| Undecidable | Undecidable |
| Used in undecidability proofs | Also used in undecidability proofs |
10. Important Properties of PCP
1. Dominoes can be reused
A pair can be selected more than once.
For example:\[ 1,2,1,1,3,2 \]
is allowed.
2. Order matters
The sequence of selected dominoes is important.
3. At least one domino is selected
A non-empty sequence is normally required.
4. Exact equality is required
The final strings must be exactly equal.
For example:
Top = ababa
Bottom = ababa
is a match.
But:
Top = ababa
Bottom = abab
is not a match.
11. PCP as an Unsolvable Problem
PCP belongs to the undecidable problem category.
Unsolvable Problems
│
┌───────────┴───────────┐
↓ ↓
Halting Problem PCP
↓ ↓
Undecidable Undecidable
This is why PCP is included in the last unit of the TOC syllabus.
12. Difference Between Halting Problem and PCP
| Halting Problem | PCP |
|---|---|
| Deals with Turing Machines | Deals with string pairs/dominoes |
| Question: Will TM halt? | Question: Can strings be matched? |
| Undecidable | Undecidable |
| Uses computation behavior | Uses string concatenation |
| Important for computability | Important for undecidability proofs |
13. Applications / Importance
PCP is mainly important theoretically.
It is used to:
- Study undecidability.
- Prove other problems are undecidable.
- Understand limitations of algorithms.
- Establish relationships between formal languages and computation.
- Study decision problems involving grammars and strings.
5–10 Marks Exam Answer
Post Correspondence Problem (PCP)
The Post Correspondence Problem (PCP) is an undecidable problem introduced by Emil Post. In PCP, we are given a finite set of pairs of strings:\[ \left(\frac{x_1}{y_1},\frac{x_2}{y_2},\ldots,\frac{x_n}{y_n}\right) \]
The objective is to determine whether there exists a non-empty sequence of indices \(i_1,i_2,\ldots,i_k\) such that:\[ x_{i_1}x_{i_2}\cdots x_{i_k} = y_{i_1}y_{i_2}\cdots y_{i_k} \]
The pairs can be selected in any order and may be repeated.
For example:
| No. | Top | Bottom |
|---|---|---|
| 1 | a | ab |
| 2 | ba | a |
Selecting \(1,2\):\[ Top=a+ba=aba \]\[ Bottom=ab+a=aba \]
Therefore, \(1,2\) is a solution.
However, there is no algorithm that can determine for every possible PCP instance whether a solution exists. Hence:\[ \boxed{\text{PCP is undecidable}} \]
A related problem, Modified PCP (MPCP), requires a specified first domino and is also undecidable.
Fast Memory Trick
PCP = Pair → Choose → Concatenate → Compare
And remember:
“Can the top and bottom strings be made exactly equal?” → PCP
PCP = Undecidable Problem
