μ-recursieve functie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

In de theoretische informatica vormen de μ-recursieve functies een klasse van functies. De klasse is gedefinieerd als de klasse van functies die de basisfuncties bevat (de constante nulfunctie, de opvolgerfunctie en de projectiefuncties) en afgesloten is onder compositie, primitieve recursie en minimalisatie. De klasse van primitief recursieve functies vormen een onderklasse van de μ-recursieve functies. De μ-recursieve functies komen precies overeen met de berekenbare functies.

Definitie[bewerken | brontekst bewerken]

μ-recursieve functies zijn partiële functies op de natuurlijke getallen, de verzameling ; het zijn functies die een of meer natuurlijke getallen als argumenten nemen en als functiewaarde ofwel een natuurlijk getal opleveren, ofwel niet gedefinieerd zijn.

De klasse der μ-recursieve functies is als volgt inductief gedefinieerd:

  • de constante 0-functie, dat wil zeggen de functie zodat , voor alle , is μ-recursief;
  • de opvolgerfunctie , gedefinieerd als , is μ-recursief;
  • voor elke is de projectiefunctie , gedefinieerd als , μ-recursief;
  • de compositie van μ-recursieve functies is μ-recursief;
  • primitieve recursie: als en μ-recursieve functies zijn, dan is ook de functie die gedefinieerd wordt als
μ-recursief.
  • minimalisatie: als een μ-recursieve functie is, dan is ook , die als volgt gedefinieerd is:
μ-recursief. Hierbij is niet gedefinieerd.

De minimalisatie van een functie is de kleinste waarde van zodat . Als het zo is dat voor alle , dan is niet gedefinieerd.

Voorbeelden[bewerken | brontekst bewerken]

  • Alle primitief recursieve functies zijn ook μ-recursief.
  • In het bijzonder is de primitief recursieve functie voor alle μ-recursief, want ze is de compositie van de opvolgerfunctie, de constante 0-functie en een projectiefunctie.
  • De overal ongedefinieerde functie , met is niet gedefinieerd voor alle , is μ-recursief. Deze functie is gelijk aan de minimalisatie van (zie hierboven), omdat er geen bestaat zodat . Dat wil zeggen: .

Verband met andere klassen van functies[bewerken | brontekst bewerken]

De μ-recursieve functies komen precies overeen met de berekenbare functies. Dat wil zeggen dat er voor elke μ-recursieve functie een turingmachine bestaat die de functie berekent, en andersom, dat elke turingmachine een μ-recursieve functie berekent. Functies die niet berekenbaar zijn, zoals de busy beaver-functie, zijn daarom ook niet μ-recursief.

De primitief recursieve functies vormen een echte onderklasse van de μ-recursieve functies. De klasse der μ-recursieve functies ontstaat als we de klasse der primitief recursieve functies onder minimalisatie afsluiten. Alle primitief recursieve functies zijn dus ook μ-recursief. Aan de andere kant bestaan er μ-recursieve functies die niet primitief recursief zijn, zoals de Ackermannfunctie.

Literatuur[bewerken | brontekst bewerken]

  • Uwe Schöning, Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum, 2009
  • Elaine Rich, Automata, Computability and Complexity, Pearson, 2008