Stopproblemet

Halting-problemet är ett problem inom datavetenskap. Problemet består i att titta på ett datorprogram och ta reda på om programmet kommer att köras för evigt eller inte. Vi säger att ett program "löser stoppproblemet" om det kan titta på vilket annat program som helst och avgöra om det andra programmet kommer att löpa för evigt eller inte.

Till exempel ett program som detta:

while True: fortsätt;

kommer att gå i en evig slinga, men programmet

while False: fortsätt;

stannar mycket snabbt.

Finns det ett program som löser problemet med stopp? Det visar sig att det inte finns något. Vi bevisar detta genom att visa att om det finns ett program som löser stoppproblemet så händer något omöjligt. Så för tillfället kommer vi att agera som om det verkligen finns ett program som löser stoppproblemet. Här är P en funktion som utvärderar funktionen F (anropad med argumentet I) och returnerar sant om den pågår i evighet och falskt annars.

def P(F, I): om F(I) löper för evigt: returnera True; annars: returnera False;

P kan titta på vilket program som helst och ta reda på om det kommer att köras för evigt eller inte. Vi använder P för att skapa ett nytt program som vi kallar Q. Vad Q gör är att titta på ett annat program och sedan besvara följande fråga: "Om vi kör det här programmet och låter det titta på en kopia av sig självt, kommer det då att köras för evigt?". Vi kan göra Q eftersom vi har P. Allt vi behöver göra är att be Q skapa ett nytt program som är det gamla programmet som tittar på sig självt, och sedan använda P för att ta reda på om det nya programmet körs för evigt eller inte.

def Q(F): återger P(F, F);

Nu skapar vi ett annat program R. R tittar på ett annat program och frågar Q om svaret på det programmet. Om Q svarar "ja, om vi kör det här programmet och låter det titta på en kopia av sig själv kommer det att köras för evigt", slutar R. Om Q svarar "nej, om vi kör det här programmet och låter det titta på en kopia av sig självt kommer det inte att köras för evigt", går R in i en oändlig slinga och körs för evigt.

def R(F): if Q(F): return; //avsluta annars: while True: continue; //loop forever

Nu tittar vi på vad som händer om vi låter R titta på en kopia av sig själv. Två saker kan hända: den kommer antingen att stanna eller köra för evigt.

Om det inte går att köra R och få det att titta på en kopia av sig självt för evigt, svarade Q "ja, om vi kör det här programmet och får det att titta på en kopia av sig självt kommer det att gå för evigt". Men Q sa detta när han tittade på R själv. Så vad Q faktiskt sa är: "Ja, om vi kör R och får det att titta på en kopia av sig själv kommer det att köras för evigt". Så: Om R som körs på en kopia av sig själv inte körs för evigt, så körs det för evigt. Detta är omöjligt.

Om det går i evighet att köra R och låta det titta på en kopia av sig själv, svarade Q: "Nej, om vi kör det här programmet och låter det titta på en kopia av sig själv kommer det inte att gå i evighet". Men Q sa detta när han tittade på R själv. Så vad Q faktiskt sa är: "Nej, om vi kör R och får det att titta på en kopia av sig själv kommer det inte att köras för evigt". Så: Om R körs på en kopia av sig själv och körs för evigt, så körs det inte för evigt. Detta är också omöjligt.

Oavsett vad som händer får vi en omöjlig situation. Vi har gjort något fel, och vi måste ta reda på vad det var. De flesta av de saker vi gjorde var inte fel. Vi kan inte säga att "det är fel att låta ett program titta på en kopia av sig självt", eller att "det är fel att titta på vad ett annat program sa och sedan gå in i en slinga om det sa en sak och sluta om det sa en annan sak". Det är inte meningsfullt att säga att vi inte får göra dessa saker. Det enda vi gjorde som ser ut att kunna vara fel är att vi låtsades att ett program som P överhuvudtaget existerar. Och eftersom detta är det enda som skulle kunna vara fel, och något måste vara fel, är det detta. Detta är beviset för att ett program som P inte existerar. Det finns inget program som löser stoppproblemet.

Detta bevis hittades av Alan Turing 1936.

Frågor och svar

F: Vad är Halting-problemet?

S: Halting-problemet är ett problem inom datavetenskap där man tittar på ett datorprogram och bestämmer om programmet kommer att köras för evigt eller inte.

F: Hur vet vi om ett program löser haltingproblemet?

S: Vi säger att ett program "löser haltingproblemet" om det kan titta på vilket annat program som helst och avgöra om det andra programmet kommer att köras för evigt eller inte.

F: Finns det ett sätt att bevisa att det inte finns något sådant program?

S: Ja, genom att visa att om det fanns ett sådant program skulle något omöjligt hända. Detta bevis hittades av Alan Turing 1936.

Fråga: Vad gör P?

S: P är en funktion som utvärderar en annan funktion F (som kallas med argumentet I) och som returnerar sant om den löper för evigt och falskt i annat fall.

Fråga: Vad gör Q?

S: Q tittar på ett annat program och svarar sedan på frågan om huruvida det kommer att resultera i en oändlig slinga om samma program körs på sig självt eller inte. Det gör det genom att använda P för att göra en utvärdering av den givna funktionen F.

F: Vad gör R?

Svar: R tittar på ett annat program och frågar Q om dess svar på just det programmet. Om Q svarar "ja, om vi kör det här programmet och låter det titta på en kopia av sig självt kommer det att löpa i evighet", slutar R. Om Q däremot svarar "nej, om vi kör det här programmet och låter det titta på en kopia av sig självt kommer det inte att löpa i evighet", går R in i en oändlig slinga och löper i evighet.

Fråga: Vad händer när du får R att titta på sig själv?

Svar: Två saker kan hända - antingen slutar R eller så körs det i all evighet - men båda resultaten är omöjliga enligt vad som har bevisats om att program som P inte existerar, så något måste ha gått fel någonstans på vägen fram till att R fick titta på sig själv.