Postův korespondenční problém

Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. Redukce z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti.

Postův systém

Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:

$S=\{({\alpha }_1,{\beta }_1),\dots ,({\alpha }_k,{\beta }_k)\}$, kde $k\ge 1$ a ${\alpha }_i,{\beta }_i$ jsou řetězce nad nějakou abecedou, která obsahuje alespoň dva symboly (v případě abecedy s jedním symbolem je problém rozhodnutelný).

Řešením Postova systému je každá neprázdná posloupnost přirozených čísel I:

$I=\{i_1,\dots ,i_m\}$, kde $1\le i_j\le k$ a $m\ge 1$, pro kterou platí ${\alpha }_{i_1}\dots {\alpha }_{i_m}={\beta }_{i_1}\dots {\beta }_{i_m}$.

Postův korespondenční problém je pak rozhodnout, zda pro daný konkrétní Postův systém existuje řešení či nikoli.

Příklady

Systém $S_1=\{(b,bbb),(babbb,ba),(ba,a)\}$ má řešení $I=\{2,1,1,3\}$ (babbb b b ba = ba bbb bbb a).

Systém $S_2=\{(ab,abb),(a,ba),(b,bb)\}$ řešení nemá, jelikož délka $|{\alpha }_i|<|{\beta }_i|$, pro všechny $i$. Nikdy tedy nebude délka $|\alpha |$ rovna $|\beta |$.