Konstruktion nichtrekursiver Funktionen. (Q2611338)

\textit{W. Ackermann} hat bewiesen (Math. Ann. 99 (1928), 118-133; F. d. M. 54, 57 (JFM 54.0057.*)), daß die mehrfache Rekursion, d. h. gleichzeitige Rekursion nach mehreren Variablen, aus der Klasse der ``rekursiven'' Funktionen, d. h. der durch einfache Rekursion herstellbaren, hinausführt. Für diesen Satz werden in vorliegender Arbeit zwei weitere Beweise gegeben. Der erste Beweis beruht auf dem Diagonalverfahren. Es wird gezeigt, daß die zweistelligen rekursiven Funktionen aus fünf Ausgangsfunktionen durch Anwendung eines Rekursionsschemas ohne Parameter und eines Substitutionsschemas entstehen. Dadurch gelingt es ziemlich einfach, diese zweistelligen Funktionen abzuzählen, und die Abzählung liefert eine dreistellige Funktion, die nach dem bekannten Diagonalverfahren nicht zur Klasse der rekursiven Funktionen gehören kann. Andererseits zeigt Verf., daß diese dreistellige Funktion durch eine zweifache Rekursion definierbar ist. Der zweite Beweis ist eine Vereinfachung des \textit{Ackermann}schen. Es wird eine Folge von Funktionen \(\varphi_m(n)\) gebildet, welche die Eigenschaften a) \(\varphi_m(n) > n\), \quad b) \((n < n') \to (\varphi_m(n) < \varphi_m(n'))\), \quad c) \(\varphi_{m+1}(n) \geqq \varphi_m(n + 1)\) \noindent haben, während außerdem gezeigt wird, daß es zu jeder einstelligen rekursiven Funktion \(\alpha(n)\) ein solches \(m\) gibt, daß \(\varphi_m(n) > \alpha(n)\) ist für alle \(n\). Da \(\varphi_n(n) > \varphi_m(n)\) ist, wenn \(n > m\), so ist also \(\varphi_n (n)\) keine rekursive Funktion. Andererseits ist \(\varphi(m, n)=\varphi_m(n)\) durch die zweifache Rekursion \[ \begin{gathered} \varphi(0,n)= 2n+1, \\ \varphi(m+1,0) = \varphi(m,1), \\ \varphi(m+1,n+1)=\varphi(m,\varphi(m+1,n)), \end{gathered} \] definiert. Zum Schlüsse verspricht Verf., die mehrfache Rekursion näher zu untersuchen, z. B. vom Gesichtspunkte ihres Zusammenhanges mit den \textit{Hilbert}schen höheren Funktionentypen, und auch von dem Gesichtspunkte, daß das Diagonalverfahren auch auf die so definierten Funktionen anwendbar ist. Man wird dem Resultate dieser Untersuchung mit großem Interesse entgegensehen.