Primitief recursieve functie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 minimalizering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt.

Definitie[bewerken]

Primitief recursieve functies zijn functies op de natuurlijke getallen, de verzameling \mathbb{N}=\{0,1,2,3,\ldots\}; het zijn functies die een of meer natuurlijke getallen als argumenten nemen en als functiewaarde een natuurlijk getal opleveren.

De klasse der primitief recursieve functies is als volgt inductief gedefinieerd:

  • de constante 0-functie, dat wil zeggen de functie f_0\colon\mathbb{N}\to\mathbb{N} zodat f_0(x)=0, voor alle x\in\mathbb{B}, is een primitief recursieve functie;
  • de opvolgerfunctie s\colon\mathbb{N}\to\mathbb{N}, gedefinieerd als s(x)=x+1, is een primitief recursieve functie;
  • voor elke 0<j\leq k is de projectiefunctie \pi_{j,k}\colon\mathbb{N}^k\to\mathbb{N}, gedefinieerd als \pi_{j,k}(n_1,\ldots,n_k) = n_j, een primitief recursieve functie;
  • de compositie van primitief recursieve functies is primitief recursief;
  • als g\colon\mathbb{N}^k\to\mathbb{N} en h\colon\mathbb{N}^{k+2}\to\mathbb{N} primitief recursieve functies zijn, dan is ook de functie f\colon \mathbb{N}^{k+1}\to\mathbb{N} die gedefinieerd wordt als
\begin{align}f(0,n_1,\ldots,n_k) &= g(n_1,\ldots,n_k) \\ f(m+1,n_1,\ldots,n_k) &= h(m,n_1,\ldots,n_k,f(m,n_1,\ldots,n_k))\end{align}
primitief recursief. (Dit laatste heet primitieve recursie.)

Het laatste geval, de primitieve recursie, kan worden gezien als een definitie van f in twee gevallen: het basisgeval, als het eerste argument gelijk 0 is, wordt gegeven door de functie g, terwijl het recursieve geval, als het eerste argument groter dan 0 is, wordt gegeven door de functie h.

Voorbeelden[bewerken]

Voorbeelden van primitief recursieve functies zijn:

  • Optellen
\begin{align} \mathit{plus}(0,n) &= n \\ \mathit{plus}(m+1,n) &= s(\mathit{plus}(m,n)) \end{align}
  • Vermenigvuldigen
\begin{align} \mathit{maal}(0,n) &= 0 \\ \mathit{maal}(m+1,n) &= \mathit{plus}(n, \mathit{maal}(m,n)) \end{align}
  • Machtsverheffen
\mathit{exp}(n,m) = \mathit{exp}'(m,n), waarbij \mathit{exp}'(0,n) = 1 en \mathit{exp}'(m+1,n) = \mathit{maal}(n,\mathit{exp}'(m,n))

Functies die niet primitief recursief zijn[bewerken]

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.

Literatuur[bewerken]

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