Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion. (Q2619882)

Die Verf. gibt zuerst einen wichtigen Grund an, sich mit den Rekursionen zu beschäftigen. Es ist nämlich, wie Ref. einmal besonders nachdrücklich hervorgehoben hat, auf Grund der rekurrierenden Denkweise möglich, die Arithmetik in durchaus finiter Weise zu begründen. Sie erklärt außer dem Begriff der ``primitiven'' Rekursion, die \(\varphi (n + 1)\) durch \(n\) und \(\varphi (n)\) bestimmt, wobei außerdem festgehaltene Parameter in beliebiger Anzahl vorkommen können, noch drei andere Arten von Rekursionen. Diese sind: 1. Die Wertverlaufsrekursionen, bei welchen der Funktionswert \(\varphi (n + 1)\) nicht nur mittels \(n\) und \(\varphi (n)\) bestimmt wird, sondern mittels mehrerer der Werte \(\varphi (0), \varphi (1), \cdots,\varphi (n)\). 2. Die eingenschachtelte Rekursion, bei welcher die Parameter nicht festgehalten werden, sondern Einsetzungen für sie gemacht werden. 3. Die mehrfache Rekursion, d. h. die gleichzeitige Rekursion nach zwei oder mehr Variablen. Versteht man nun unter einer ``rekursiven'' Funktion eine, die mit Hilfe von primitiven Rekursionen und Einsetzungen gebildet werden kann, so weiß man nach einem Satze von \textit{W. Ackermann}, daß man mittels der mehrfachen Rekursion Funktionen bilden kann, die nicht mehr zur Klasse der rekursiven Funktionen gehören. Dagegen zeigt Verf. in dieser Arbeit, daß die Wertverlaufsrekursion und die eingeschachtelte Rekursion nicht aus jener Klasse herausführen können. Zuerst zeigt sie durch Anwendung der Primzahlzerlegung, daß es genügt, höchstens zweistellige Funktionen zu betrachten. Indem der Wertverlauf einer Funktion \(\varphi (i,a)\) durch die Funktion \[ \psi (n,a) = p_0^{\varphi (0,a)} p_1^{\varphi (1,a)} \cdots p_n^{\varphi (n,a)}, \] wo \(p_i\) die \(i\)-te Primzahl bedeutet, vollständig charakterisiert ist und \(\psi \) eine primitive Rekursion definierbar ist, gelingt es zu zeigen, daß jede durch eine Wertverlaufsrekursion definierte Funktion \(\varphi \) auch rekursiv ist. Danach zeigt sie, daß die eingeschachtelte Rekursion \[ \varphi (0,a) = \alpha (a), \] \[ \varphi (n + 1,a) = \mathfrak {g}_b(n,a,\varphi (n,b)), \] wo \(\alpha \) und die in \(\mathfrak {g}_b\) eingehenden Funktionen rekursiv sind, zu einer rekursiven Funktion \(\varphi \) führt. Der Beweis ist ziemlich kompliziert; Verf. macht aber in einem Zusatz darauf aufmerksam, daß sie auf Anregung von \textit{L. Kalmár} den Beweis vereinfacht hat (\textit{R. Péter}, Zur Theorie der rekursiven Funktionen. (Ungarisch mit deutschem Auszug.) Mat Fiz. Lapok 42 (1935), 25-49; F. d. M. \(61_{\text{II}}\)).