Problem odpowiedniości Posta

Zobacz też: Fencyklidyna, która również ma skrót PCP.

Problem odpowiedniości Posta (ang. Post correspondence problem, PCP) – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku^[1].

Sformułowanie problemu

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

${\displaystyle P=\{(l_{1},r_{1}),(l_{2},r_{2}),\dots ,(l_{k},r_{k})\},}$   gdzie: ${\displaystyle l_{i},r_{i}\in \Sigma ^{*}\ (1\leqslant i\leqslant k).}$

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

Przykład

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

${\displaystyle P=\{(l_{1},r_{1}),(l_{2},r_{2})\}}$

${\displaystyle l_{1}=aab,\ r_{1}=aa,\ l_{2}=b,\ r_{2}=bb}$

Rozwiązanie: ciąg indeksów ${\displaystyle 1,2,}$ słowo: ${\displaystyle 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.

Przypisy