Post Correspondence Problem (PCP)
🧩 Post Correspondence Problem (PCP)
💡 1. What is the Post Correspondence Problem?
The Post Correspondence Problem (PCP) was introduced by Emil Post in 1946.
It is a classic undecidable problem that is often used to prove undecidability of other problems in computability theory.
It’s based on matching strings from two lists.
✉️ 2. The Setup
You are given two lists (or sequences) of strings over some alphabet, say Σ:
Each and is a string over the alphabet Σ.
🎯 3. The Goal
You must determine whether there exists a non-empty sequence of indices
such that when you concatenate the strings from both lists in that order,
the two results are equal.
That is:
Such a sequence is called a match or solution to the PCP instance.
🧮 4. Example
Let’s take an example over Σ = {0, 1}.
i | ||
---|---|---|
1 | 1 | 10 |
2 | 01 | 1 |
Now, let’s check:
If we pick sequence :
❌ Not equal.
But if we pick
✅ Equal!
So the sequence [1, 2] is a solution.
Another Example
⚙️ 5. The Decision Problem
The decision version of the PCP is:
Given two lists of strings
does there exist a non-empty sequence of indices such that
🚫 6. Why It’s Important
The PCP looks simple — just compare strings —
but surprisingly, there is no general algorithm that can determine whether such a sequence exists for all possible instances.
That is, the PCP is undecidable.
🧠 7. Proof of Undecidability
Let’s understand why.
Step 1: Suppose PCP is decidable.
That means there exists a Turing machine that can take any instance (two lists of strings) and decide:
-
✅ YES — if a matching sequence exists
-
❌ NO — if not
Step 2: Reduce a known undecidable problem to PCP.
To prove PCP is undecidable, we reduce another known undecidable problem to it.
We use the Halting Problem, which is already known to be undecidable.
Step 3: Idea of the reduction
We want to construct a PCP instance that simulates the behavior of a Turing machine M on an input w.
-
The PCP will have a solution if and only if M halts on w.
Thus, if we could solve PCP, we could solve the Halting Problem — which is impossible.
So PCP must also be undecidable.
Step 4: Encoding configurations
A configuration of a Turing machine (TM) is a snapshot of its current state, tape content, and head position.
Example configuration:
can be represented as a string like:
We can construct PCP pairs to simulate transitions between configurations — meaning the way a TM moves from one configuration to the next.
Step 5: How the reduction works
-
Encode each transition of the Turing machine as a pair of strings in PCP.
-
Each pair represents one possible move (reading, writing, moving head, changing state).
-
Matching in PCP corresponds to valid sequences of transitions in the Turing machine.
-
A valid match exists iff the Turing machine halts.
Thus, if we could solve PCP, we could decide if a Turing machine halts — contradiction.
Step 6: Therefore,
That is, no Turing machine can decide all instances of PCP.
📘 8. Related Version — Modified PCP (MPCP)
Sometimes textbooks use a Modified Post Correspondence Problem (MPCP) for proofs.
In MPCP:
-
The sequence of indices must start with the first pair .
-
Apart from that, it’s the same as PCP.
The MPCP is also undecidable, and it is usually shown first because it’s easier to reduce the Halting Problem to MPCP.
Then, we show that MPCP → PCP (reduction), proving that PCP is also undecidable.
🔁 Summary of the Proof Chain
-
Halting Problem is undecidable.
-
Halting Problem is reducible to Modified PCP.
-
Modified PCP is reducible to PCP.
-
Therefore, PCP is undecidable.
🧩 9. Key Properties
Property | PCP |
---|---|
Input | Two lists of strings |
Question | Is there a sequence of indices making concatenated strings equal? |
Output | YES/NO |
Decidable? | ❌ No |
Recognizable? | ✅ Yes (you can try sequences systematically, but may not halt) |
🧠 10. Intuitive Explanation of Undecidability
-
For some pairs of string lists, the “matching process” could go on forever — there’s no limit to how long the sequences could be.
-
So a Turing machine trying all possibilities might never halt.
-
Therefore, no general algorithm can guarantee to decide all cases.
Comments
Post a Comment