Problem odpowiedniości Posta () – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku.
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
Kategoria:Teoria obliczeń