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