Problem odpowiedniości Posta

Z Wikipedii

Problem odpowiedniości Posta (Post correspondence problem, w skrócie PCP) - 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.