Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Berekenbaarheidstheorie (theoretische informatica)

Engels: Theory of computation · Ook wel: theory of computation, computation theory, berekeningstheorie

In het kort

Berekeningstheorie is het vakgebied in de theoretische informatica en de wiskunde over de grenzen van computers. Onderzoekers gebruiken eenvoudige rekenmodellen, zoals de turingmachine, om te bepalen welke problemen een algoritme kan oplossen en hoeveel tijd of geheugen dat kost. Een bekend resultaat is het stopprobleem: geen programma kan vooraf bepalen of een willekeurig programma bij een gegeven invoer ooit stopt.

Waarom is dit belangrijk?

Dankzij berekeningstheorie is duidelijk dat geen algemeen hulpmiddel elk gedrag van willekeurige software altijd volledig kan controleren. In het hoger onderwijs leren informaticastudenten juist daardoor wanneer een automatische controle van bestaande programma's niet verder komt. Voor leerlingen en werknemers blijft zo'n controle in de praktijk nuttig, maar niet elke concrete fout in een programma is vooraf met zekerheid te vinden.

Zo werkt het in de praktijk

In de natuurkunde en de biologie gebruiken onderzoekers berekeningstheorie om rekengrenzen te beschrijven. De vereniging Computability in Europe brengt dat werk samen met wiskunde en informatica. De Association for Symbolic Logic organiseert als beroepsvereniging meerdere conferenties per jaar.

Onderzoekers vragen hoe zij niet-berekenbare functies in een rangorde zetten. Die rangorde laat zien welke functie meer hulp nodig heeft dan een andere. Daarnaast bestuderen zij of de ene verzameling de berekening van de andere mogelijk maakt.

In de informatica koppelen onderzoekers de theorie aan formele methoden en formele talen. Formele methoden zijn een werkwijze om berekeningen met vaste regels te beschrijven en te toetsen. Computability in Europe voert de redactie van het tijdschrift Computability en van een boekreeks over deze theorie.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026