Problem odpowiedniości Posta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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[edytuj]

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

,   gdzie:

Problem: Czy dla danego istnieje niepuste słowo (ciąg indeksów) takie, że ?

Przykład[edytuj]

Rozwiązanie: ciąg indeksów , słowo:

Rekurencyjna przeliczalność[edytuj]

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.