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},\ldots ,\alpha _{N}$ og  $\beta _{1},\ldots ,\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\leq k\leq K}$ hvor  $K\geq 1$ og  $1\leq i_{k}\leq N$ for alle k, slik at

$\alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.$

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

Eksempel

For de to listene

α1 α2 α3 a ab bba

β1 β2 β3 baa aa bb

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

αi βi

Lø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.

bba bb i1 = 3

ab aa i2 = 2

bba bb i3 = 3

a baa i4 = 1

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.