Loading AI tools
Van Wikipedia, de vrije encyclopedie
In de theoretische informatica vormen de primitief recursieve functies een klasse van totale, berekenbare functies. De klasse is gedefinieerd als de kleinste klasse van functies die de basisfuncties (constante functies, opvolgerfunctie en projectie) bevat, en afgesloten is onder compositie en primitieve recursie. Alle primitief recursieve functies zijn totaal en berekenbaar, maar er bestaan totale en berekenbare functies die niet primitief recursief zijn, zoals de Ackermannfunctie. Als we de klasse van primitief recursieve functies ook onder minimalisering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt.
Een primitief recursieve functie is een functie die aan een of meer natuurlijke getallen (0,1,2,3,...) als functiewaarde een natuurlijk getal toevoegt, en die behoort tot de als volgt inductief gedefinieerde klasse:
De laatste eis, de primitieve recursie, kan worden gezien als een definitie van in twee gevallen: het basisgeval, als het eerste argument gelijk aan 0 is, wordt gegeven door de functie , terwijl het recursieve geval, als het eerste argument groter dan 0 is, wordt gegeven door de functie .
Voorbeelden van primitief recursieve functies zijn:
De primitief recursieve functies vormen een onderklasse van de berekenbare functies; dat wil zeggen dat niet-berekenbare functies, zoals de busy beaver-functie, ook niet primitief recursief zijn. Aangezien het eerste argument van recursief gedefinieerde functies in de recursieve aanroep altijd wordt verlaagd, zijn primitief recursieve functies altijd totale functies. Dat wil zeggen dat berekenbare functies die niet overal gedefinieerd zijn niet primitief recursief kunnen zijn. Ten derde zijn er ook totale, berekenbare functies die niet primitief recursief zijn. Het bekendste voorbeeld van zo'n functie is de Ackermannfunctie.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.