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

, kde a 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:

, kde a , pro kterou platí .

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 má řešení (babbb b b ba = ba bbb bbb a).
Systém řešení nemá, jelikož délka , pro všechny . Nikdy tedy nebude délka rovna .