Stopprobleem

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 bewezen door Alan Turing in 1936.

Definitie

Het stopprobleem is informeel gedefinieerd het volgende beslissingsprobleem:

Gegeven een programma $M$ en een invoerwaarde $x$, bepaal of $M$ met invoer $x$ 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.

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, of programmeren. We kunnen bijvoorbeeld alle Turingmachines op een rij zetten, en dan het volgnummer in deze rij als de code voor de turingmachine gebruiken. Als $w$ een code voor een turingmachine is, dan schrijven we $M_w$ voor de turingmachine die door $w$ gecodeerd wordt. Bovendien schrijven we $⟨x,y⟩$ voor de code van het paar $(x,y)$. Het stopprobleem kan nu formeel als volgt worden gedefinieerd:

$h(⟨w,x⟩)=\{\begin{array}{cc}1& \text{als turingmachine }{M}_w\text{ stopt in een eindig aantal stappen met }x\text{ als invoer}\\ 0& \text{anders}\end{array}$

Beslissingsproblemen worden ook vaak gedefinieerd als de verzameling van positieve invoerwaardes, dus alternatief luidt de definitie van het stopprobleem:

$H=\{⟨w,x⟩\mid \text{Turingmachine }{M}_w\text{ stopt in een eindig aantal stappen met }x\text{ als invoer}\}$

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 algoritme, dat Turing het later beroemd geworden idee van de turingmachine bedacht.

Bronnen

• Sjabloon:En Elaine Rich, Automata, Computability and Complexity. Theory and Applications., 2008