Problem odpowiedniości Posta

Problem odpowiedniości Posta (ang. Post correspondence problem, PCP) – przykład nierozstrzygalnego problemu decyzyjnego. 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źć. W ogólnym przypadku nie można natomiast stwierdzić jego braku.