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   og   av ord over alfabetet  hvor  består av minst to symboler. Ei løsning for dette problemet er en sekvens av indekser   hvor   og   for alle k, slik at

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

 Eksempel 
For de to listene

 α1 α2 α3aabbba

 β1 β2 β3baaaabb
Vil ei løsning for dette problemet være sekvensen (3,2,3,1) fordi

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.

Kategori:Uavgjørbare problemer