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