Posts korrespondanseproblem

Posts korrespondanseproblem er et uavgjørbart beslutningsproblem innenfor informatikken og matematikken introdusert av Emil Post i 1946. Sagt på en annen måte, det finnes inga turingmaskin som sies å avgjøre problemet. Det brukes ofte i beviser for uavgjørbarhet da det er enklere å jobbe med enn andre uavgjørbare beslutningsproblemer som for eksempel stoppeproblemet.

Definisjon

Det finnes flere ulike definisjoner på problemet. En måte å se det på er følgende.

La dataen for problemet være to lister  ${\alpha }_1,\dots ,{\alpha }_N$ og  ${\beta }_1,\dots ,{\beta }_N$ av ord over alfabetet $A$ hvor $A$ består av minst to symboler. Ei løsning for dette problemet er en sekvens av indekser  $(i_k{)}_{1\le k\le K}$ hvor  $K\ge 1$ og  $1\le i_k\le N$ for alle k, slik at

${\alpha }_{i_1}\dots {\alpha }_{i_K}={\beta }_{i_1}\dots {\beta }_{i_K}.$

Posts korrespondanseproblem er å finne ut om slik ei løsning eksisterer i det hele tatt.

Eksempel

For de to listeneMal:Col-begin Mal:Col-break

α1	α2	α3
a	ab	bba

β1	β2	β3
baa	aa	bb

Mal:Col-endVil ei løsning for dette problemet være sekvensen (3,2,3,1) fordi

${\alpha }_3{\alpha }_2{\alpha }_3{\alpha }_1=bba+ab+bba+a=bbaabbbaa=bb+aa+bb+baa={\beta }_3{\beta }_2{\beta }_3{\beta }_1.$

Videre vil alle repetisjoner av sekvensen også være ei løsning.

En annen enklere måte er også å se på dette som dominobrikker. Mal:Col-begin Mal:Col-break

αi

βi

Mal:Col-endLøsninga kan dermed også visualiseres enklere på følgende måte, hvor strengen satt sammen av de øvre grønne delene av dominobrikka er lik strengen satt sammen av de nedre blå delene av dominobrikka. Mal:Col-begin Mal:Col-break

bba

bb

i₁ = 3 Mal:Col-break

ab

aa

i₂ = 2 Mal:Col-break

bba

bb

i₃ = 3 Mal:Col-break

a

baa

i₄ = 1 Mal:Col-end

Litteratur

• Michael Sipser (2005). "A Simple Undecidable Problem". Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. side. 199–205. ISBN 0-534-95097-3.
• E. L. Post (1946). "A variant of a recursively unsolvable problem" (PDF). Bull. Amer. Math. Soc. 52.