Primitief recursieve functie

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.

Definitie

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 constante functie 0, dat wil zeggen de functie die elke $n\in \mathbb {N}$ op 0 afbeeldt, is een primitief recursieve functie;
• de opvolgerfunctie $s\colon \mathbb {N} \to \mathbb {N}$, gedefinieerd als $s(n)=n+1$, is een primitief recursieve functie;
• voor elke $0<j\leq k$ is de projectie $\pi _{j,k}\colon \mathbb {N} ^{k}\to \mathbb {N}$, gedefinieerd door $\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, is ook de functie $f\colon \mathbb {N} ^{k+1}\to \mathbb {N}$ die gedefinieerd wordt door

$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}))$

primitief recursief. (Deze laatste eis heet primitieve recursie.)

De laatste eis, de primitieve recursie, kan worden gezien als een definitie van $f$ in twee gevallen: het basisgeval, als het eerste argument gelijk aan 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

Voorbeelden van primitief recursieve functies zijn:

• Optellen

${\begin{aligned}{\mathit {plus}}(0,n)&=n\\{\mathit {plus}}(m+1,n)&=s({\mathit {plus}}(m,n))\end{aligned}}$

• Vermenigvuldigen

${\begin{aligned}{\mathit {maal}}(0,n)&=0\\{\mathit {maal}}(m+1,n)&={\mathit {plus}}(n,{\mathit {maal}}(m,n))\end{aligned}}$

• 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

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

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