Brontekst bekijken van Correspondentieprobleem van Post

Het '''correspondentieprobleem van Post''' (Engels: ''Post Correspondence Problem'') is een [[berekenbaarheid|onbeslisbaar]] [[beslissingsprobleem|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:
{|
|-
|
{| class="wikitable"
|align="center" width="50"| a
|-
|align="center" width="50"| aaa
|}
|
{| class="wikitable"
|align="center" width="50"| abaaa
|-
|align="center" width="50"| ab
|}
|
{| class="wikitable"
|align="center" width="50"| ab
|-
|align="center" width="50"| b
|}
|}

Een oplossing voor het bovenstaande correspondentieprobleem is:
{| class="wikitable"
|align="center" width="50"| abaaa
|align="center" width="50"| a
|align="center" width="50"| a
|align="center" width="50"| ab
|-
|align="center" width="50"| ab
|align="center" width="50"| aaa
|align="center" width="50"| aaa
|align="center" width="50"| 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:

{|
|-
|
{| class="wikitable"
|align="center" width="50"| aa
|-
|align="center" width="50"| b
|}
|
{| class="wikitable"
|align="center" width="50"| bba
|-
|align="center" width="50"| babb
|}
|
{| class="wikitable"
|align="center" width="50"| ab
|-
|align="center" width="50"| aa
|}
|}

== Formele definitie ==
Laat een eindige verzameling <math>\Sigma</math> (het alfabet) gegeven zijn. Een instantie van het PCP is een eindige rij <math>(x_1,y_1),\ldots, (x_n,y_n)</math>, waarbij <math>(x_i,y_i)\in \Sigma^*\times\Sigma^*</math> voor alle <math>0 < i \le n</math>. Een oplossing voor een PCP-instantie is een eindige rij van indices, <math>i_1,\ldots, i_k</math>, zodat 
:<math>x_{i_1}\ldots x_{i_k} = y_{i_1}\ldots y_{i_k}</math>

Het eerste voorbeeld hierboven wordt bijvoorbeeld gerepresenteerd door de rij <math>\text{(a,aaa), (abaaa,ab), (ab,b)}</math>. Een oplossing voor deze instantie is 2,1,1,3, omdat 
<math>x_2x_1x_1x_3=\text{abaaaaaab}=y_2y_1y_1y_3</math>.

== Onbeslisbaarheid ==
De vraag of een bepaalde PCP-instantie een oplossing heeft is niet [[berekenbaarheid|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.

[[Categorie:Theoretische informatica]]