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[endre | endre wikiteksten]
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[endre | endre wikiteksten]
For dei to listene
|
|
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.
|
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.
i1 = 3 |
i2 = 2 |
i3 = 3 |
i4 = 1 |
Litteratur[endre | endre wikiteksten]
- 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.