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 .
Zdroj
Poslední aktualizace obsahu: 2023-12-14 13:06:30
Zdroj: Wikipedia (autoři článku Postův korespondenční problém)
Licence textu: CC-BY-SA-3.0 Unported
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.