Problem odpowiedniości Posta
Wygląd
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.