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 Σ:

A=[a1,a2,a3,...,an]A = [a_1, a_2, a_3, ..., a_n]B=[b1,b2,b3,...,bn]B = [b_1, b_2, b_3, ..., b_n]

Each aia_i and bib_iis a string over the alphabet Σ.


🎯 3. The Goal

You must determine whether there exists a non-empty sequence of indices

i1,i2,i3,...,ik(1ijn)i_1, i_2, i_3, ..., i_k \quad (1 \leq i_j \leq n)

such that when you concatenate the strings from both lists in that order,
the two results are equal.

That is:

ai1ai2ai3...aik=bi1bi2bi3...bika_{i_1}a_{i_2}a_{i_3}...a_{i_k} = b_{i_1}b_{i_2}b_{i_3}...b_{i_k}

Such a sequence is called a match or solution to the PCP instance.


🧮 4. Example

Let’s take an example over Σ = {0, 1}.

    
iaia_ibib_i
1        110
2011

Now, let’s check:

If we pick sequence i1=1,i2=2,i3=2i_1 = 1, i_2 = 2, i_3 = 2:

a1a2a2=1 01 01=10101a_{1}a_{2}a_{2} = 1\ 01\ 01 = 10101
b1b2b2=10 1 1=1011b_{1}b_{2}b_{2} = 10\ 1\ 1 = 1011

❌ Not equal.

But if we pick i1=1,i2=2:

a1a2=1 01=101a_1a_2 = 1\ 01 = 101
b1b2=10 1=101b_1b_2 = 10\ 1 = 101

✅ 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 A=[a1,...,an] and B=[b1,...,bn]B = [b_1, ..., b_n]
does there exist a non-empty sequence of indices such that
ai1ai2...aik=bi1bi2...bika_{i_1}a_{i_2}...a_{i_k} = b_{i_1}b_{i_2}...b_{i_k}


🚫 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 MPCPM_{PCP} 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:

q101q210q_1 0 1 q_2 1 0

can be represented as a string like:

001q210001q2 10

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

  1. Encode each transition of the Turing machine MM as a pair of strings in PCP.

  2. Each pair represents one possible move (reading, writing, moving head, changing state).

  3. Matching in PCP corresponds to valid sequences of transitions in the Turing machine.

  4. 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,

PCP is undecidable.\text{PCP is undecidable.}

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 (a1,b1)(a_1, b_1).

  • 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

  1. Halting Problem is undecidable.

  2. Halting Problem is reducible to Modified PCP.

  3. Modified PCP is reducible to PCP.

  4. Therefore, PCP is undecidable.


🧩 9. Key Properties

PropertyPCP
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

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

Non deterministic Finite Automata NFA

Formal Definition - Turing Machine