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