Post Correspondence Problem (PCP)
Post Correspondence Problem
Learn about the Post Correspondence Problem (PCP) and its importance in computability theory
Theory & Concepts
Definition:
The Post Correspondence Problem (PCP) is an undecidable problem in theoretical computer science, first introduced by Emil Post in 1946.
Key Points:
- Input: A finite set of domino pairs (x₁, y₁), (x₂, y₂), ..., (xₙ, yₙ), where each xᵢ and yᵢ is a non-empty string
- Question: Does there exist a sequence of indices i₁, i₂, ..., iₖ such that x_i₁x_i₂...x_iₖ = y_i₁y_i₂...y_iₖ?
- The general PCP is undecidable
- PCP is often used in reductions to prove other problems undecidable
Applications:
- Proving undecidability of various problems
- Computational linguistics
- Formal verification
University Guidelines
Syllabus Coverage:
- Theory of Computation
- Undecidability
- Computability Theory
Common Questions:
- Solve the given PCP instance
- Use PCP to prove undecidability of problem X
- Explain the relation between PCP and the Halting Problem
Exam Tips:
Algorithm Details
Algorithm Steps:
- 1Represent each domino pair as (top string, bottom string)
- 2Try different sequences of dominoes
- 3For each sequence, concatenate the top strings and bottom strings
- 4Check if the top and bottom concatenated strings match
- 5If they match, we have found a solution
PCP Instance
Limits the search depth to avoid excessive computation. Higher values may slow down the browser.
PCP Solution
Remember:
The Post Correspondence Problem is undecidable in general. This simulator uses a breadth-first search with a depth limit, so it may not find solutions that require more steps than the limit allows.
PCP Examples and Variants
Classic Example (Has Solution):
- (a, ab)
- (b, ca)
- (ca, a)
Solution: [1, 2, 3] produces "abca" on both top and bottom.
Simple Unsolvable Instance:
- (a, aa)
- (b, b)
No solution exists because any sequence will always have more a's on the bottom than on the top.
PCP Variants:
- Bounded PCP: Ask if there's a solution with at most k dominoes.
- Modified PCP: First and last dominoes are fixed.
- Marked PCP: All dominoes have special markers at certain positions.
- 2-PCP: Only two domino pairs are allowed (decidable!).
Complexity:
- General PCP: Undecidable
- Bounded PCP: NP-complete
- 2-PCP: Decidable in polynomial time
Undecidability Proof Sketch
The Post Correspondence Problem is proven undecidable by reduction from the Halting Problem for Turing machines.
Reduction Steps:
- Given a Turing machine M and input w, construct a PCP instance.
- Create domino pairs that encode:
- The initial configuration of M on input w
- Legal moves of M according to its transition function
- A way to check for the accepting state
- Design the encoding such that a solution exists if and only if M halts on input w.
- Since determining if M halts on w is undecidable, determining if the constructed PCP instance has a solution must also be undecidable.
Implications:
This reduction establishes the PCP as one of the simplest undecidable problems, which makes it a useful tool for proving other problems undecidable through further reductions.
Post Correspondence Problem Example Result
Input: "Domino pairs: (a, ab), (b, ca), (ca, a)"
Simulation Steps
Step-by-step execution trace