Decidabiliteit

Decidabiliteit is in de wiskunde en de theoretische informatica de eigenschap van een beslissingsprobleem dat er een algoritme bestaat dat op elke invoer in eindige tijd een definitief ja- of nee-antwoord geeft. Een beslissingsprobleem wordt gezien als een taal L ⊆ Σ*, en het doel is te bepalen of een invoer w tot L behoort. Het bijbehorende algoritme stopt altijd en geeft correct ja als w ∈ L en nee als w ∉ L.

Een probleem is decidabel als zo’n algoritme bestaat; ondecideerbaar (of onbeslist) betekent dat geen dergelijk algoritme bestaat. Een verwant begrip is semi-decideerbaar (semi-decideerbaar of recursief oplijstbaar): er bestaat een algoritme dat ja-instanties accepteert en stopt, maar bij nee-instanties mogelijk niet stopt.

Bekende resultaten: het halting-probleem is ondecideerbaar: er bestaat geen algoritme dat voor iedere Turing-machine en invoer bepaalt of de machine stopt. De geldigheidsproblematiek van de eerste-orde logica is eveneens ondecideerbaar. Aan de andere kant is Presburger-aritmetiek decidabel, terwijl volledige Peano-aritmetiek ondecideerbaar is.

Reductie wordt vaak gebruikt: als een bekend ondecideerbaar probleem kan worden gereduceerd naar een nieuw probleem, dan is ook dat nieuw ondecideerbaar. De Church-Turing-these koppelt decidabiliteit aan wat effectief berekenbaar is via algoritmen of Turing-machines, en vormt een fundament voor begrip van wat computabel is. Decidabiliteit heeft toepassing in automatische verificatie, formele redenering en het ontwerp van programmeertalen.