Zur Theorie der rekursiven Funktionen. (Q2614111)

Eine zahlentheoretische Funktion wird \textit{rekursiv} genannt, falls sie aus den Ausgangsfunktionen 0 und \(n + 1\) mit Hilfe von endlich vielen Substitutionen und \textit{primitiven Rekursionen} entsteht. Dabei wird unter einer primitiven Rekursion die rekursive Definition einer Funktion \(\varphi\) mit Hilfe der Funktionen \(\alpha\) und \(\beta\) mittels eines Gleichungssystems der Form \[ \varphi(0, \, a_1, \ldots \!, a_r) = \alpha(a_1, \ldots \!, a_r), \] \[ \varphi(n+1, \, a_1, \ldots \!, a_r) = \beta(n, \, a_1, \ldots \!, a_r, \, \varphi(n, \, a_1, \ldots \!, a_r)) \] verstanden. In {\S} 1 wird die Rekursivität einiger Hilfsfunktionen bewiesen, die später gebraucht werden. {\S} 2 enthält den Beweis, daß eine \textit{Wertverlaufsrekursion}, angewandt auf rekursive Funktionen, wiederum eine rekursive Funktion ergibt. Dabei nennt Verf. Wertverlaufsrekursion eine rekursive Definition, bei der \(\varphi(0, \, a_1, \ldots \!, a_r)\) direkt, ferner \(\varphi(n+1, \, a_1, \ldots \!, a_r)\) mit Hilfe der Funktionswerte von \(\varphi\) an beliebig vielen Stellen angegeben wird, wobei an Stelle von \(n + 1\) stets kleinere Zahlen stehen; z.B. \[ \varphi(0, \, a) = \alpha(a), \] \[ \varphi(n+1, \, a) = \beta(n, \, a, \, \varphi(\gamma(n, \, a), \, a), \, \varphi(\delta(n, \, a), \, a)) \] mit \(\gamma(n, \, a) \leqq n\), \(\delta(n, \, a) \leqq n\); oder \[ \varphi(0, \, a) = \alpha(a), \] \[ \varphi(n+1, \, a) = \beta(n, \, a, \, \sum_{i=0}^{n} \gamma \, (\varphi(i, \, a)). \] Als allgemeine Form einer Wertverlaufsrekursion wird \[ \varphi(0, \, a_1, \ldots \!, a_r) = \alpha(a_1, \ldots \!, a_r), \] \[ \varphi(n+1, \, a_1, \ldots \!, a_r) = \beta \left (n, \, a_1, \ldots \!, a_r, \, \prod\limits_{i=0}^{n} p_i^{\varphi(i, \, a_1, \ldots \!, a_r)} \right) \] zugrunde gelegt (\(p_0 = 2\), \(p_n\) = die \(n\)-te ungerade Primzahl für \(n \geqq 1\)); es wird gezeigt, daß diese Form die rekursiven Definitionen der oben erwähnten Beispiele als Spezialfälle enthält. Der Beweis ist im wesentlichen derselbe, den Verf. in Math. Ann. 110 (1934), 612-632 (F.~d.~M. 60\(_{\text{II}}\), 851) gegeben hat. In {\S} 3 wird bewiesen, daß aus rekursiven Funktionen auch durch eine \textit{eingeschachtelte Rekursion} wiederum eine rekursive Funktion entsteht. Dabei sagt man, die Funktion \(\varphi\) entsteht aus den Funktionen \(\alpha, \, \beta_1, \, \beta_2, \ldots \!, \beta_l\) durch eine eingeschachtelte Rekursion, falls \[ \varphi(0, \, a_1, \ldots \!, a_r) = \alpha(a_1, \ldots \!, a_r), \] ferner \(\varphi(n+1, \, a_1, \ldots \!, a_r)\) als ein Ausdruck angegeben ist, der aus \(\varphi, \, \beta_1, \, \beta_2, \ldots \!, \beta_l\) mit Hilfe von endlich vielen Einsetzungen entsteht, aber so, daß an der ersten Argumentstelle von \(\varphi\) stets \(n\) stehen soll; z. B. \[ \varphi(0, \, a) = \alpha(a), \] \[ \varphi(n+1, \, a) = \beta(n, \, \varphi(n, \, \gamma(n, \, a, \, \varphi(n, \, a))). \] Der Beweis ist wesentlich einfacher, als in der oben angeführten Arbeit; die dort auftretenden kombinatorischen Schwierigkeiten werden nämlich mit Hilfe des Satzes von der eindeutigen Primfaktorenzerlegung umgangen. Der deutsche Auszug am Schlüsse der Arbeit ist so ausführlich, daß daraus alle Einzelheiten dieses Beweises zu verstehen sind.