Halting-problemet
Halting-problemet er et problem inden for datalogi. Problemet består i at se på et computerprogram og finde ud af, om programmet vil køre for evigt eller ej. Vi siger, at et program "løser stopproblemet", hvis det kan se på et hvilket som helst andet program og fortælle, om det andet program vil køre for evigt eller ej.
For eksempel et program som dette:
while True: fortsætte;vil løbe i en evighed, men programmet
while False: fortsæt;stopper meget hurtigt.
Findes der et program, der løser problemet med stop? Det viser sig, at der ikke findes noget. Vi beviser dette ved at vise, at hvis der findes et program, der løser stopproblemet, så sker der noget umuligt. Så i øjeblikket vil vi lade som om, at der virkelig findes et program, der løser stopproblemet. Her er P en funktion, som evaluerer funktionen F (kaldet med argumentet I) og returnerer sandt, hvis den kører for evigt, og falsk ellers.
def P(F, I): hvis F(I) kører for evigt: return True; ellers: return False;P kan se på et hvilket som helst program og finde ud af, om det vil køre for evigt eller ej. Vi bruger P til at lave et nyt program, som vi kalder Q. Det Q gør er at se på et andet program og derefter besvare følgende spørgsmål: "Hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det så køre for evigt?". Vi kan lave Q, fordi vi har P. Alt vi skal gøre er at bede Q om at lave et nyt program, som er det gamle program, der kigger på sig selv, og derefter bruge P til at finde ud af, om det nye program kører for evigt eller ej.
def Q(F): return P(F, F);Nu laver vi et andet program R. R ser på et andet program og spørger Q om svaret på dette program. Hvis Q svarer "ja, hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det køre for evigt", så stopper R. Hvis Q svarer "nej, hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det ikke køre i al evighed", så går R ind i en uendelig løkke og kører i al evighed.
def R(F): if Q(F): return; //slutter ellers: while True: continue; //loop for evigtNu ser vi på, hvad der sker, hvis vi får R til at se på en kopi af sig selv. Der kan ske to ting: Den vil enten stoppe eller køre for evigt.
Hvis det at køre R og få det til at se på en kopi af sig selv ikke kører for evigt, så svarede Q: "Ja, hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det køre for evigt". Men Q sagde dette, da han kiggede på R selv. Så det, Q faktisk sagde, var: "ja, hvis vi kører R og får det til at se på en kopi af sig selv, vil det køre for evigt". Så: Hvis R, der kører på en kopi af sig selv, ikke kører for evigt, så kører det for evigt. Det er umuligt.
Hvis det at køre R og få det til at se på en kopi af sig selv kører for evigt, så svarede Q: "Nej, hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det ikke køre for evigt". Men Q sagde dette, da han kiggede på R selv. Så det, Q faktisk sagde, var: "Nej, hvis vi kører R og får det til at se på en kopi af sig selv, vil det ikke køre for evigt". Så: Hvis R kører på en kopi af sig selv og kører for evigt, så kører det ikke for evigt. Dette er også umuligt.
Uanset hvad der sker, får vi en umulig situation. Vi har gjort noget forkert, og vi skal finde ud af, hvad det var. De fleste af de ting, vi gjorde, var ikke forkerte. Vi kan ikke sige, at "det er forkert at lade et program se på en kopi af sig selv", eller at "det er forkert at se på, hvad et andet program sagde, og derefter gå ind i en løkke, hvis det sagde én ting, og stoppe, hvis det sagde noget andet". Det giver ikke mening at sige, at vi ikke må gøre disse ting. Det eneste, vi gjorde, som ser ud til at være forkert, er, at vi lod som om, at et program som P overhovedet eksisterer. Og da dette er det eneste, der kunne være forkert, og noget må være forkert, er det dette. Dette er beviset for, at et program som P ikke eksisterer. Der findes ikke noget program, der løser problemet med stop.
Dette bevis blev fundet af Alan Turing i 1936.
Spørgsmål og svar
Q: Hvad er Halting-problemet?
A: Halting-problemet er et problem inden for datalogi, hvor man ser på et computerprogram og bestemmer, om programmet vil køre for evigt eller ej.
Spørgsmål: Hvordan ved vi, om et program løser halting-problemet?
Svar: Vi siger, at et program "løser halting-problemet", hvis det kan se på et hvilket som helst andet program og fortælle, om det andet program vil køre for evigt eller ej.
Spørgsmål: Kan man på nogen måde bevise, at der ikke findes et sådant program?
A: Ja, ved at vise, at hvis der fandtes et sådant program, ville der ske noget umuligt. Dette bevis blev fundet af Alan Turing i 1936.
Spørgsmål: Hvad gør P?
Svar: P er en funktion, der evaluerer en anden funktion F (kaldet med argumentet I) og returnerer sandt, hvis den kører for evigt, og falsk ellers.
Spørgsmål: Hvad gør Q?
Svar: Q ser på et andet program og besvarer derefter spørgsmålet om, hvorvidt det at køre det samme program på sig selv vil resultere i en uendelig sløjfe eller ej. Det gør det ved at bruge P til at foretage en evaluering af den givne funktion F.
Spørgsmål: Hvad gør R?
Svar: R ser på et andet program og beder Q om sit svar på dette program. Hvis Q svarer "ja, hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det køre for evigt", stopper R; hvis Q derimod svarer "nej, hvis vi kører dette program og får det til at se på en kopi af sig selv, vil det ikke køre for evigt", går R ind i en uendelig løkke og kører for evigt.
Spørgsmål: Hvad sker der, når man får R til at kigge på sig selv?
Svar: Der kan ske to ting - enten stopper R eller kører for evigt - men begge resultater er umulige i henhold til det, der er blevet bevist om, at programmer som P ikke eksisterer, så der må være gået noget galt et eller andet sted på vejen op til at få R til at se på sig selv.
