Posts korrespondanseproblem

Posts korrespondanseproblem er eit uavgjerbart beslutningsproblem innanføre informatikken og matematikken introdusert av Emil Post i 1946. Sagt på ein annan måte, det finst inga turingmaskin som vert sagt å avgjera problemet. Det verta ofte nytta i bevis for om eit problem er uavgjerbart eller ikkje, då det er enklare å jobba med enn andre uavgjerbare beslutningsproblem som til dømes stoppeproblemet.

Definisjon

Det finst fleire ulike definisjonar på problemet. Ein måte å sjå det på er følgjande.

La dataen for problemet vera to lister  ${\alpha }_1,\dots ,{\alpha }_N$ og  ${\beta }_1,\dots ,{\beta }_N$ av ord over alfabetet $A$ der $A$ inneheld minst to symbol. Ei løsning for dette problemet er ein sekvens av indeksar  $(i_k{)}_{1\le k\le K}$ der  $K\ge 1$ og  $1\le i_k\le N$ for alle k, sånn at

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

Posts korrespondanseproblem er å finna ut om ei slik løysing eksisterer i det heile.

Døme

For dei to listeneMal:Kol-start Mal:Kol-bryting

α1	α2	α3
a	ab	bba

β1	β2	β3
baa	aa	bb

Mal:Kol-slutt Vil ei løysing for dette problemet vera sekvensen (3,2,3,1) ettersom

${\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.$

Vidare vil alle repetisjonar av sekvensen òg vera ei løysing.

Ein annan enklare måte er òg å sjå på dette som dominobrikker. Mal:Kol-start Mal:Kol-bryting

αi

βi

Mal:Kol-slutt Løsninga kan dermed òg visualiserast enklare på følgjande måte, der strengen sett sammen av dei øvste grønne delane av dominobrikka er lik strengen sett sammen av dei nedste blå delane av dominobrikka. Mal:Kol-start Mal:Kol-bryting

bba

bb

i₁ = 3 Mal:Kol-bryting

ab

aa

i₂ = 2 Mal:Kol-bryting

bba

bb

i₃ = 3 Mal:Kol-bryting

a

baa

i₄ = 1 Mal:Kol-slutt

Litteratur

• Michael Sipser (2005). "A Simple Undecidable Problem". Introduction to the Theory of Computation (2nd eid.). 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.