Problem odpowiedniości Posta
Z Wikipedii
Problem odpowiedniości Posta - jest to przykład nierozstrzygalnego problemu decyzyjnego, czyli takiego, dla którego nie istnieje program komputerowy, czy też algorytm go rozwiązujący. Został on przedstawiony przez Emila Leona Posta w 1946 roku.
[edytuj] Sformułowanie problemu
Niech Σ będzie pewnym alfabetem.
Rozważmy zbiór P par słów nad Σ
- , gdzie:
Problem: Czy dla danego P istnieje niepuste słowo (ciąg indeksów) takie, że jest nierozstrzygalny.
[edytuj] Przykład
Σ = {a,b}
P = { < aab,aa > , < b,bb > }
Rozwiązanie: ciąg indeksów 1,2, słowo: aabb
[edytuj] 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źć. Nie można natomiast stwierdzić jego braku.