Correspondentieprobleem van Post

Het correspondentieprobleem van Post (Engels: Post Correspondence Problem) is een onbeslisbaar probleem uit de theoretische informatica dat in 1946 door Emil Leon Post werd geformuleerd. Het wordt vaak gebruikt om de onbeslisbaarheid van andere problemen te bewijzen. Het probleem is ook bekend onder zijn (Engelse) afkorting: PCP.

Informele definitie

Gegeven is een aantal stenen (een soort dominostenen) waarop boven en onder een rijtje letters staat. Het is de bedoeling de stenen zo aan elkaar te leggen, dat boven en onder hetzelfde woord staat. Hierbij hoeven niet alle stenen gebruikt te worden, en mogen stenen bovendien meerdere keren worden gebruikt.

Beschouw bijvoorbeeld de volgende stenen:

a aaa

abaaa ab

ab b

Een oplossing voor het bovenstaande correspondentieprobleem is:

abaaa	a	a	ab
ab	aaa	aaa	b

waar zowel boven als onder het woord "abaaaaaab" staat.

Niet alle instanties van PCP hebben een oplossing. Dat is bijvoorbeeld het geval in het volgende voorbeeld, omdat er geen enkele steen geschikt is om als meest linkse steen te dienen:

aa b

bba babb

ab aa

Formele definitie

Laat een eindige verzameling $\Sigma$ (het alfabet) gegeven zijn. Een instantie van het PCP is een eindige rij $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$, waarbij $(x_{i},y_{i})\in \Sigma ^{*}\times \Sigma ^{*}$ voor alle $0<i\leq n$. Een oplossing voor een PCP-instantie is een eindige rij van indices, $i_{1},\ldots ,i_{k}$, zodat

$x_{i_{1}}\ldots x_{i_{k}}=y_{i_{1}}\ldots y_{i_{k}}$

Het eerste voorbeeld hierboven wordt bijvoorbeeld gerepresenteerd door de rij ${\text{(a,aaa), (abaaa,ab), (ab,b)}}$. Een oplossing voor deze instantie is 2,1,1,3, omdat $x_{2}x_{1}x_{1}x_{3}={\text{abaaaaaab}}=y_{2}y_{1}y_{1}y_{3}$.

Onbeslisbaarheid

De vraag of een bepaalde PCP-instantie een oplossing heeft is niet beslisbaar. Dat betekent dat er geen algoritme bestaat dat in alle gevallen in eindige tijd kan beslissen, of een gegeven PCP-instantie een oplossing heeft. Dat kan bewezen worden door het stopprobleem naar PCP te reduceren. Hiervoor wordt uit een turingmachine een instantie van het PCP gegenereerd, die precies dan een oplossing heeft als de oorspronkelijke turingmachine termineert. Door deze reductie zou uit de beslisbaarheid van het PCP de beslisbaarheid van het stopprobleem volgen, maar aangezien het stopprobleem niet beslisbaar is, moet het PCP ook onbeslisbaar zijn.

Literatuur

• E.L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52. 1946.
• Michael Sipser. Introduction to the Theory of Computation, 3rd Ed. Cengage Learning, 2013.