Postův korespondenční problém
Z Wikipedie, otevřené encyklopedie
Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Redukce z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti.
[editovat] Postův systém
Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:
- , kde a αi,βi jsou řetězce nad nějakou abecedou.
Ř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 zní: Existuje pro daný Postův systém řešení?
- Příklad
Systém má řešení : babbb b b ba = ba bbb bbb a
.
Systém řešení nemá.