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 .
Kategorie:Vyčíslitelnost Kategorie:Nerozhodnutelné problémy