Från Rilpedia

Stopproblemet (en The Halting Problem) är ett grundläggande beslutsproblem inom beräkningsbarhetsteorin som kan informellt 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.

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

Skisserat bevis

Börja med att välja ett programspråk; detta är ett sätt 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, måste det vara eftersom stoppar(t, t) svarade falskt, men det betyder att trassel(t) borde inte ha stoppat.
• 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, 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.