Het stopprobleem, ook bekend als het 'halting problem', is het beslissingsprobleem uit de wiskunde en informatica, om te bepalen of een algoritme bij een eindige invoer in een eindig aantal stappen eindigt of dat het eindeloos blijft doorgaan. Het is een bekend voorbeeld van een wiskundig probleem dat onbeslisbaar is, en een van de eerste als dusdanig herkende problemen. Dit werd in 1936 door Alan Turing bewezen.
Definitie Het stopprobleem is informeel gedefinieerd het volgende beslissingsprobleem: Gegeven een programma en een invoerwaarde , bepaal of met invoer na een eindig aantal stappen wel of niet stopt. Om het stopprobleem formeel te definiëren, moeten we afspreken wat we onder het begrip programma verstaan. Oorspronkelijk werd het stopprobleem voor turingmachines geformuleerd, maar analoog kan het ook voor andere turingvolledige formalismes worden gedefinieerd, zoals een programma in een willekeurige programmeertaal of een uitdrukking in de lambdacalculus.
De invoer van een turingmachine bestaat uit een rij symbolen, een tekenreeks. Om turingmachines als invoer voor andere turingmachines op te kunnen vatten, moeten we ze eerst coderen. We kunnen bijvoorbeeld alle Turingmachines op een rij zetten, en dan het volgnummer in deze rij als de code voor de turingmachine gebruiken. Als een code voor een turingmachine is, dan schrijven we voor de turingmachine die door gecodeerd wordt. Bovendien schrijven we voor de code van het paar . Het stopprobleem kan nu formeel als volgt worden gedefinieerd:
Beslissingsproblemen worden ook vaak gedefinieerd als de verzameling van positieve invoerwaardes, dus alternatief luidt de definitie van het stopprobleem:
Onbeslisbaarheid Alan Turing bewees in 1936 dat het stopprobleem onbeslisbaar is. Dat betekent dat er geen turingmachine bestaat die in alle gevallen correct beslist, of een turingmachine met een bepaalde invoerwaarde in een eindig aantal stappen stopt of niet.
Het was voor zijn bewijs, of beter gezegd voor het geven van een definitie van het concept 'algoritme', dat Turing het later beroemd geworden idee van de turingmachine bedacht.
Bronnen Elaine Rich, Automata, Computability and Complexity. Theory and Applications., 2008
Categorie:Paradox Categorie:Theoretische informatica