Posts korrespondanseproblem

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

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[rediger | rediger kilde]

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[rediger | rediger kilde]

For de to listene

α1 α2 α3
a ab bba
β1 β2 β3
baa aa bb

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[rediger | rediger kilde]