6

gemeine Relationen werden hergeleitet. Kurz wird auch die Klasse mit den Startfunktionen (},1, x -\- y, x y betrachtet, die echt in der obigen Klasse halten ist. - Я. Ostmann.

Péter , Rôzsa: Rekursive Definitionen, wobei frühere Funktionswerte von abler Anzahl verwendet werden. Publ. math., Debrecen 3, 33—70 (1954).

In einer früheren Arbeit (dies. Zbl. 10, 241) hat Verf. gezeigt, daß die sog. Wertverlaufsrekursion auf gewöhnliche Rekursionen vom selben Typ ( tive bei einer Variablen, ^-rekursive bei к Variablen) und Substitutionen geführt werden kann. Bei einer Wertverlaufsrekursion wird der Wert von q>{n-\- 1)

durch n und 9(0), <p{\), cp{%),.. .,cp{n) so gegeben, daß ^^(w + 1) = у I п,П^ p/W j

( y primitiv-rekursiv). In der vorliegenden Arbeit untersucht Verf. Rekursionen, bei denen der Funktionswert in komplizierterer Weise von früheren ç;-Werten ab-

hängt , wie z. B. 1ю1 <p{m-\-l, n + 1, a) = П max (cp (m -f 1, n, г), (p{m, i, a)).

i — O

Ein anderes Beispiel einer solchen „neuartigen" Rekursion bietet eine rekursive Aufzählung der elementaren Funktionen (das sind solche, die aus 1 und Variablen durch endlich viele Additionen, Multiplikationen, arithmetische Subtraktionen und Divisionen, sowie endliche Summen- und Produktbildungen zusammengesetzt werden können). Verf. erläutert an diesen Beispielen ein allgemeines Verfahren, solche kursionen in gewöhnliehe mehrfache Rekursionen umzuformen. Es besteht, kurz gesagt, darin, die Angaben über die Verwendung der früheren Funktionswerte durch rekursiv definierte Hilfsfunktionen zu beschreiben, die miteinander und mit der Hauptfunktion verschachtelt sind. Das entstehende System simultaner Rekursionen läßt sich zu einer mehrfachen Rekursion für (p zusammenfassen. Das Verfahren kann auch unter Verwendung von Funktionsfunktionen (vgl. R. Péter, dies. Zbl. 45, 4) durchgeführt werden, wobei sich eine primitive Rekursion der 2. Stufe ergibt. In einem Anhang erläutert Verf. die Zurückführimg dieser Rekursion auf eine fache der 1. Stufe. — Im 2. Teil der Arbeit diskutiert Verf. die Frage, welche fachen Rekursionen in primitiv-rekursive umgeformt werden können. Дт Beispiel der Funktion <p{m, n) = Q falls m • n = 0, (p{m-\-l,n-\-1) = ß(m,n,cp{m, y(m, % 9?(w, % + 1))), cp{m-\-l,n)) wird eine solche Umformung durchgeführt. Dabei ist wesentHeh, daß in der Definition von 9?(m + 1, и -f 1) nur Terme (p{m, x) ineinandergeschachtelt sind, nicht aber solche der Form ç)(w -f 1, ж). Dann können die (ungeschaehtelten Glieder q){m+l,x) in einem primitiv-rekursiven Prozeß schrittweise zu ç?(w + 1, 0) abgebaut werden. Es bleibt schließlich eine telte Rekursion nach einer Variablen, die leicht primitiv dargestellt werden kann. Der allgemeine FaU wird analog behandelt, ist aber formal erheblich kompMzierter. Daß eine einzige Schachtelung zweier Terme 9?(w + 1, x) eine nicht primitiv- rekursive Funktion erzeugen kann, ergibt sich aus einer entsprechenden Umformung der bekannten Aekermannschen Funktion. Die erwähnte Aufzählung der elementaren Funktionen genügt dieser Bedingung, ist also primitiv-rekursiv darstellbar. Da diese Funktion nicht elementar sein kann (Diagonalverfahren), gewinnt Verf. einen neuen Beweis für den Satz von Ilona Bereczki (dies. Zbl. 49, 8), nach dem nicht alle primitiv-rekursiven Funktionen elementar sind. — Errata: S. 37, Z. 13 v.u.: (p{m, i, a) statt cp{m, i, r). S. 40, Z. 3 v. o.: ipj, statt ip; Z. 6 v. o. : ср^^. statt q).

W . MarJcwaM.

Rice , H. G.: Recursive real numbers. Proc. Amer. math. Soc. 5, 784—791 (1954).

Die reelle Zahl a ist eine rekursive reelle Zahl, wenn sie Grenzwert ist einer kursiven (= aUgemein rekursiven) Folge «^ von rationalen Zahlen, welche rekursiv konvergiert, d. h. zu der es eine solche rekursive Punktion g gibt, daß \a^ — a^\ <1/Ж für g{N) < m, n. Der Bereich E dieser Zahlen bildet einen Körper; jede rekursive und rekursiv konvergente Folge von Zahlen aus E besitzt einen Grenzwert in E