Problem odpowiedniości Posta

Szablon:Inne znaczenia Problem odpowiedniości Posta (Szablon:Ang.) – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku.

Sformułowanie problemu

Niech $\mathrm{\Sigma }$ będzie pewnym alfabetem. Rozważmy zbiór $P$ par słów nad $\mathrm{\Sigma }$

$P=\{(l_1,r_1),(l_2,r_2),\dots ,(l_k,r_k)\},$   gdzie: $l_i,r_i\in {\mathrm{\Sigma }}^{*}(1⩽i⩽k).$

Problem: Czy dla danego $P$ istnieje niepuste słowo (ciąg indeksów) $w_1{w}_2\dots w_s\in \{1,2,\dots ,k\}$ takie, że $l_{w_1}{l}_{w_2}\dots l_{w_s}=r_{w_1}{r}_{w_2}\dots r_{w_s}$?

Przykład

$\mathrm{\Sigma }=\{a,b\}$

$P=\{(l_1,r_1),(l_2,r_2)\}$

$l_1=aab,r_1=aa,l_2=b,r_2=bb$

Rozwiązanie: ciąg indeksów $1,2,$ słowo: $aabb$

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.