Hier wird fur jedes n (n 2 1) eine n + 1-stellige rekursive Funktion beschrieben, die eine universelle Funktion fur die n-stelligen primitiv-rekursiven Funktionen ist. Wir legen die von RITCHIE und MEYER [6] bewiesene Charakterisierung der primitivrekursiven Funktionen zugrunde, nilmlich, daB sie die Funktionen sind, die durch Programme einer gewissen Sprache, der sogenannten Loopsprache, bestimmt sind. Unser Beitrag besteht darin, daB wir einen eleganten Algorithmus gefunden haben, mit dem man die Ausfuhrung eines Loopprogramms kontrollieren kann, und daB wir eine einfache bijektive Godelisierung entwickelt haben, die in Einklang mit diesem Algorithmus steht. Hinsichtlich dieser Godelisierung ist zu erwiihnen, daB die Benutzung von bijektiven Abbildungen es uns ermoglicht hat, gewisse liistige Umstande zu vermeiden.
Vier Nebenprodukte unserer Arbeit sind :
- Eine 2-stellige rekursive FunkBion, die in einem gewissen Sinn eine universelle Funktion fur die ganze Menge aller finit-stelligen primitiv-rekursiven Funktionen ist.
2 .
Ein Beispiel dafur, daB es eine rekursive Funktion gibt, die nicht primitiv-rekursiv ist. Die Idee, solch ein Beispiel auf eine universelle Funktion zu begrunden, geht auf P ~T E R
[7] zuruck.
Eine 1 -stellige rekursive Funktion, die alle 1-stelligen primitiv-rekursiven Funktionen majorisiert.
Ein Normalformsatz fur die primitiv-rekursiven Funktionen, die dem Kleeneschen Normalsatz fur die partiell-rekursiven Funktionen ahnelt . 2. Die Loopsprachen L" and L"I Hier werden die Hauptmerkmale der Sprachen kurz zusammengefaBt. Weitere Einzelheiten stehen z. B. in den Buchern von DAVIS und WEYUKER [4] und BRAINERD und LANDWEBER [2].