title: Μ-recursieve functie
text: 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 
  μ-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 
   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 
  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  
   Uwe Schöning, Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum, 2009
   Elaine Rich, Automata, Computability and Complexity, Pearson, 2008
  
  Theoretische informatica