Zeitsohr. 1. math. Logik und Orundlagen d . MUh. Bd. 33, S. 527-535 (1987)

EINE REKURSIVE UNIVERSELLE FUNKTION FOR DIE PRIMITIV-REKURSIVEN FUNKTIONEN

von HILBERT LEVITZ und WARREN NICHOLS in Tallahassee, Florida (U.S.A.)

1. Einleitung

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 primitiv- rekursiven 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 Be- nutzung von bijektiven Abbildungen es uns ermoglicht hat, gewisse liistige Umstande zu vermeiden.

Vier Nebenprodukte unserer Arbeit sind :

1. Eine 2-stellige rekursive FunkBion, die in einem gewissen Sinn eine universelle Funk- tion 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.

3. Eine 1 -stellige rekursive Funktion, die alle 1-stelligen primitiv-rekursiven Funk- tionen majorisiert.

4. 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 Einzel-

heiten stehen z. B. in den Buchern von DAVIS und WEYUKER [4] und BRAINERD und LANDWEBER [2].

Die Sprache L besitzt drei Arten von Variablen:

Die Symbole X , , X I , X , , . . . sind Eingangsvariablen. Die Symbole Z , , 2, ~ Z, , . . . sind Hilfsvariablen. -

Das Symbol Y ist Ausyungsvuriable.

Als Mitteilungszeichen fiir Variablen verwenden wir die Symbole V , V' . Mittei- lungszeichen fur die Werte der Variablen V , V' sind v bzw. v'.

528 x. LEVITZ UND w. NICHOLS

Die Befehle sind

1. V t O , 2. V t V + 1 , 3. V t V' , 4. LOOP V , 6. END.

Ein E-Programm ist eine endliche (eventuell leere) Folge von Befehlen, deren LOOP- END Befehle sich wie Klammern paaren.

Die erste Art von Befehl bedeutet, ,,v SOH durch 0 ersetzt werden", die zweite, ,,v sol1 durch v + 1 ersetzt werden", die dritte, ,,v soll durch v' ersetzt werden". Diese drei Arten von Befehlen nennen wir Zuordnungsbefehle. LOOP V befiehlt, ,,alles bis zu dem zugehorigen END soll v-ma1 wiederholt werden". Wahrend der Ausfuhrung der Schleife darf der Wert von V verandert werden, aber das hat keinen EinfluD auf die Anzahl der Wiederholungen der betreffenden Schleife ; diese ist alleine bestimmt durch den Wert der Loopvariablen V beim Eintritt in die Schleife.

1 eine n-stellige Funktion wie folgt : Den Variablen X, , X , , X , , . . . , X n - , ordnet man die Werte x, , x, , x2 . . . , x,-, zu. Alle anderen Variablen bekommen am Anfang den Wert 0. Am Ende der Ausfiihrung des Programms wird der Wert der Variablen Y als Bild des n-Tuples xo , z1 , x2 , . . . , xn- , betrachtet. Nach Vereinbarung bestimmt das leere Programm die Funktion, deren Wert immer 0 ist.

Jedes E-Programm bestimmt f i i r jede Zahl n

Wegen des Programms

V c O , LOOP V ' , V t V + 1 END

ist der Befehl V c V' iiberflussig. Wir ziehen es vor, diesen Befehl wegzulassen. Die dadurch entstehende Sprache nennen wir A', und ihre Programme nennen wir E'-Pro- graname.

Unter einem Programmabschnitt verstehen wir eine Folge von Befehlen, die ent- ueder nur aus einem einzelnen Glied V t 0 oder V t V + 1 besteht oder die Form LOOP V , P, END hat, wobei, P kin Programm bedeutet. Die ersterwahnte Art nennen wir einen Zuordnungsabschnitt, die zweite einen Loopabschnift.

Es laBt sich leicht beweisen, daB es zu jedem Programm P eine eindeutig bestimmtc cndliche Folge P = P o , P, , . . . , Pk von Programmabschnitten gibt, so daB P qie Ver- kettung dieser Folge ist. Eine endliche Folge von Programmabschnitten nennen wir eine Absclwdtsfolge. Offenbar ist jede Abschnittsfolge eine Abschnittsfolge eines ein- deutig bestimmten Programms.

Beispiel 2.1. Das E'-Programm

x , + X I + 1 , LOOP x, , X34-X3 + 1 , END

besitzt die Abschnittsfolge P = P o , P, , wobei Po nur das Glied X , c X , + 1 ent- halt und P, aus den Gliedern LOOP X , , X, t X , + 1, END besteht.

EINE REKURSIVE UNIVERSELLE FUNKTION FUR DIE PRIYITIV-REKURSIVEN FUNKTIONEN 529

3. Der Hontrollalgorithmus

Hier geben wir eine naheliegende Beschreibung eines Algorithmus an, der die Aus- fiihrung der E’-Programme kontrollieren kann. Wir stellen uns vorliiufig vor, daB fur die Ausfuhrung der E’-Programme ein Mensch verantwortlich ist. Da es nur die Zu- ordnungsbefehle V c 0 und V t V + 1 sind, die eine direkte Wirkung auf die Va- riablen haben, besteht letzten Endes seine Aufgabe darin, diese Befehle in der richtigen Reihenfolge und Hiiufigkeit auszufiihren. Um die Ausfiihrung des Programms ver- folgen zu konnen, halt der Kontrolleur eine Abschnittsfolge aufrecht. Am Anfang ist diese Folge die Abschnittsfolge des gegebenen Programms. Die Berechnung findet Schritt fur Schritt statt. In einem gegebenen Schritt betrachtet der. Kontrolleur das am weitesten links stehende Glied der Abschnittsfolge und reagiert wie folgt: Wenn das Glied ein Zuordnungsabschnitt ist, fuhri er den Zuordnungsbefehl aus, beseitigt das Glied aus der Abschnittsfolge und geht nach rechts zum niichsten Glied der Ab- schnittsfolge, falls es ein niichstes Glied gibt. Wenn dagegen das am weitesten links stehende Glied ein Loopabschnitt LOOP V , Q, END ist, merkt er sich den Wert w der Loopvariablen V , beseitigt das Glied aus der Abschnittsfolge, hiingt dafiir w Exemplare der Abschnittsfolge des Programms Q an das linke Ende der Abschnittsfolge an, und fahrt mit dem am weitesten links stehenden Glied der nun entstandenen Abschnitts- folge fort (falls es ein solches gibt). Die Berechnung hort auf, wenn die Abschnitts- folge leer ist.

Beispiel 3.1. Wir fiihren das in Beispiel 2.1 gegebene Programm mit den folgenden Anfangswerten aus. Sei X, = 2, und seien alle anderen Variablen gleich 0 gesetzt. Hier bezeichnen wir mit Q den Programmabschnitt, dessen einziges Glied der Befehl X, t X, + 1 ist. (Obrigens ist Q kein Programmabschnitt des urspriinglichen Pro- gramms.)

Sohritt Abschnittsfolge Zustand der Variablen

0 P o , p1

1 P I

2 Q> Q 3 Q 4 G.I

Y = 0, XI = 0, x, = 2, x, = 0

Y = 0, x, = 1, x, = 2, x, = 0

Y = 0, x, = 1, x, = 2, x, = 0

Y = 0, XI = 1, x, = 2 , x, = 1

Y = 0, x, = 1, x, = 2, x, = 2

4. Ein Hilissatz uber primitive Rekursion

f ( r , , x 2 , . . ., x,) definiert man wie folgt: Die k-fache Iteration f k ( x I , x2, . . . , xn) der n-stelligen primitiv-rekursiven Funktion

f O ( x l 9 x2 5 . . . i xn) = xn >

f ” ” ( ~ 1 , 2 2 , . . ‘ 7 xn) = ~ 2 , . . ‘ 9 x n - 1 3 fk(xl, ~ 2 , . * ., x n ) ) .

Es folgt unmittelbar aus der Definition der primitiven Rekursion, daB die n + 1- stellige Funktion f k ( ( x l , 2, , . . . , xn) ebenfalls primitiv-rekursiv ist. Die Iteration wird nicht nur in diesem Teil unseres Artikels benutzt, sondern auch in den folgenden. 34 L t d i r . f . math. Loglh

530 H. LEVITZ UND w. NICHOLS

Der folgende Hilfssatz ist ein spezieller Fall eines in P ~ T E R [7] stehenden Ergebnisses. Da es dort nur mittels eines Beispiels beschrieben ist, geben wir hier unseren eigenen Beweis.

Hi l f ssa tz 4.1. Sei f eine Funktion, wekhe die folgenden Uleichungen erfiillt:

(1) / ( X I , $ 2 , - * xn, 0) = S(x1,52 7 * * * xn),

(2) f(xt 9 x2 > * . * 9 rn, Y) = 74x1 , 2 2 9 3 xn y, f(p1 (XI), p z ( x z ) , * . ., pn(xn), q(y))) fiir y > 0 .

Sind g , h, p1 , p 2 , . . . , p n , q primitiv-rekursive Funktionen mit q(0) = 0 und q ( y ) < y fur y > 0, dann ist auch f primitiv-rekursiv.

Beweis. Wir beschranken uns auf den Fall n = 1. Im wesentlichen ist der Beweis fur n > 1 derselbe. Statt x1 und p1 schreiben wir x bzw. p. Wir setzen

6(Y) = (pi 5 Y) CPi(Y) = 0 1 9

q(x,y, 0 ) = g(p'"')(z)), q ~ ( r , y , i + 1) = h(p'(y):(l+l) (XI, 4 ' ( Y ) ' ( i + I ) (Y)t P@, Yl i ) ) .

und wir definieren eine primitiv-rekursive Funktion y (x , y, i) durch

Das erwunschte Ergebnis wurde aus der Identitat

(3) f(X, Y) = 94x, Y, &Y)) folgen, da rp and 6 primitiv-rekursiv sind. Wir gehen nun daran, (3) zu beweisen: Zuerst bemerkt man, daB fur y > 0, 6(y) = 6(q(y)) + 1 gilt. Damit l&Dt sich leicht durch Induktion nach i zeigen, daB fur alle x, alle y > 0 und alle i < 6(y)

(4) P I X , Y, i ) = P(P(4, P(YL i) gilt. Sodann kann man mit (4) nachprufen, daD die Funktion &c, y, 6(y)) die induktive Definition ( l ) , (2) fur f erfullt.

6. Die GSdelisierung

Um den Variablensymbolen Godelnummern zuzuordnen, ordnen wir sie zuerst wie folgt an :

y , x,, 2 0 , XI 3 % , x2 , 2 2 , . . Sei d a m die Godelnummer einer Variablen ihre Stelle in dieser Folge. Wir ziihlen von 0 ab, z. B. ist 5 die Godelnummer von X2. Unserer Godelisierung legen wir die Paarfunktion (2, y) = 2"(2y + 1) - 1 , zugrunde. Es wurde z. B. in [4], [5] gezeigt : 1. Die Funktion (x, y) ist eine primitiv-rekursive eineindeutige Abbildyng der Menge

2: Es gibt eindeutig bestimmte 1-stellige primitiv-rekursive Funktionen I (fur links) aller geordneten Paare naturlicher Zahlen auf die naturlichen Zahlen.

und r (fur rechts), welche fur alle x, y und n die Gleichungen

W, Y)) = 2, rKx , Y)) = Y, = (W, W) erf ullen .

3. Offenbar gilt auch r(0) = 0 und r(n) c n fur n c 0.

EINE REKURSIVE UNIVERSELLE FUNKTION ~ i i ~ DIE PRIMITIV-REKURSIVEN FUNKTIONEN 53 1

In einem gegebenen Schritt der Ausfiihrung eines E'-Programms ist die Zuordnung von Werten zu den Variablen eine unendliche Folge natiirlicher Zahlen, deren Glieder hochstens in endlich vielen Fallen nicht gleich 0 sind. Wir nennen solche Folgen Werte- folgen. Wertefolgen konnen wir folgendermaflen durch Godelnummern darstellen :

Schreibweise f u r die Verke t tung . Sei a ein Gegenstand und @ eine Folge (end- lich oder unendlich). Die Verkettung der Folge, deren einziges Glied a ist, mit der Folge @ bezeichnen wir mit (a,@). (Der Gegenstand sol1 dann links stehen.)

I n d u k t i v e Def in i t ion de r Godelnummer e iner Wertefolge. (SoJche Folgen konnen selbstversthndlich eindeutig aus der Folge 0, 0, 0, . . , durch wiederholte An- wendungen der ebenerwahnten Verkettung aufgebaut werden.)

a) Die aadelnummer der Folge O,O, 0, . . . ist 0. b) Sei a eine natiirliche Zahl und @ eine Wertefolge mit Godelnummer b, dann be-

kommt die Verkettung (a, @) die Godelnummer (a, b).

Es lLDt sich auf Grund der oben enviihnten Eigensbhaften der Paarfunktion Ieicht beweisen, daD unsere Zuordnung der Godelnummern zu den Wertefolgen eine einein- deutige Abbildung ist, welche die Menge aller Wertefolgen auf die Menge aller natiir- lichen Zahlen abbildet. Allgemein hat die Folge a,, a,, . . ., u,,, O , O , . . . die Godel- nummer (a,, (a,, (. . . ,(a,,, 0) . . .))).

Wir wollen Programmabschnitte und Abschnittsfolgen durch Godelnummern dar- stellen. Im Gegensatz zu der Zuordnung von werten zu den Variablen handelt es sich hier urn Folgen, die wirklich endlich sind. Dafiir fiihren wir die 2-stellige Funktion [x, y] = (x, y) + 1 ein;l)

Es liiDt sich leicht beweisen: i) Die Funktion [x, y] ist eine primitiv-rekursive eineindeutige Abbildung der Menge

aller geordneten Paare natiirlicher Zahlen auf die positiven natiirlichen Zahlen. ii) Definieren wir die Funktionen I(n), e(n) als I ( n ) = I(n 2 1) und e(n) = r(n 2 l),

dann gilt I ( 0 ) = e(0) = 0 und, fur alle natiiqlichen Zahlen z, y und alle positiven natiirlichen Zahlen n

A", 211) = x, e([% Yl) = 9 , n = [W, e(41, I ( n ) < n und e(n) < n .

Jede Abschnittsfolge, die nicht gleich der leeren Folge 0 ist, liil3t sich eindeutig aus B durch wiederholte Anwendungen der friiher erwahnten Verkettung aufbauen. Zum Beispiel besitzt die Abschnittsfolge P = P o , P, den kanonischen Aufbau (Po, (P1 ,0)). Die folgende Definition bezieht sich auf diesen kanonischen Aufbau. Wenn die Ab- schnittsfolge P mit (Q, R ) bezeichnet wird, meinen wir, daD Q ein Programmabschnitt ist, und daD die Abschnittsfolge & kanonischen Aufbau hat.

S imul t ane i n d u k t i v e Def in i t ion de r Godelnummer eines L ' -Programm- a b s c h n i t t s u n d d e r Godelnummer einer L ' -Abschni t tsfolge.

1. Die Cijdelnummer der leeren Abschnittsfolge 0 ist 0.

*

I ) Diese Funktion erweist sich ale ein gutes Werkzeug, urn endliche Folgen von natiirlichen Zah- len zu Godelisieren. Die Gadelnummer der endlichen Folge a,, a , , az, . . . , a, konnte man als [a,, [a,, [az. . . . , [a,, 0) . , .]I] definieren. In unserer Arbeit ist diese Abbildung etwas verborgen. 341

532 H. LEVITZ UND w. NICHOLS

2. Ein Programmabschnitt, dessen einziger Term ein Befehl V c 0 ist, hat die Godel- nummer (0, a) , wobei a die Godelnummer der Variablen V ist.

3. Ein Programmabschnitt, dessen einziger Term ein Befehl V c V + 1 ist, hat die Godelnummer (1, a ) , wobei a die Godelnummer der Variablen V ist.

4. Ein Programmabschnitt der Form LOOP V , P, END hat die Godelnummer ( a + 2, b) wobei a die Godelnummerder Variablen V und b die Godelnummer der Abschnittsfolge fur das Programm P ist.

5 . Eine Abschnittsfolge, die eine Verkettung ( Q , P ) ist, hat die Godelnummer [a, b], wobei a die Godelnummer des Programmabschnitts Q und b die Godelnummer der Abschnittsfolge P ist.

Hat die Abschnittsfolge P als Glieder die Programmabschnitte P o , PI, P2, . . . , P,, mit den Godelnummern p o , p l , p 2 , . . ., p,,, dann hat P die Godelnummer

Auf Grund der friiher erwiihnten Eigenschaften der Funktionen (x, y) und [x, y] laBt sich beweisen :

i) Die Zuordnung von Godelnummern zu Programmabschnitten bildet eine einein- deutige Abbildung der Menge aller Programmabschnitte auf die natiirlichen Zahlen.

ii) Die Zuordnung von Godelnummern zu den Abschnittsfolgen bildet eine einein- deutige Abbildung der Menge aller Abschnittsfolgen auf die natiirlichen Zahlen.

k" 3 [PI 9 [P2 > . . . > [P. 7 01 . * .Ill .

6. Spezielle Funktionen

Schreibweise. Von diesem Punkt an finden wir es manchmal bequem, die Klam- mern um die Argumentestellen der Funktionen wegzulassen. Zum Beispiel schreiben wir rX anstatt r ( X ) und IrX anstatt I ( r ( X ) ) . GroBe lateinische Buchstaben beziehen sich immer auf natiirliche Zahlen, kleine lateinische und griechische Buchstaben auf finit-stellige Funktionen von naturlichen Zahlen zu natiirlichen Zahlen.

Defini t ion. Es sei z ( W , K , X) die Godelnummer der Wertefolge (= Folge natiir- licher Zahlen mit hochstens endlich vielen Gliedern ungleich Null), die sich ergibt, wenn in der Wertefolge, deren Godelnummer W ist, die Nummer in der K-ten Stelle durch X ersetzt wird. (Hier ist das Symbol z eine Abkiirzung fur ,,Zuordnung" und W eine Abkiirzung fur ,,Wertefolge".)

Hi l f ssa tz 6.1. Die Funktion z ( W , K , X ) is t primitiv-relcursiv. Be weis. Zuerst bemerkt man, daB diese Funktion die Gleichungen

z ( W , O , X ) = ( X , r W ) , z(W, K + 1, X ) = ( Z W , z ( r W , K , X ) ) erfiillt. Sodann ergibt sich aus Hilfssatz 4.1, daB z primitiv-rekursiv ist.

Defini t ion. In dieser Definition benutzen wir das Symbol A (bzw. 8) fur die Ab- schnittsfolge, deren Godelnummer A (bzw. B) ist. Es sei v (A , B ) die Godelnummer dcr Abschnittsfolge, die sich ergibt, wenn man die Abschnittsfolge A mit der Abschnitts- folge B verkettet ( A links von B). (Hier dient das Symbol v als Abkiirzung fur Ver- kettung .)

EINE REKURSIVE UNIVERSELLE FUNKTION FUR DIE PRIMITIV-REKURSIVEN FUNRTIONEN 533

Godelnummer der niichsten Wertefolge fur die Variablen

Hi l f s sa t z 6.2. Die Funktion v(A, B) ist primitiv-rekursiv.

Beweis. Zuerst bemerkt man, dal3 diese Funktion die folgenden Gleichungen erfullt:

w(0,B) = B , v ( A , B ) = [ ; t l , v (@A,B) ] fur A > 0 .

Sodann ergibt sich aus Hilfssatz 4.1, dal3 v primitiv-rekursiv ist.

plare von A mit B verkettet, ist vK(A, B) . Zusatz . Die Godelnummer der Abschnittsfolge, die sich ergibt, wenn man K Exem-

Godelnummer der niichsten Abschnittsfolge

7. Die Haaptergebnisse

Wir nehmen an, dal3 ein Programm und eine Anfangswertefolge fur die Werte der Variablen gegeben ist. Wir wollen den Lauf der durch den Kontrollalgorithmus fest- gelegten Berechnung mittels Godelnummern beschreiben. Sei P die Godelnummer der Abschnittsfolge des Programms und X die Godelnummer der Anfangswertefolge fur die Variablen. In einem gegebenem Schritt handelt es sich dann darum, die Godel- nummer W der neuen Wertefolge fur die Variablen und die Godelnummer A der neuen Abschnittsfolge auszurechnen. Das am weitesten links stehende Glied dieser Abschnitts- folge hat die Godelnummer AA. Was fur eine Art Programmabschnitt dieses Glied bil- det, konnen wir von der Zahl ZAA erfahren. Es ist ein Zuordnungsabschnitt oder ein Loopabschnitt, je nachdem, ob ZAA 1 oder ZA.4 > 1. Weitere wichtige Information ist in der Tafel unten zu finden. Mit W , bezeichnen wir den Wert der Variablen, die an der N-ten Stelle steht, d. h. die Godelnummer N hat. W , ist eine primitiv-rekursive Funktion von W und N, weil W N =.ZrNW gilt.

Typ des linken Pro- gramm- abschnitts

Fall Godel- nummer der betreffenden Variablen

ZAA = 0

1AA = 1

ZAA > 1

Zuordnung v c o Zuordnung V t V + 1 Loop

rAA

rAA

A A - 2

Die beiden Grol3en W und A konnen ir weiter in eine einzelne Zahl ( W , A ) ver- einigen. Diese Zahl konnen wir als den Zustand der Berechnung in dem gegebenen Schritt betrachten. Es liegt nahe, eine Funktion a(X, P, N ) = <W, A ) zu betrachten, die den Zustand im N-ten Schritt angibt. (Diese Funktion ist wohl-definiert, weil mir unsere Godelisierung durch bijektive Abbildungen geleistet haben.)

Mittels der obenstehenden Tafel kommen wir zu der folgenden induktiven Beschrei- bung der Funktion a(X, P , N ) :

(5 )

(6)

U P , k 0) = ( X , P ) 7

<z(W, rA-4, O ) , @ A ) ,

( W , vwII.A-z(rAA, @ A ) ) ,

falls ZAA = 0 , a(X, P , N + 1 ) = ( z ( W , r l A , WldA + l), @ A ) , falls ZAA = 1 ,

falls ZAA > 1 .

534 H. LEVITZ UND W. NICHOLS

Aus der urspriinglichen Definition von o konnen wir entnehmen, da13 W = l o ( X , P , N ) und A = r a ( X , P , N ) gilt. Wenn wir diese Ausdrucke fur W bzw. A in (6) einsetzen, konnen wir sofort sehen, da13 diese induktive Beschreibung eine primitiv-rekursive Be- schreibung ist. Deshalb ist a primitiv-rekursiv.

Defini t ion. Es sei u ( X , P) die Godelnummer der Wertefolge von Werten der Variablen am Ende der Berechnung, wenn man mit einem Programm arbeitet, dessen Abschnittsfolge die Godelnummer P hat, und mit der Anfangswertefolge mit der Godel- nummer X beginnt. (Hier ist u eine Abkurzung fur ,,universell". Die Angemessenheit dieses Namens wird spiiter besprochen.)

S a t z 7.1 . Die Funktion u ( X , P ) ist rekursiv.

Beweis. Wir setzen wie friiher o ( X , P, N ) = ( W , A ) . Dann ist u ( X , P) der Wert von W , wenn die betreffende Berechnung aufhort, d. h. der Wert von W , wenn A = 0 gilt, also

u ( X , P ) = lO(X, P, ( p N ) [ ra (X , P , N ) = 01). ' Damit haben wir einen Aufbau mittels primitiver Rekursion und der p Operation, welcher uns zeigt, daB u ( X , P) eine rekursive Funktion ist.

Bemerkung 7.2. Die Funktion ( p N ) [ ro (X , P , N ) = 01, die in dem obigem Beweis auftritt, bezeichnen wir mit h ( X , P) . Offenbar ist h ( X , P ) rekursiv. Es wird sich spiiter herausstellen, daD u ( X , P) und deshalb h ( X , P) keine primitiv-rekursiven Funktionen sind. h ( X , P) ist eine interessante Funktion, weil sie anzeigt, wie viele Schritte eine Berechnung hat.

Wie im folgenden gezeigt wird, 15Bt sich eine universelleFunktion uk(x1, x , , . . . , x k ,P) fur die k-stelligen primitiv-rekursiven Funktionen aus zwei einfachen primitiv-rekursi- ven Funktionen und der Funktion u ( X , P ) aufbauen. In diesem Sinn konnen wir die Funktion u ( X , P ) als eine ,,universelle" Funktion fur die Menge aller finit-stelligen primitiv-rekursiven Funktionen betrachten.

Sei f eine k-stellige Funktion und P eine Godelnummer der Abschnittsfolge eines Programms, welches die Funktion f bestimmt. Seien X , , X , , . . . , X , natiirliche Zah- len. Nehmen wir an, da13 wir den Wert f ( X , , X,, . . . , X, ) berechnen wollen. Die An- fangswertefolge wiirde die Godelnummer (XI , ( X , , , . . , ( x k , 0) . . .)) haben. Diese kiirzen wir mit ( X , , X , , . . . , xk, 0) ab. Am Ende der Berechnung wurde die Werte- folge die Godelnummer u ( ( X , , X , , . . . , x k , 0 ) , P ) haben. Zu diesem Zeitpunkt ist der Wert der Ausgangsvariablenlu((X, , X , , . . . , X,, 0) , P). Somit haben wir gezeigt, daB

(8) f(xl 9 x 2 9 * * * x k ) = ~ u ( ( X , , x 2 * * * 9 xk, o), p) gilt. Umgekehrt ist der rechte Teil der Gleichung (8) fur ein festes P immer eine primitiv- rekursive Funktion, weil jedes P eine Godelnummer einer Abschnittsfolge eines Pro- gramms ist und weil die durch Loopprogramme festgelegten Funktionen immer primitiv rekursiv sind. Somit haben wir den nun folgenden Satz gezeigt:

S a t z 7.3. Die k + 1-stellige Funktionu,(X, , X , , . . . , X, , P ) = l u ( ( X , , X , , . . . , X , ,O) , P ) , ist eine rekursive universe& Funktion fur die Menge alEer k-stelligen primitiv-rekursiven Funktionen.

S a t z 7.4. Die Funktion u l ( X , Y ) ist eine rekursive, aber keine primitiv-rekursive Funktion.

EINE REKURSIVE UNIVERSELLE FUNKTION FUR DIE PRIMITIV-REKURSIVEN FUNKTIONEN 535

Beweis (PBTER). Ware u l ( X , Y) primitiv-rekursiv, so wiirde auch v ( X ) = = u , ( X , X ) + 1 primitiv-rekursiv sein. D a m gilt fur alle X , v(X) = u , (X , N ) fur ein gewisses N . Nun haben wir die beiden widerspriichlichen Aussagen v ( N ) = ul(N, N ) und v ( N ) = u l ( N , N ) + 1.

S a t z 7.6. u ( X , Y ) ist eine rekursive, aber keine primitiv-rekursive Funktion. Bew eis. Wiire u ( X , Y) primitiv-rekursiv, so ware auch u , ( X , Y) primitiv-rekursiv.

S a t z 7.6. Esgibt ein k + 8-stelliges pr imi t i v - rekurs i vespr~ i~ t Tk(x l ,x2, . . . ,xk,P,Z) und eine I-steltige primitiv-rekursive Funktion g rnit der folgenden Eigenschaft: Die k-stel- l igen primitiv-rekursiven Funktionen sind genau die jenigen, welch die Form g ( p 2 ) [ T k ( X 1 , X 2 , . . . , xk, P,Z)] fiir ein P haben.

Beweis. Sei Ti+l das herkommliche Kleenesche T-Priidikat [3]. Wegen des Kleene- schen Normalformsatzes gibt es eine primitiv-rekursive Funktion g und ein N , so daR

%(XI 9 x 2 , . .) 3 p, = g(pue) [TL+l(xl, x 2 , * * -, x k , p, N , z)l gilt. Jetzt konnen wir unser eigenes T-Prildikat folgendermaBen definieren :

Tk(x,, x,, . . Y xk, p, 2) c-, Ti+i(Xi, x2, * . - 9 x k , p, fl, 2). Sa t z 7.7. Es existiert eine I-steellige rekursive Funktion, die alte I-stelligen primitiv-

Beweis. Sei v ( X ) eine gegebene primitiv-rekursive Funktion. Es gibt ein P, so daB rekursiven Funktionen mjorisiert.

f u r alle X , u , ( X , P ) = v ( X ) gilt. Daraus folgt fur X 2_ P: X

Y=O c % ( X , Y ) 2 U l ( X , P) = v ( X ) .

X

Y=O Die Funktion c u , ( X , Y) ist die gesuchte rekursive Funktion.

Literatur

[I] ACKERMANN, W., Zum Hilbertschen Aufbau der reellen Zahlen. Math. Ann. 93 (1928), 1-36. [2] BRAINERD, W., and L. LANDWEBER, Theory of Computation. Wiley, New York 1974. [3] CUTLAND, N., Computability: An Introduction to Recursive Function Theory. Cambridge

[4] DAVIS, M., and E. WEYUKER, Computability, Complexity and Languages. Academic Press,

[5 ] HERMES, H., Aufzilhlbarkeit, Entscheidbarkeit und Berechenbarkeit. Springer-Verlag, Berlin-

[6] MEYER, A., and D. RITCHIE, Computational Complexity and Program Structure. IBM Research

[7] PETER, R., Konstruktion nicht rekursiver Funktionen. Math. Ann. 111 (1935), 42 - 60.

University Press, Cambridge 1980.

New York 1983.

Gottingen-Heidelberg 1961.

Paper RC-1817, Yorktown Heights: IBM Watson Research Center, 1967.

Hilbert Levitz Department of Computer Science Florida State University Tallahassee, Florida 32306, U.S.A.

Warren Nichols Department of Mathematics Florida State University Tallahassee, Florida 32306, U.S.A.

(Eingegangen am 20. September 1986)