Onberekenbare functies: de grenzen van de berekening begrijpen

In de berekenbaarheidstheorie wordt een functie onberekenbaar genoemd als deze door geen enkel algoritme kan worden berekend. Met andere woorden, er is geen procedure die kan worden toegepast op invoergegevens om de uitvoer van de functie te produceren. Een voorbeeld van een niet-berekenbare functie is het stopprobleem, dat vraagt of een bepaald programma uiteindelijk zal stoppen (stoppen met draaien) of zal blijven draaien voor onbepaalde tijd. Deze functie is niet berekenbaar omdat er geen algemeen algoritme is dat kan bepalen of een bepaald programma wel of niet stopt. Andere voorbeelden van niet-berekenbare functies zijn onder meer de Busy Beaver-functie, die vraagt hoeveel stappen een bepaalde Turing-machine zal nemen voordat deze stopt, en de Entscheidungsproblem, dat de vraag stelt of een bepaald formeel systeem consistent of inconsistent is. Deze functies zijn ook niet berekenbaar omdat ze door geen enkel algoritme kunnen worden berekend. Samenvattend zijn niet-berekenbare functies functies die door geen enkel algoritme kunnen worden berekend, en ze worden vaak gebruikt om de beperkingen van berekeningen en het belang van de computationele complexiteitstheorie aan te tonen.