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   og   av ord over alfabetet  der  inneheld minst to symbol. Ei løsning for dette problemet er ein sekvens av indeksar   der   og   for alle k, sånn at

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

 Døme 
For dei to listene

 α1 α2 α3aabbba

 β1 β2 β3baaaabb

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

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.
Kategori:Uavgjerbare problem