Problem odpowiedniości Posta

Problem odpowiedniości Posta (Post correspondence problem, w skrócie PCP) - jest to przykład nierozstrzygalnego problemu decyzyjnego, czyli takiego, dla którego nie istnieje program komputerowy, czy też algorytm go rozwiązujący. Został on przedstawiony przez Emila Leona Posta w 1946 roku.

Sformułowanie problemu

Niech $\Sigma$ będzie pewnym alfabetem. Rozważmy zbiór $P$ par słów nad $\Sigma$

$P = \{ ( l_1,r_1), (l_2,r_2), \ldots, (l_k,r_k) \}$,   gdzie: $l_i,r_i \in \Sigma^* \ (1 \leqslant i \leqslant k)$

Problem: Czy dla danego $P$ istnieje niepuste słowo (ciąg indeksów) $w_1 w_2 \dots w_s \in \{ 1, 2, \ldots, k \}$ takie, że $l_{w_1} l_{w_2} \ldots l_{w_s} = r_{w_1} r_{w_2} \ldots r_{w_s}$?

Przykład

$\Sigma = \{ a, b \}$

$P = \{ (l_1, r_1), (l_2, r_2) \}$

$l_1 = aab,\ r_1 = aa,\ l_2 = b,\ r_2 = bb$

Rozwiązanie: ciąg indeksów $1, 2$, słowo: $aabb$

Rekurencyjna przeliczalność

Problem odpowiedniości Posta jest problemem rekurencyjnie przeliczalnym, co oznacza, że jeśli istnieje rozwiązanie to jesteśmy w stanie je znaleźć. Nie można natomiast stwierdzić jego braku.