Primitiv-rekursive Funktion

Grundidee und Bedeutung

Primitiv-rekursive Funktionen sind totale Funktionen auf natürlichen Zahlen, die aus wenigen Grundfunktionen durch Komposition und primitive Rekursion aufgebaut werden. „Total“ bedeutet: Eine k-stellige Funktion ist für jedes Element von ℕᵏ definiert. Funktionen mit einem kleineren Definitionsbereich müssen deshalb zunächst passend auf ganz ℕᵏ fortgesetzt werden.

Primitiv-rekursive Funktionen spielen in der Rekursionstheorie und bei der Präzisierung des Berechenbarkeitsbegriffs eine Rolle. Jede primitiv-rekursive Funktion ist im intuitiven Sinn berechenbar. Umgekehrt ist jedoch nicht jede berechenbare Funktion primitiv-rekursiv: Die Ackermannfunktion und die Sudanfunktion sind berechenbar, aber nicht primitiv-rekursiv. Erst die Klasse der μ-rekursiven Funktionen erfasst den Berechenbarkeitsbegriff vollständig.

Für eine primitiv-rekursive Funktion kann ein Komplexitätsmaß definiert werden. Damit lässt sich die Dauer der Berechnung eines Funktionswertes vorab ermitteln. Die Klasse der primitiv-rekursiven Funktionen ist außerdem genau so mächtig wie die Klasse der LOOP-berechenbaren Funktionen.

Grundfunktionen und Bildungsregeln

Die Klasse Pr der primitiv-rekursiven Funktionen ist die kleinste Menge von Funktionen, die bestimmte Grundfunktionen enthält und unter zwei Bildungsregeln abgeschlossen ist.

Die Grundfunktionen sind:

• Die k-stellige Nullfunktion 0ᵏ: ℕᵏ → ℕ mit 0ᵏ(n₁, …, nₖ) := 0.

• Die k-stellige Projektion πᵏᵢ: ℕᵏ → ℕ für 1 ≤ i ≤ k mit πᵏᵢ(n₁, …, nₖ) := nᵢ. Sie wählt also das i-te Argument aus.

• Die Nachfolgerfunktion ν: ℕ → ℕ mit ν(n) := n + 1.

Die erste Bildungsregel ist die Komposition. Für g: ℕᵐ → ℕ und h₁, …, hₘ: ℕᵏ → ℕ wird C[g,h₁,…,hₘ]: ℕᵏ → ℕ definiert durch Cg,h₁,…,hₘ := g(h₁(n₁,…,nₖ), …, hₘ(n₁,…,nₖ)). Dabei werden zunächst die Funktionen h₁ bis hₘ berechnet; ihre Ergebnisse werden anschließend als Argumente von g verwendet.

Die zweite Bildungsregel ist die primitive Rekursion. Für k ∈ ℕ \ {0}, g: ℕᵏ⁻¹ → ℕ und h: ℕᵏ⁺¹ → ℕ ist R[g,h]: ℕᵏ → ℕ festgelegt durch Rg,h := g(n₂,…,nₖ), falls n₁ = 0, und Rg,h := h(Rg,h, n₁−1,n₂,…,nₖ), falls n₁ ≠ 0. Die Berechnung beginnt somit bei einem Grundwert g und erzeugt jeden weiteren Wert mithilfe von h aus dem vorherigen Wert.

Eine Funktion ist genau dann primitiv-rekursiv, wenn sie sich als Ausdruck aus diesen Grundfunktionen, Komposition und primitiver Rekursion darstellen lässt. Bereits als primitiv-rekursiv nachgewiesene Funktionen dürfen dabei verwendet werden, weil sie durch ihre jeweiligen Ausdrücke ersetzt werden können.

Addition, Multiplikation und Potenz

Die Addition +: ℕ² → ℕ wird rekursiv über das erste Argument definiert: m + n = n, falls m = 0, und m + n = ν((m−1) + n) sonst. Formal gilt +=R[π¹₁,C[ν,π³₁]]. Damit ist die Addition primitiv-rekursiv.

Die Multiplikation ·: ℕ² → ℕ wird mithilfe der bereits primitiv-rekursiven Addition definiert: m · n = 0, falls m = 0, und m · n = (m−1) · n + n sonst. Formal gilt ·=R[0¹,C[+,π³₁,π³₃]]. Daher ist auch die Multiplikation primitiv-rekursiv.

Die Potenzfunktion pot: ℕ² → ℕ mit pot(m,n)=mⁿ wird wiederum über die Multiplikation definiert: pot(m,n) = 1, falls n = 0, und pot(m,n) = pot(m,n−1) · m sonst. Formal gilt pot=C[R[C[ν,0¹],C[·,π³₁,π³₃]],π²₂,π²₁]. Die äußere Komposition C[_,π²₂,π²₁] vertauscht dabei die Parameter m und n. Die drei Beispiele zeigen, dass komplexere Rechenoperationen schrittweise aus einfacheren primitiv-rekursiven Funktionen aufgebaut werden können.

Vorgänger und totale Subtraktion

Die gewöhnliche Vorgängerfunktion ist bei 0 nicht definiert und daher keine primitiv-rekursive Funktion, denn primitiv-rekursive Funktionen müssen total sein. Sie lässt sich jedoch durch einen Wert an der Stelle 0 zu einer totalen Funktion erweitern.

Die modifizierte Vorgängerfunktion p: ℕ → ℕ ist definiert durch p(0)=0 und p(n)=n−1 für n≠0. Sie ist primitiv-rekursiv; formal gilt p=R[0⁰,π²₂].

Auch die gewöhnliche Subtraktion natürlicher Zahlen ist nicht für alle Zahlenpaare definiert. Sie wird deshalb durch Nullen zu einer totalen Subtraktion sub: ℕ² → ℕ erweitert. Diese sogenannte arithmetische Differenz wird charakterisiert durch sub(m,n)=m, falls n=0, und sub(m,n)=p(sub(m,n−1)) sonst. Ist n größer als m, bleibt das Ergebnis nach dem Erreichen von 0 weiterhin 0. Formal gilt sub=C[R[π¹₁,C[p,π³₁]],π²₂,π²₁]. Somit ist die totale Subtraktion primitiv-rekursiv.

Weitere Beispiele und Grenzen

Weitere primitiv-rekursive Funktionen und Konstruktionen sind:

• die zweistelligen Funktionen max und min;

• die Folge der Primzahlen;

• die Funktion, die zu einer natürlichen Zahl n und einer Primzahl p ermittelt, wie oft p als Primfaktor in n vorkommt;

• Arithmetisierungen endlicher Folgen natürlicher Zahlen, also primitiv-rekursive Darstellungen solcher Folgen durch natürliche Zahlen.

Die Beispiele markieren zugleich verschiedene Grenzen der Funktionsklassen. Die Ackermannfunktion und die Sudanfunktion sind nicht primitiv-rekursiv, aber μ-rekursiv und damit berechenbar. Die Funktion Fleißiger Biber („busy beaver“) ist dagegen weder primitiv-rekursiv noch μ-rekursiv.