Problem odpowiedniości Posta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Ujednoznacznienie Zobacz też: Fencyklidyna, która również ma skrót PCP.

Problem odpowiedniości Posta (Post correspondence problem, w skrócie PCP) - jest to przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku[1].

Sformułowanie problemu[edytuj | edytuj kod]

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[edytuj | edytuj kod]

\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ść[edytuj | edytuj kod]

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

  1. E. L. Post. A variant of a recursively unsolvable problem. „Bull. Amer. Math. Soc”, 1946.