berekenbaar

Berekenbaar is een term uit wiskunde en informatica die aangeeft dat een functie of probleem door een algoritme kan worden opgelost in eindige stappen. Een functie f: N^k -> N of f: {0,1}* -> {0,1}* is berekenbaar als er een eindige procedure bestaat die bij elke geldige invoer x resulteert in f(x) binnen een eindig aantal stappen en stopt. Een beslissingsprobleem is berekenbaar als er een algoritme bestaat dat voor elke invoer ja of nee beslist en stopt.

In de computabiliteitstheorie wordt vaak gesproken van berekenbare functies: deze zijn precies de functies die door een Turingmachine kunnen worden berekend, oftewel die door verschillende formele modellen zoals de lambda-calculus of primitieve recursieve functies kunnen worden beschreven. De Church-Turing-stelling stelt in het kort dat elke intuïtief berekenbare functie ook door zulke modellen kan worden berekend.

Voorbeelden van berekenbare functies zijn basale wiskundige bewerkingen zoals optelling en vermenigvuldiging, of complexere functies die altijd in eindig aantal stappen uitkomsten opleveren. Een beroemd tegenvoorbeeld uit de theoretische informatica is het Halting-probleem: er bestaat geen algoritme dat voor alle programma's en invoer beslist of het programma zal stoppen, dus dit probleem is niet berekenbaar.

Terminologie: in het Nederlands wordt doorgaans gesproken van 'berekenbaar' of, tegenovergestelde, 'onberekenbaar' of 'niet-berekenbaar'. Het begrip is fundamenteel in de computabiliteitstheorie en beïnvloedt zowel de theorie als de praktijk van algoritmen en probleemoplossing.