Über die mehrfache Rekursion. (Q2610751)

Vorliegende Arbeit enthält wichtige Ergebnisse über die mehrfachen rekursiven Definitionen, d. h. diejenigen, welche nach mehreren Variablen zugleich laufen. Die Verf. macht im Teil I darauf aufmerksam, daß die mehrfachen Rekursionen sich auf einfache zurückführen lassen, wenn die Rekursionen der \textit{Hilbert}schen zweiten Stufe, nämlich Rekursionen, worin auch Funktionsfunktionen eingehen, zugelassen werden. Dies wird durch ein Beispiel näher gezeigt; übrigens verspricht sie, in einer späteren Arbeit genauer auf den Zusammenhang der \textit{Hilbert}schen höheren Stufen mit der mehrfachen Rekursion zurückzukommen. Im Teil II wird zuerst die \(k\)-fache Rekursion auf eine ``normierte'' Form gebracht. In dieser können beliebig komplizierte Einschachtelungen vorkommen. Verf. zeigt, wie diese teilweise eliminiert werden können, so daß man die ``primitive'' Form der \(k\)-fachen Rekursion erhält. In dieser kommen nur zweifache Einschachtelungen vor. Andererseits beweist sie, daß die mehrfachen Rekursionen ohne Einschachtelung sämtlich auf einfache Rekursionen zurückführbar sind. Da nach einem Satze von \textit{Ackermann} schon eine zweifache Rekursion über die einfachen hinausführen kann, so folgt, daß eine Elimination der in der ``primitiven'' \(k\)-fachen Rekursion noch vorkommenden Einschachtelungen nicht möglich ist. Die Zurückführung der \(k\)-fachen Rekursionen auf die ``primitive'' Form ermöglicht eine Abzählung aller \(k\)-rekursiven Funktionen. Diese Abzählung wird durch eine \((k+1)\)-fache Rekursion bewerkstelligt. Nach dem Diagonalverfahren folgt daraus, daß diese \((k+1)\)-fache Rekursion aus dem Bereich der \(k\)-rekursiven Funktionen hinausführt. Im letzten Paragraphen wird unter Anwendung eines von \textit{J. v. Neumann} herrührenden Gedankens der Satz bewiesen: Jede \(k\)-rekursive Funktion \(\psi \,(n_1, \ldots \!, n_l)\) kann in der ``expliziten'' Form \[ \psi \,(n_1, \ldots \!, n_l)= \alpha \,(\mu_x \,(\text{\boldsymbol{B}} \,(x, \,n_1, \ldots \!, n_l))) \] geschrieben werden, wo \(\alpha \,(n)\) eine 1-rekursive Funktion und \(\text{\boldsymbol{B}} \,(m, \,n_1, \ldots \!, n_l)\) eine 1-re kursive Beziehung ist, für die es zu jedem \(n_1, \ldots \!, n_l\) ein \(m\) gibt derart, daß \(\text{\boldsymbol{B}} \,(m, \,n_1, \ldots \!, n_l)\) zutrifft; sogar gilt \(\psi \,(n_1, \ldots \!, n_l)=\alpha \,(m)\) für jedes solche \(m\).