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.