Correspondentieprobleem van Post

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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[bewerken]

Laat een eindige verzameling Σ (het alfabet) gegeven zijn. Een instantie van het PCP is een eindige rij (x1,y1),...,(xn,yn), waarbij xi, yi ∈ Σ* voor alle 0 < in. Een oplossing voor een PCP-instantie is een eindige rij van indices, i1,...,ik, zodat

x_{i_1}\cdots x_{i_k} = y_{i_1}\cdots y_{i_k}.

Het eerste voorbeeld hierboven wordt bijvoorbeeld gerepresenteert door de rij (a,aaa), (abaaa,ab), (ab,b). Een oplossing voor deze instantie is 2,1,1,3, omdat x2x1x1x3 = abaaaaaab = y2y1y1y3.

Onbeslisbaarheid[bewerken]

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[bewerken]

  • 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.