onberekenbare

Onberekenbare is een term uit de wiskunde en informatica die wordt gebruikt om aan te geven dat iets niet door een algemeen algoritme kan worden berekend. Concreet betekent onberekenbaar dat er geen procedure bestaat die voor alle geldige invoer in finite tijd een exacte uitkomst geeft. Het begrip staat centraal in de computabiliteitstheorie en contrasteert met berekenbaar ( computable), waarbij een algoritme of berekeningsprocedure bestaat.

In deze context wordt vaak gesproken over berekenbaarheid door een Turingmachine of een equivalente formele definitie van algoritme. Een object kan onberekenbaar zijn als er geen algoritmische methode bestaat die het beschreven resultaat voor alle gevallen oplevert. Dit onderscheid is fundamenteel voor de studie van wat wiskundig gezien berekenbaar is en wat niet.

Klassieke voorbeelden illustreren het idee. Het halting-probleem is onberekenbaar: er bestaat geen algorithme dat voor elk willekeurig programma en invoer correct beslist of het programma zal stoppen. Andere voorbeelden zijn onberekenbare getallen, zoals Chaitin’s Omega, en onberekenbare functies zoals de Busy Beaver-functie, die sneller groeit dan elke berekenbare functie. In de realiteit betekent dit dat bijna alle reële getallen onberekenbaar zijn in de zin dat ze niet volledig door een algoritme kunnen worden beschreven of bepaald.

Zie ook: berekenbaarheid, onbeslisbaar, Turingmachine, algoritme, computabiliteit.