μ-recursieve functie

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 $\mathbb {N} =\{0,1,2,3,\ldots \}$; 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 $c_{0}\colon \mathbb {N} \to \mathbb {N}$ zodat $c_{0}(x)=0$, voor alle $x\in \mathbb {N}$, is μ-recursief;
• de opvolgerfunctie $s\colon \mathbb {N} \to \mathbb {N}$, gedefinieerd als $s(x)=x+1$, is μ-recursief;
• 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}$, μ-recursief;
• de compositie van μ-recursieve functies is μ-recursief;
• primitieve recursie: als $g\colon \mathbb {N} ^{k}\to \mathbb {N}$ en $h\colon \mathbb {N} ^{k+2}\to \mathbb {N}$ μ-recursieve functies zijn, dan is ook de functie $f\colon \mathbb {N} ^{k+1}\to \mathbb {N}$ die gedefinieerd wordt als

${\begin{aligned}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{aligned}}$

μ-recursief.

• minimalisatie: als $f\colon \mathbb {N} ^{k+1}\to \mathbb {N}$ een μ-recursieve functie is, dan is ook $\mu f\colon \mathbb {N} ^{k}\to \mathbb {N}$, die als volgt gedefinieerd is:

$\mu f(n_{1},\ldots ,n_{k})=\min\{m\mid f(n_{1},\ldots ,n_{k},m)=0{\text{ en voor alle }}m'<m{\text{ is }}f(n_{1},\ldots ,n_{k},m'){\text{ gedefinieerd}}\}$

μ-recursief. Hierbij is $\min \varnothing$ niet gedefinieerd.

De minimalisatie $\mu f$ van een functie $f(x,y)$ is de kleinste waarde van $y$ zodat $f(x,y)=0$. Als het zo is dat $f(x,y)\neq 0$ voor alle $y$, dan is $\mu f(x)$ niet gedefinieerd.

Voorbeelden

• Alle primitief recursieve functies zijn ook μ-recursief.
• In het bijzonder is de primitief recursieve functie $f(x,y)=1$ voor alle $x,y\in \mathbb {N}$ μ-recursief, want ze is de compositie van de opvolgerfunctie, de constante 0-functie en een projectiefunctie.
• De overal ongedefinieerde functie $\omega$, met $\omega (x)$ is niet gedefinieerd voor alle $x$, is μ-recursief. Deze functie $\omega$ is gelijk aan de minimalisatie $\mu f$ van $f$ (zie hierboven), omdat er geen $m$ bestaat zodat $f(x,m)=0$. Dat wil zeggen: $\omega =\mu f$.

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