Stopproblemet

Stopproblemet eller haltproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som informellt kan beskrivas så här:

Med en given beskrivning av ett program och dess indata, bestäm om programmet, när det utförs med indatat, någonsin stoppar (slutför beräkningen). Alternativet är att det fortsätter i evighet utan avbrott.

En annan beskrivning av problemet lyder:

Är det möjligt att inom ändlig tidsrymd med något program avgöra om ett godtyckligt program stannar för godtyckliga indata?

Alan Turing visade 1936 att en allmän algoritm för att lösa stopproblemet för samtliga (program, indata)-par inte kan existera. Man säger att stopproblemet inte är rekursivt lösbart.

Skisserat bevis

Börja med att välja ett programspråk; det är standard att förknippa varje program med (åtminstone) en teckensträng (programtexten i det valda programspråket). Anta att någon hävdar att man har funnit en algoritm stoppar(p, i) som svarar sant om p är programtexten till ett program som stoppar när det får i som indata, och falskt om det inte stoppar. Skriv då ett annat program trassel som använder stoppar som en subrutin:

   function trassel(string s)
       if stoppar(s, s) == false
           return true
       else
           snurra i evighet

Det här programmet tar en sträng s som ett argument och anropar stoppar med s som både programtext och indata till programmet. Om stoppar svarar falskt så svarar trassel sant, annars hamnar trassel i en oändlig slinga. Eftersom alla program kan uttryckas som strängar, finns det en sträng t som motsvarar trassel. Vad händer om vi försöker anropa trassel(t)?

• Om trassel(t) stoppar så betyder det att stoppar(t, t) svarade falskt, vilket i sin tur betyder att trassel(t) inte borde ha stoppat. En paradox.
• Om trassel(t) snurrar i evighet, är det antingen därför att stoppar också snurrar i evighet, eller därför att stoppar svarade sant. Detta betyder antingen att stoppar inte fungerar för ett giltigt program (vilket strider mot antagandet), eller att trassel(t) borde ha stannat.

I båda fallen dras slutsatsen att stoppar inte gav ett korrekt svar, i motsats till det ursprungliga antagandet. Eftersom resonemanget gäller för vilket program som helst som någon kan föreslå som en lösning till stopproblemet, finns det ingen lösning. Stopproblemet är därmed oavgörbart.