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 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
Rozwiązanie: ciąg indeksów słowo:
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
- ↑ E.L. Post. A variant of a recursively unsolvable problem. „Bull. Amer. Math. Soc”, 1946.