berekenbare

Berekenbare is een bijvoeglijk naamwoord in het Nederlands, afgeleid van berekenen, en betekent dat iets kan worden berekend of vastgesteld met een vaste, eindige procedure. Het wordt gebruikt in wiskunde, informatica en het dagelijks taalgebruik om aan te geven dat een waarde, functie of grootheid theoretisch of praktisch kan worden bepaald via een algoritme of meetmethode. In het Engels wordt vaak het woord computable gebruikt.

In de wiskunde verwijst berekenbaar meestal naar functies of getallen waarvoor een algoritme bestaat dat bij elke geldige invoer een eindige stap uitvoert en de juiste uitkomst oplevert. Een functie f: N -> N is berekenbaar als er een procedure (of Turing-machine) is die f(n) oplevert en stopt. In de context van reële getallen spreekt men van berekenbare getallen wanneer er een algoritme is dat voor elke gewenste precisie een decimale of binaire benadering van de waarde kan leveren.

Veel voorkomende voorbeelden zijn polynomiële of rationele functies en veel bekende constanten zoals π en e, die berekenbaar blijven dankzij algoritmen. Niet-berekenbare getallen bestaan in theorie: er zijn reële getallen waarvoor geen algoritme de exacte waarde kan produceren. Het onderscheid tussen berekenbaar en niet-berekenbaar is fundamenteel in de theorie van berekenbaarheid en heeft invloed op wat meetbaar of te simuleren is.