haltprobleem

Het halttprobleem, ook wel de halting-probleem genoemd, is in de informatica het beslissingsprobleem waarbij wordt gevraagd of een gegeven programma met een bepaalde invoer ooit zal stoppen met draaien of uiteindelijk in een oneindige lus blijft hangen. Het vormt een kernprobleem binnen de computabiliteitstheorie.

Het haltthema werd in 1936 geformuleerd door Alan Turing als onderdeel van zijn onderzoek naar de mogelijkheden en grenzen van mechanische berekeningen. In een technische modelering wordt vaak gebruikgemaakt van Turingmachines, maar het haltthema geldt voor vrijwel elk formeel model van berekening. Het centrale resultaat is dat er geen algemeen algoritme bestaat dat voor alle programma‑invoerparena beslist of het programma stopt.

De undecidabiliteit van het halttprobleem wordt meestal aangetoond via een diagonalisatie-argument. Stel dat er een decider bestaat die voor elk programma P en invoer x kan bepalen of P stopt op x. Dan kan men een programma D construeren dat op invoer y diens eigen gedrag bekijkt: als de decider zegt dat D stopt op D, dan draait D oneindig; anders stopt D. Door D(D) te voeren ontstaat een contradictie, wat aantoont dat zo’n decider niet kan bestaan. Uit dit gevolg volgt dat het halttprobleem in het algemeen onverwerkbaar is.

Toch is halting wel semidecidabel (recursief oplijstbaar): er bestaat een algoritme dat ja kan zeggen zodra het programma daadwerkelijk stopt, maar het programma kan blijven draaien als het niet stopt. Dit heeft praktische implicaties voor programmeeranalysis en formele verificatie: algemene termination-proofing is onmogelijk, maar onder vereisten of beperkingen kunnen terminationtests wel werken.

Zie ook: Turingmachine, computabiliteit en Rice’s theorem.