haltingfunctie

Haltingfunctie is een term uit de computabiliteitstheorie die verwijst naar de functie die aangeeft of een programma op een gegeven invoer eindigt. In de formalisme wordt vaak gesproken over de haltingset K = { ⟨programma, invoer⟩ | het programma stopt op die invoer }. De haltingfunctie is daarmee meestal een partiale functie: H(p, x) is gedefinieerd en gelijk aan 1 als p stopt op x, maar ongedefinieerd als p op x niet stopt. Soms wordt een ge-totaliseerde variant geformuleerd die in dat geval 0 teruggeeft, maar de klassieke interpretatie beschouwt H als partial.

Onbepaalbaarheid van de haltingfunctie is een fundamenteel resultaat: er bestaat geen algorithme dat voor elk paar (p, x) beslist of p stopt op x. Dit werd aangetoond door Alan Turing in 1936 door middel van een diagonaliteitsargument. De conclusie is het haltingprobleem undecideerbaar: er bestaat geen algemeen programma dat altijd ja of nee kan geven over stoppen voor alle mogelijke programma’s en invoeren.

Hoewel de haltingfunctie niet decidable is, is de haltingset wel semideelbaar (recursief opeenvolgend): er bestaat een Turingmachine die halt en 1 teruggeeft voor paren die stoppen, maar geen machine die altijd correct antwoordeert voor alle paren. Deze eigenschap maakt K recursief opeenvolgend maar niet decidabel.

Betekenis en toepassingen: het is een sleutelbegrip bij bewijsvoering over onbeslisbaarheid van problemen en bij redeneringen over terminateerbaarheid. In de praktijk probeert men termination analysis en andere statische analyses over- of onderschattende uitspraken te doen over stoppen, aangezien een volstrekte beslissing onhaalbaar is in het algemeen.