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  ${\displaystyle \alpha _{1},\ldots ,\alpha _{N}}$ og  ${\displaystyle \beta _{1},\ldots ,\beta _{N}}$ av ord over alfabetet ${\displaystyle A}$ der ${\displaystyle A}$ inneheld minst to symbol. Ei løsning for dette problemet er ein sekvens av indeksar  ${\displaystyle (i_{k})_{1\leq k\leq K}}$ der  ${\displaystyle K\geq 1}$ og  ${\displaystyle 1\leq i_{k}\leq N}$ for alle k, sånn at

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

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

Døme

For dei to listene

α1 α2 α3 a ab bba

β1 β2 β3 baa aa bb

Vil ei løysing for dette problemet vera sekvensen (3,2,3,1) ettersom

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

αi βi

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.

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