Mapping Reductions, Post Correspondence Problem & Chomsky Hierarchy

A mapping reduction (many-one reduction) reduces problem A to problem B (A ≤_m B) via a computable function f: \Sigma^ \to \Sigma^ such that for all w:

$w \in A \iff f(w) \in B$

Directional Consequences of A ≤_m B (Crucial GATE Logic):

1. If B is Decidable, then A is Decidable.

2. If A is Undecidable, then B is Undecidable.

3. If B is Recursively Enumerable (RE), then A is RE.

4. If A is not RE, then B is not RE.

GATE Exam Trap: If A is decidable, it tells us NOTHING about whether B is decidable! If B is undecidable, it tells us NOTHING about whether A is undecidable!

The Post Correspondence Problem (PCP):

Given two lists of strings over an alphabet \Sigma:

A = (x_1, x_2, ..., x_k) and B = (y_1, y_2, ..., y_k).

Does there exist an index sequence i_1, i_2, ..., i_m (m ≥ 1) such that:

$x_{i_1} x_{i_2} \cdots x_{i_m} = y_{i_1} y_{i_2} \cdots y_{i_m}$

- PCP is UNDECIDABLE for alphabet size |\Sigma| ≥ 2 and list length k ≥ 7.

- PCP over a unary alphabet (|\Sigma| = 1) is DECIDABLE!

- Modified PCP (MPCP), where the match must start with index 1 (i_1 = 1), is also UNDECIDABLE.

- PCP is the standard intermediate tool used to prove that CFG ambiguity and CFG equivalence are undecidable.