Über die mehrfache Rekursion.
type: Item
instance of: scholarly article
title: Über die mehrfache Rekursion.
zbMATH Open document ID: 62.1055.04
DOI: 10.1007/BF01571648
published in: Mathematische Annalen
publication date: 1936-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/159882
review text: 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 \!, …
zbMATH DE Number: 2528665
author: R. Politzer
MaRDI profile type: MaRDI publication profile
cites work: Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion
description: scientific article; zbMATH DE number 2528665