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ů:

${\displaystyle S=\{(\alpha _{1},\beta _{1}),\,\ldots ,\,(\alpha _{k},\beta _{k})\}}$, kde ${\displaystyle k\geq 1}$ a ${\displaystyle \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:

${\displaystyle I=\{i_{1},\,\ldots ,\,i_{m}\}}$, kde ${\displaystyle 1\leq i_{j}\leq k}$ a ${\displaystyle m\geq 1}$, pro kterou platí ${\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{m}}=\beta _{i_{1}}\ldots \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 ${\displaystyle S_{1}=\{(b,bbb),\,(babbb,ba),\,(ba,a)\}}$ má řešení ${\displaystyle I=\{2,\,1,\,1,\,3\}}$ (babbb b b ba = ba bbb bbb a).

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