Über die mehrfache Rekursion

Uber die mehrfache Rekursion. Von

R6zsa P6ter in Budapest.

Einleitung.

I.

1. In zwei friiheren Arbeiten 1) (die ich hier als bekannt voraussetzen werde) habe ich gewisse Eigenschaften der rekursiven Funkt ionen behandelt. Unter rekursiven Funktionen werden diejenigen zahlentheoretischen Fnnkt ionen verstanden, die yon den Funktionen 0 und n + 1 ausgehend du tch eine endliche Ket te von Substitutionen und Rekursionen entstehen. Der Begriff der Rekursion l~iBt sich auf verschiedene Weisen abgrenzen. I n , , r ' und , , I I " habe ich reich auf die ,,einfache" Rekursion besehr/inlrt, wobei die Rekursion blol~ nach einer Variablen liiuft, wie z. B. bei der bekannten Definition der Summe:

a + O = a ,

a +4- (n-4- 1) ~- ( a + n) + 1.

Wie bekannt~), kSnnen siimtliehe Funktionen, die in der elementaren Zahlentheorie eine Rolle spielen, dutch einfache Rekursionen definiert werden.

t) R. P6ter (Politzer). ~ber den Zusammenhang der versehiedenen Begriffe der rekursiven Funktion, Math. Annalen 110 (1934), S. 612-632; und R. P6ter, Kons$ruktion nichtrekursiver Funktionen, Math. Annalen 111 (1935), S. 42--60; zitiert im folgenden als ,,I" bzw. ,,I[".

~) Th. Skolem, Begrttndung der elementaren Arithmetik durch die rekurrJeronde Denkweise, Videuskapsselskapets Skrifter (Kristiania) I. Mat.-Naturv. El. (1923), :Nr. 6; K. GOdel, ~ber formal unentscheidbare S~tze der Principia Mathematica und verwandter Systeme I., Monatshefte fiir Math. und Phys. 88 (1981), S. 173--198. In vorliegender Arbeit wird (auGer yon a + b, a. b, a 5) yon folgenden Funktionen benutzt, dal~ sie dureh einfache Rekursionen definiert werden kfnnen:

/ 0, falls a -~ b, a - - b -.~ [ a - - b sonst;

O, falls a -~- O, sga ~ (1 sonst; - - [ 1, fa l l s a ~ O, s g a = ~ 0 s o n s t ;

2, falls n - - 0, ~0 n sonst die der Gr6Be nach n-re ungerade Primzah] ;

/ 0, falls a ~--- 0 , (a) ~n sonst der Exponent yon Pn in der Primfaktorendarstellung yon a;

490 I~. P~ter.

Jedoch gibt es auch verhiiltnismiil3ig einfache zahlentheoretisehe Funktionen, die sich nut dutch ,,mehrfache" Rel<ursionen definieren lassea, d.h. dutch solche, wobei die Rekursion gleichzeitig naeh mehreren Variablen liiuft. Eine solche Funktion ist z.B. des Aekermannsche Beispiel ~) ~ (n), das ist die Funktion, welehe den Weft darstellt, den ftir die Argumente n, n die n-re der Operationen ergibt, die man ausgehend yon der Addition dutch sukzessive Iterationen gewinnt; anch de s Diagonalverfahren, angewandt auf die dutch einfache Rekursionen deft- nierten Funktionen, fiihrt zu einer solehen Funktion. (Siehe , , I I" , Nr. 12, S. 53). Es erscheint demnach lohnend, aueh die mehrfachen Rekursionen zu untersuehen.

2. Die Beschriinkung auf einfache Rekursionen wiire im Grunde genommen sehr willkiirlieh. Eine Funktion wird n~mlieh dutch Rekursion definiert, wenn ihr Weft an einer gegebenen Stelle aus Werten aufgebaut wird, we]che die Funktion an vorherigen Stel]en angenommen hat . Handelt es sich z.B. um eine zweistellige Funktion ~ (m, n), so sind die in Frage kommenden Stellen:

(0, 0), (0,1), (0, 2) . . . . . (0, n), (o, n + 1) . . . .

(1, 0), (1, 1), (1, 2) . . . . , (1, n), (1, n + 1), . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ . . . . .

(m, o), (m, 1), (m, 2), . . . , ( ~ , n), (m, n + 1), . . .

(m-~ 1,0), ( m + 1, 1), (m~- 1 , 2 ) , . . . , ( m + 1, n), (m + 1 , n + 1 ) , . . .

und es ist sehr willktirlich, nut jene Stellen als vor (m + 1, n -~-1) stehend zu betrachten, welche in friiheren R e i h e n vorkommen. Vie] natiirlieher ist jene Anordnung, wobei auch (m + 1, 0) (m + 1,1), . . . , (m + 1, n) vor (m + 1, n + 1) stehen; und diese Betrachtung fiihrt zu einer Rekursion, bei welcher ~ (m + 1, n-t-1) aus endlieh vielen solcher Werte der Funk-tion ~ aufgebaut wird, we des erste Argument ~ m, das zweite betiebig, oder das erste Argument m -]- 1, das zweite ~_~ n ist , Des ist aber eine zweifaehe Rekursion.

Bei gegebenem m u n d n l~il3t sich naeh einer solchen Definition q ~ ( m , n ) in endlich vie]en Sc.hritten auf ~(0,0) zttriicl~iihren; ist a l so noeh ~ (0, 0) gegeben, so ist des eine intuitionistiseh einwandf~eie Defini- tion der Funktion ~ (m, n).

$ 1

ferner wird benutzt, dal3 mit ~ (n, a t , �9 . . , at) auch ~ a . (x , a t . . . . , at) u a d

/ I ~ (x, a I . . . . , ar durch einfache Rekursionen definiert werden kSnnen. Diese

Tatsachen wurden auch in ,,I", S. 616--619 bewiesen. 3) W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, M~t.h. Annalen 99

~1928), S. 118--133.

Mehrfache Rekursion. 491

Im aUgemeinen, wenn q~ (n , , . . . , nk, a , , . . . , an) durch eine k-fache Rekursion naeh n~, n 2 , . . . , ne definiert wird, werde ich sagen, dab eine Stelle (m, . . . , ink, b,, �9 �9 b~) der Stelle (n, . . . . . nk, a, . . . . . a,) voraageht, wenn es ein i, 1 ~ i ~ k , gibt, so dal~ m 1 = n , . . . . . m ~ _ l - - n i -1 , m~ < n~.

3. Eine weitere Bedeutung gewinnt die mehrfache Rekursion dureh die Tatsache, daB sich siimtliche mehrfaehen Rekursionen auf eiufaehe zuriickfiihren lassen, falls auch die Hilbertsehe zweite S tu fe ' ) (auf der nicht nut zahlentheoretisehe Funktionen, sondern aueh Funktiousfunktionen dutch Rekursion nach einer Zahleuvariablen definiert werden kSnnen) zugelassen wird.

Sei z .B . die Definition von 90 (m, n):

/ ~(0,n) = l, . ~(m + 1,0) = 1,

+ + = + +

(ich werde beweisen, dab sieh die allgemeine zweifache Rekursion auf diese Form zuriickftihren lii6t), dann definiere ich die Funktionsfunktion 6) r (m, n, / (x)) durch folgencle einfache Rekursion:

sei ferner

{ ~ ( O , n ) = 1, (m + 1, n) = ~ (m, n, ~ (m, x));

das is$ wiederum eine einfache Rekursion. Nun ist

(m, n) = ~ (m, n).

Dies gilt niimlich fiir m = 0; ferner ist ftir m ~ 0

~(m,O) = r 1,O,~o(m-- I ,x)) = I = 9~(m,O),

daher gilt die Behauptung fiir die Stellen (m, n), bei denen m. n = 0 ist. Angenommen, dab sie schon fiir die Vorgiinger der Stelle (m + 1, n + 1) besteht, so ist ideatisch in

v; (m,~) = ~(m,x),

~) D. h. jener Spezialfall des ~llgemeinen Hilbert~ohen Rekursionsbegriffes (D. Hilbert~ Cber das UnPndliche, Math. Annalen 95 (1916), S. 161~190, insbe- "sondere S. 186), wobei der Variableutyp der duroh Rekursion definierten Ausdrficke hSchstens yon der HShe 2 ist. (Der Ausdruok ,,Funktion zweiter Stufe" Iiir eine Funktion yon Funktionen stammt yon Frege).

5) Der ~nd~x �9 yon r weis~ darauf bin, dab ~ yon der Funktion ] und nicht 9on x abh~ngt.

492 R. Peter.

also v / (m- / - 1 ,n ~- 1) = Cx(m, n -~ 1, ~ ( m , x ) )

doch ist nach Voraussetzung

r e(m,x)) = r n, ~ (m, x)) = ~(m + l,n) = ~(m + i,n),

und daher

,p(,~ + 1 , , ~ + 1 ) = ~(m,,~, ~ ( - ~ , ~ ( , n , , ~ , ~ ( ,~ + 1, n))), ~ ( m + 1 ,n))

= ~ (m + 1, n ~- 1),

also gilt die Behaup tung auch f i i r die Stelle (m ~- 1, n ~- 1); demzufolge

gilt sie allgemein. Auf die nahere U n t e r s u c h u n g des Zusammenhanges der Hi lber t schen

hSheren Stufen mi t der m e h r f a c h e n Rekurs ion will ich in einer sp~iteren

Arbei t zur i ickkommen. 4. Da die Anordnung der S te l l en (m, n) yore Typus co ~ ist, b e ruh t

der Beweis tier Nr . 3. auf einer t r ans f i n i t en Induk t ion 6) v o m T y p u s eo ~. Die zweifache Rekurs ion kaun a u c h als ein Spezialfall der t ransf in i ten Rekurs ion v o m Typus w ~ aufgefal~t werden. Eine solche t ransf in i te

Relmrsion einer zweistelligen zah len theore t i schen Funk t ion kann m a n

ni~mlich wie folgt schreiben:

~ ( m - i - l , n q - l ) = (P(m,n, cp(O,O),~(O,t) . . . . ; ~ ( 1 , O ) , ~ p ( 1 , 1 ) , . . . ; . . . ; q~(m,O), q~ (re, l ) . . . . ; (y (m H- 1,0), r 1,1), . . . ,

q~ (~ + 1, n)) = qD~(m,n, cp(O,x); (p(1,x); . . . ; (p (m,x) ; g ~ ( m + 1,0),

~ ( m -Jr 1 , 1 ) , . . . , q~ (m--[- 1,n)),

6) Die transfinite Induktion yore Typus co ~ kann ohne Anwendung mengen- theoretischer Begriffe wie folgt formuliert werden. Eine Aussage gilt fiir 8lie Stellen (m, n). wenu sie erstens filr die Stelle (0, 0) gilt und wenn sie zweitens fiir die yon (0, 0) verschiedene Stelle (m, n) gilt, sofern ale ffir alle Vorg~nger dieser Stelle gilt. Dies kann bekanntlich auch durch gewShnliche vol]st~ndige Induktion bewiesen werdcn: man beweist zun/ichst durch vollst~ndige lnduktion in bezug auf n, dal} die frag|iche Aussage fiir die Stellen (0, n) gilt; dann ebenfalls dutch vollst~ndige Induktion in bezug auf n, dal3 die Aussage fiir die Stelle (m, ~).gilt, sofern sie fiir alle Vorg~nger der Stelle (m, 0) gtiltig :ist; ~ hieraus ergibt sich dutch vo]lst~,ndige Induktion in bezug auf m, dab die~ Aussage, bei beliebigem m, ftir die Vorganger der Stelle (m, 0) giiltig ist, daher gilt sie fiir alle Ste]len iiberhaupt. Ebenso kann man ftir jedes k die transfinite Induktion yore Typus co k (die in entsprechender Weise formuliert werden kann) e u f die gCwShnliclie vol]st/tndige Induktion zuriick/iihren. Icb bemerke noch, daI~ ioh in dieser Arbeit immer nttr folgonden Spezialfall der transfiniten Induktion yore Typus ~o k anwende: Eino Aussage gilt f-fir alle Stellen (n . . . . . n~),. wenu, r erstens ffir alle dm Stellen ( ~ . . . . . n~)~gilr be~ denen n �9 ..:. n~ ~ 0 ist; undo- wenzl-sie zweitens ftir die S~;el~e (a~-~-1 . . . . , n ~ - 1 ) gilt, sofern sie for atle Vorganger dieser ~telle gilt.


und ~hnlich :

T ( m + l , 0 ) = hv,(m,~(0, x); ~0(1,x); . . . ; q~(m,z)).

Um auf eine finite Definition zu kommea, beschranke ich mich auf solche Funktionsfunktionen q~ (m, n, gl (x) . . . . , g,,, + 1 (x), a o, a l , . . . , a,) und ~ (m, g, (x),. . . , g~+ 1 (x)), die aus m, n, gl(x) . . . . , r 1 (x), und bei r174 noch a0, al . . . . . a , , und gewissen schon eingefiihrten Funktionen durch eine endliche Kedge yon Substitutionen aufgebaut werden. Auflerdem mui~ der Weft ~ (0,0) angegeben werden, ferner 9 (0, n + 1) in Abhiingig- keit yon den vorangehenden Werten; beides zusammen bedeutet eine einfache Rekursion fiir ~ (0, n), kann also in eine Gleichung yon der Form

~o (0, n) = ~ (n) zuzammengefaBt werden.

Es kSnnen auch Parameter bo, b l , . . . , b, auftreten. Diese lassen sieh genau so, wie das in ,,I" (Nr. 11, S. 619--620) bei der einfachen Rekursion gezeigt wurde, dutch einen einzigen Parameter a = Tobo �9 p~t. . , p br vertreten.

Die angegebene Definition ist eine Wertverlaufsrekursion in einem entsprechenden Sinne wie in ,,I" (l~r. ]2, S. 620--621). Sie kann iihnlich, wie bei der einfachen Rekursion in ,,I", aber in zwei Schritten, auf eine einfachere Form zuriickgefiihrt werden: die dort dargelegte Methode ist erst auf die eine, dann auf die ander~. Variable anzuwenden. Man erh~lt so eine Rekursion, in der zum Aufbau eines Funktionswertes bloi] die Werte der unmittelbar vorangehenden Reihe, und in derselben Reihe blol~ der Weft an der unmittelbar vorangehenden Stelle benutzt werden. Man kann sich also auf zweifache Rekursionen der folgenden :Form beschr~nken:

~o (0, n, a) ---- ~ (n, a) ~o (m + 1,0, a) ---- ~P| q~(m,x, y)) 9 ( m + 1, n + 1,a) = # ~ , , ( m , n , a , ~ ( m , x , y ) , 9 ( m + 1, n,y)).

Ahnlich geniigt es bei der k-fachen Rekursion (die als der finite Spezialfall einer transfiniten Rekursion vom Typus o~ ~ aufgefal3t werden- kann) folgende Form zu betraehten:

{ r ~-- zx...x k(n, . . . . , n , , n t + 2 , . . . , n ~ , a , 9(nx, z 1 . . . . ,zk), 9 ( h i + l ,

D1 n~,xl, . . . , x ~ - l ) , . . . , 9 ( n i + 1 . . . . . n z - x + l , nz, x l , . . . , x k - z + l ) ),

(I = O, 1 ,2 , . . . , k )

(ftir l-----0 soll die reehte Seite a]s r (n 2 . . . . , nk, a) gelesen werden, wobei also r keine ~'unktionsfunktion, sondern eine zahlentheoretische Funk*ion ist).

Mathematischo Annalen. 118. 32

494 R. Pfiter.

II.

5. Ich werde die Funktionen, die yon den Ausgangsfuuktionen 0 und n + 1 ausgehend dutch eine endliche Kegte von Substitutionen und k- faehen Rekursionen der Form D 1 entstehen, k-rekursiv nennen. S t a r t ,,1-rekursiv" werde ich auch ,,rekursiv" sagen.

In w 1 werde ich die Definition D 1 durch folgeade ,,normierte F o r m " ersetzen:

{9( n , . . . , n~, a) = 1, falls n 1.n 2 . . . n~ = 0,

D~ ~ (n~ + 1 . . . . , n~ + 1, a) = r ~(n~ . . . . , nk, a, ~ (n 1, xl . . . . , xk),

q~ (nl + 1, n~, ~ , . . . , xk-~), �9 ~ (n, + 1, . . . , n~_, + 1, n~, ~ ) ) ,

wobei also alle ,,Anfangswerte" durch 1 ersetzt wurclen.

Dana werde ich i m w 2 die Einschachtelungen in D 2 teilweise elimi- nieren, indem ich zun~iehst D~ auf eine solche Form zuriick[iihre, in weleher in r (n~ + 1 . . . . , nk-~ + 1, n~, x~) fiix x~ blofl a eingesetzt wird. Diese Zuriickfiihrung kSnnte auch dutch die Methode vollzogen werden, die ich in , ,I" bei den einfachen Rekursionea angewanclt habe, doeh k a n n diese Methode nach einer Bemerkung yon L. Kalmlr wesentlieh verein- (acht. werden dadurch, dab die dort auftretenden kombinatorischen HiHsmittel dutch eine hnordauag mittels der Primfaktorenzerlegung ersetzt werdenT). Diese Zurttckftthrung ermfglieht dana die vollst~ndige Aussehaltung der Parameter; nach unwesentlichen Umformungen k o m m t man so zu der ,,primitiven" Form der ]c-fachen Rekursion:

~0 ( n , . . . , n~) = 1, falls hi, n2 . . . . , n~ = 0, (n~ + 1 . . . . , nk + 1) = ~ (n~ . . . . . ~ , ~, ( n , . . . , n~), . . . . ~ ( , , . . . , n~)) ,

wo flit i---- 1 ,2 . . . . . k, D~

~, (nl . . . . . n~) = ~ ( ~ + L . . . , ~ i - 1 + 1, n,,/~(# ( n , . . . , ~ , ~ (n, + 1 . . . . .

~ - ~ + ~, ~ ) ) , ~ ( ~ ( , , , . . . , ~ , v ( ~ + ~ , . . . , ~ - ~ + ~, ~ ) ) . . . . ,

~:)_,( ,~ . . . . , ,~, ~ ( ~ + ~ . . . . . ~ _ ~ + ~, ~ ) ) ) ,

wobei ~ ) ftir i = 1, 2, . . . , k -- 1, j = 1, 2 . . . . . k - - i sehon eingef~ihr~e Funktionen sind. In diesem Rekursionsschema treten nunmehr blol~ zweifache Einschaeh~elungen auf.

Da~ die Einsehachtelungen nieht ganz ausgesehaltet werden kSnaen, zeige ioh in w 3. Hier betrachte ich niimlieh denjenigen Spezialfall y o n D~, we keine Einschaehtelungen vorkommen. Es stellt sich heraus, da~ sich in diesem Fall die Funktion ~ aus gewissen sehon eingefiihrten Funkt ionen

7) Siehe: R. P~ter, A rekurziv fiiggv~nyek elm~let~hez, Matematikai ~s Fizikai Lapok 42 (1935), deutscher Auszug auf S, 25--28.


(die auf der rechten Seite der Definition yon ~ figurieren) uad aus rekursivea Funktionen durch Substitutionen aufbauen l~l~t. Die k-fache nicht eingeschachtelte Rekursion fiihrt daher aus der Klasse der 1-rekursiven Funktionen nicht heraus. Da nun die allgemeine k-faehe Rekursion nach dem Satz yon Ackermann schon fiir k = 2 tiber die Klasse der 1- rekursiven Funktionen hinausfiihrt, so kann die Einschachtelung bei der allgemeinen k-fachen Rekursion flit kein k =~ 1 vermieden werden.

In w 4 verallgemeinere ich den genannten Ackermannschen Satz da- bin, dab die ( k + 1)-fache Rekursion fiir jedes k fiber die Klasse der k- rekursiven Funktionen hinausffihrt. Der Beweis ist ~ihnlich, wie in ,,II", w 2, S. 49--53: ich zi~hle n~imlich die k-rekursivea Funktionen mit Hilfe einer Funktion ab, die dutch eine einzige (k + 1)-fache Rekursion deft- niert wird, woraus sich die Behauptung mittels des Diagonalverfahrens ergibt. Es w~e nicht uninteressant, dieselbe auch rnit Hilfe einer entsprechenden Verallgemeinerung der Ackermannschen Funktion (sozusagen dutch ein transfinites Iterationsverfahren) zu beweisen.

Das Zwischenergebnis tvonw 4, dab n~mlich jede k-rekursive Funk- tion mit Hilfe yon 1-rekursiven l~unktionen dutch eine einzige (k-f-])- fache Rekursion definiert werden kann, verwende ich in w 5, um eine beliebige k-rekursive Funktion ~ (n~, . . . , n,) mittels einer geeigneten 1-rekursiven Funktion~r (m) und einer 1-rekursiven Beziehung B (m, n , . . . , n~) in der Form

. . . . , , , , ) = , , , . . . . . , , , ) ) )

darzustellen; hier bedeutet /x=(A (x)) die kleinste Zahl x, ffir die A (x) besteht. (In dieser Arbeit wird das Zeichen /~ (A (x)) ausschliel~lich in solchen Fiillen benutzt, wo zugleich ein Verfahren zur effektiven Er- mitttung einer Zahl z angegeben wird, ftir die A (x) besteht; sonst hat man im ]~alle, dal] A (x) fiir kein ~ besteht, /~| (x)) = 0 zu setzen.) Die MSglichkeit dieser Darstellung yon ~ (~ . . . . , n~) beweise ich mit freundlicher Erlaubnis des Herrn J . v . Neumann dutch eine von ihm stammende ~IethodeS), die eleganter ist als meine urspriingliche (zwar unabh~ngig von Herrn v. Neumann, abet sparer entstandene) Beweis- anordnung.

6. Wird das Diagonalverfahren auf sgmtliehe mehrfach-rekursiven Funktionen angewandt, so entsteht die ,,Diagonalfunktion" dutch Ein- setzung aus einer solchen Funktion, bei der es vom ersten Argument abhiingt, wieviels~ellig die l~unktion ist. Das ergibt eine in~eressante

s) Ein Hinweis auf das Ergebnis yon Herrn v. Neumann, das auch yon Herrn G6del dutch eine ~hnliche Me,bode gefunden wurde, befindet sich im Buche: D. Hilbert und P. Bernays, Grundlagen der Mathematik I (1934), S. 421--422.

32*

496 R. P~ter.

Erweiterung des Rekursionsbegriffes, worunter auch die in ,,I" behandelte Wertverlaufsrekursion als Spezialfall f~illt. Es scheint lohnend, diese weiteren Rekursionsbegriffe n/~her zu untersuchen.

t terrn P. Bernays (Princeton) und L. Kalmhr (Szeged) spreehe ich fiir wertvolle Ratschli~ge und Vereinfaehungen meinen Dank aus.

w

Normierung der Anlangswerte.

7. Um die Fi~lle, wo eines der Argumente 0 ist, nicht unterscheiden zu miissen, fiihre ieh die Defini t ion

l q (n 1 + 1 . . . . , n ~+ 1, 0, n~+ ~ . . . . . n~, a) (b if) 7,1 . . zk (n , , - - . , hi, n t + , , . . . , nk, a, ~ (nl, x , , . . . , xa~),

D~ q (n, -4- 1, n~, x,, . . . , xk-1), . . . , ~ (n 1 ~--1, . . . , n l -1 + 1, nt, x l , . . . , x k - t + , ) ) ,

(l = o, 1, 2 . . . . , k)

auf eine solche Form zuriick, wobei der Wert der deiinierten Funktion 1 ist an allen Stellen, wo ein Argument 0 ist.

Zu diesem Zweck fiihre ich die folgende Funktionsfunktion ein:

~)Xl ' "~k ( ~bl' ' * "' nk , ~ ' gl (Xl:l"" *:l X.~.), g2 (~171, . . . , Z k _ _ I ) , . . . , gk (X,))

__ ,~ ( l ) ( n I 1 , n ~ - - l , n t + ~ , . , n ~ , a , g ~ ( x l , . , xk) ,

~ (x~ . . . . . x k - ~ ) , . . . , g~(x , , . . . , z ~ _ , + , )),

falls n~ ~= 0, n~ ~ 0, . . . , nz ~= 0, n~+~ =-- 0; (l = 0, 1, 2", . . . , k; fiir 1 = k ist n, ~= 0, n~ ~= 0 , . . . , n~ ~= 0 zu lesen).

Diese Funktionsfunktion en t s teh t aus den Funktionsfunktionen ~(0 ~I'" xk

und aus rekursiven Funktionen du tch Einsetzung. In der Tat ist

�9 ~ . . .~ (n , . . . , n~, a, g~ ( z , , . . . , x~) , g~ ( x , , . . . , x ~ _ l ) . . . . . g~ (x~))

= I ~ ( % ., n,~). r �9 " ~1.- . z~ (nl --" 1, . . . , n~ ~ " 1, nl + 2, �9 � 9 l ~ 0 n~, a, g~ (~,,.. . , z ~ ) , g~ (z~ . . . . , ~_~) , . . . , ~(x , , . . . , z ~ _ , + ~)),

wobei die Funktionen 0, falls n ~ . n ~ . . , nt ---- 0, oder n~+~ ~ 0,

~ ( n , . . . . . n ~ ) = 1, ,, n ~ # 0 , . . , n ~ 0 , n ~ + ~ = 0

rekursiv sin& Dann ist

(n~ . . . . , n~, a) = r ~ ( n , . . . , n~,, a, ~ (n~ "-- 1, z~ . . . . , x~),

~ ( n ~ , n~ --" 1, x , . . . , z ~ _ ~ ) , . . . , ~ (n~ , n~ . . . . . n~_~ , n~ --" 1, z~)),

also gilt ftir die Funktion, die fiir n ~ . n ~ . . . n~, :~ 0 dutch

~p(np . . . , n~, a) - ~ q~(n~ - - 1 . . . . . n~ - 1, a)


definiert wird,

~ ( ~ 1 + 1, . . . , n~ -~ 1, a) = Czl...~k (n, . . . . . nk, a, 0o(n, "-- 1, ~1 . . . . , x~),

(n 1, n~ ~" 1, Xl, . . . , x k - d , . . . , ~ (nl, . . . , nk-1, nk - - 1, xd) ---- q)~l . . .~ (nl, "" ", n~, a, vJ (n , xl .4- 1 . . . . . xk_ l -4-1, xk),

(hi .4- 1, n~, x~ .4- 1, . . . , x~_~ .4- 1, xk-1), . . . , ~p (n l -~ 1 . . . . . n k - l . § 1, nk, x,)).

Yiir n , . n2 . . �9 n~ = 0 kann ~ (n~ . . . . . n~, a) beliebig, z . B . als 1 definiert werden; wird also

= ~ . . . ~ k ( n , . . . , 2 . n , : , a, q~(x~ -4 1 . . . . , :~k--~ .4- 1, X~), . . . , g , , (~ ) )

gesetzt, so laute t die Definit ion yon ~(n~ . . . . , nk, a):

~0 (n,, . . . , nk, a) ~-- 1, falls n~. n 2 . . . n , = 0, ,p (n, + 1, . . . , n~ ~- 1, a) = T ~ I . . . ~ (nl . . . . , nk, a, ~0 (n 1, x, . . . . , x~),

(n, .4- 1, n~, xl, . . . , xk-1), . . . , y~ (n, .4- 1, . . . , n~_, .4- 1, n~, x~)),

and aus ~ (n,, . . . n~, a) gewinnt man ~ ( n , . . . , n~, a) durch eine Sub-

stitution wieder:

r (n, . . . . , n~, a) ~- ~0 (n, .4- 1 . . . . , n~ .4- 1, a).

Wird in .der Definit ion yon ~ (n , . . . . , n~, a) s tar t v2 wieder r and statt T wieder q~ geschrieben, so geht sie in die Definit ion D~ der Ein-

leitung Nr. 5 tiber.

w

Zur i iekf i ihrung ant die pr imi t ive F o r m .

8. Nun werde ich die Definit ion D~ auf die , ,primitive F o r m " D.. zuriickfiihren. Wie schon in der Einlei tung erw~hnt wurde, lasso ich, um bei den f ini ten Definit ionen zu bleiben, im Rekursionsschema D1 und D~ nu t solehe ]) 'unktionsfunkCionen r zu, die aus ihren Argumenten und gewissen schon eingefiihrten k-rekarsiven Funkt ionen -- die ieh die K o m - ponenten yon r n e n n e - du tch eine endliohe Ke t t e yon Subst i tu t ionen auigebau~ sind, wobei si~mtliehe Leerstellen du tch Einsetzungen , ,gebunden" werden sollen. I eh nenne eine Funkt ion , die aus 0 und n-4-1, ferner aus gewissen weiteren Funk t ionen dutch Einsetzungen und einfaehen Rekursionen ents teht , eine (in bezug auf iene weiteren Ausgangsfunktionen) ausgezeiohnete, und falls nu t pr imit ive Rekursionen ~) zugelassen werden, eine ausgezeiehnete pr imi t ive ~unkt ion . In diesem Paragraphen werden

9) Im Sinne yon ,,I", d. h. Rekursionen der Form r (0, a) ~- r162 (a), ~ ( n § l , a )~ - f l (n ,a , r Cn, a)).

498 R. P6ter.

als weitere Ausgangsfunktionen die Komponenten yon �9 betrachtet. Man kann voraussetzen, dal] die Anzahl der Argumente aller Komponenten gleich, und zwar grSl~er als k sei; die Komponenten miissen freilich nicht yon allen Argumenten tats~chlich abh~ngen. Aus demselben Grunde kSnnen wit annehmen, da$ auch n,, n~ . . . . , n, unter den Argumenten der Komponenten vorkommen, und damit ist erreicht, dail auch n,, n, . . . . . n, als Komponenten betrachtet werden kSnnen.

Seien also

~ , ( n , , . . ., n , , a , , . . . . , a t ) , f12 ( h i . . . . . nl,, a~, . . . . at) . . . . , fls (h i . . . . . nk, a l . . . . , at)

die Komponenten des in Definition D, auftretenden Terms

~x~ .. ~ ( n , , . . . , n~, a, g, (~, . . . . . ~ ) . . . . . ~ (z,));

dann kann dieser Term auch in der Form geschrieben werden:

r ~tlr (n,~, . . *, t(bk~, a , ~1 (X,, . . . . , Zk ) . . . . , ~Ir (XI))

= ~ . . . ~ . . . ~ , (a , f l~ (n~ , . . . , n , , y , . . . . . y~) . . . . ,

wobei die Funktionsfunktion

T,, . . .**v,. . .u, (a , /h (Y~ . . . . , Y~),.

nk, y~ . . . . . y,), g, (xL, . . . , xk), . . . , gk (x~)),

.., h, (y, . . . . , y~), 9, (:~, . . . . . z~), . . . , g~ (z,))

ohne" Komponenten, d .h . aus seinen Zahlen- und Funktionsargumenten dutch eine endliche Kette yon Substitutionen aufgebaut wird. Eine solche Funktionsfunktion werde ich Substitutionsterm nennen.

9. Um den Gedankengang klarer hervorzuheben, beschr~inke ich reich zun~chst auf den Spezialfall k = 1 yon D~:

/ (P(O,a) = 1, (~ + 1, a) = r ( , , a, ~ (n, x)).

In die~ Fall kann q~x in der Form:

~zu, . . .vr (a, fit (n, y, . . . . . y , ) , . . . , ft, (n, y, . . . , Yr), g (x))

ausgedrtiekt werden.

Die Werte yon ~ (n, a) lassen sich also aufbauen wie folgt:

~(o , a) = 1,

(1, a) ----- k ~ , ...v,(a, fl, (0, Yl, . . . , Y, ) , . . . , ft, (0, yt . . . . . Yr), ~0 (0, x))

= ~ l . . . ~ , ( a , ~ , ( o , y , , . . . , yr) . . . . . ~~ ~1 . . . . , y,), 1),

�9 ~ ( 2 , a) ---- ~ , , , . . . v ~ ( a , f l , (1 , y~ . . . . . y~) . . . . . f l~ y , . . . . , y , ) , ~ ( 1 , x))

= ~ , v , . . . ~ , ( a , fl, (1, y , _ . . , y~),..., fl~ (1, y, . . . . , y~),

~'~ ~, . . .~,(~, p, (o, ~, . . . . , u~) . . . . . ~ (o, ~ . . . . '~,), 1 ) ) ,

USW.


So liiilt sich ein jeder Wert ~ (n + 1, a) als ausgezeichnete (sogar primitive) Funktion aufbauen, also ohne den im Term r vorkommenden Aus- druck ~0 (n, x) (abgesehen yon ~ (0, x) ---- 1) verwenden zu miissen, es treten abet dafiir auch Ausdriicke tier Form fl~(m, Yl , . . . , Y~) (i : ], 2 . . . . . s) auf, w o m < n ist.

Definiere ich also eine Funktion y ( n , a ) derart, dal~ vp(0, a ) ----1, dall es ferner eln n gibt, Iiir welches ~ (n, a) -= a, endlich, dall ~ (n, a) als Funktion yon n (bei festem a) such die Werte fl~(m, yl . . . . . Yr) (i = 1, 2 . . . . , s) annimmt, ( w o m eine beliebige Zahl ist), falls sie schon die Werte Yl, Y2,-. . , Y, angenommen hat: so gibt es zu jedem n ein o~, fiir welches

~0 (co, a) = ~ (n, a).

Ich werde zeigen, dal~ sich, bci geeigneter Festlegung tier Funktion ~ (n,a), r als rekursive Funktion yon n definieren liiSt. Hierzu definiere ich zuni~chst v/(n, a) mit I-Iilfe der rekursiven Funktion ~ (a) wie folgt:

~p(0, a) ----- 1,

l a, falls n o(n-t- 1) = 0,

~p(n -4- 1, a) = / fl~~ (" + ~) (~' (n-t- 1), V (a~ (n+l)'fallsa) . . . . . 1 -~YJ (ze~ + , = 0 (n(n~- 1), a ) ) , + 1) < s,

( 1 sonst.

Man sieht leicht, dall die so definierte Funktion ~(n, a) die ge- wiinschten Eigenschaften besitzt: es gibt eine Stelle, wo sie den Wert a annimmt, z. B. (a) ~ (1, a) = a.

Nimmt sie ferner die Werte y~, y~ . . . . , y, an, ist z. B.

[ y~ = v2 (l~, a ) , y~ = ~ (l~, a ) , . . . , y~ = ~ (l~, a ) ,

(b) so ist flit i = 1, 2 . . . . . s

fl, (m, Yl . . . . , y , ) .= v 2 (2'. 3~.i__/~1 py+ ,, a).

Unter den Werten yon v 2 (n, a) kommen daher siimtliche Terme vor, die zum Aufbau yon ~ ( n A - 1 , a) notwendig sind; saint x nimmt sie daher auch den Wert ~ (n, x ) a n ; des genaueren ergibt sich dieses aus folgendem Hilfssatz:

H i l f s s a t z : Es 9ibt eine rekursivr _Yunktion v (u, v) so, da~

V' (u, V (", a)) = W (~' (~', v), a). Wird ni~mlich

~.(0, v) = o gesetzt, so ist zun/ichst

y~ (0, y) (v, a)) -~. 1 = yJ (v (0, v), a).

500 R. P~ter.

Sei ferner fiir i ___~ u die Funktion v so definiert, dal]

~fl (i, yJ (v, a)) = v 2 (v (i, v), a) so ist

"V' (v, a), falls :~o (u + 1) = 0,

(i = 0 . . . . , u ) ,

~,~o(u+ : ) ( ~ , ( u + 1), ~(gm(u-~- 1), v / ( v , a ) ) ,

. . . . w (=. + , (u + :), ~ (v, a)))

= fl=0(~+,) (~, (u ~- 1), ~ (v (~2 (u + 1 ) , v ) , a ) , (u~- 1, ~v (v, a)) ----

. . . , + o))

r + l *'(zj(U+l),V) a), ---- ~ ( 2~~ / / TJ

j = 2

falls 1 < go(u-b 1) <: s, 1 = v? (0, a) sonst,

und demnaeh wird die Gleichung

~ ( u + 1, ~(v,a)) = ~ ( v ( u + 1, v),a) erfiillt, wenn

iv, falls go (u + 1) = 0, I r + l

v ( u + 1,v) =- ~ 2no(u+l) 'an'(u+l) ' / ~ p~{~(u+l ) , v ) ,

/ falls 1 < ~o(U + 1) ~_~ s, tO sonst

definiert wird. Dies ergibt aber zusammen mit v (0, v) ---- 0 eine einfache Rekarsion (sogar ohne Einschachtelungen) f i i r r (u, v). Es ist zwar eine Wert- verlaufsrekursion, diese kann abet - wie scion erw~hnt wurde -- auf eine primitive Rekursion zuriickgefiihrt werden. Hiermit ist der Hilfs- satz bswiesen.

Mit Hilfe der Funktion v (u, v) gelangen wir nun zur Definition einer Funktion o~ (n), welche die Gleichung

@ (n), a) = ~ (n, ~) erfiillt, auf folgende Weise: setzen wit zunlichst

o) (o) = 0, so ist

~p (o) (0), a) ---- ~ (0, a)

= -1

---- ~ (0, a).

Nehmen wit nun an, dab die Funktion o~ sehon bis zu einer bestimmten Zahl n bin so definiert ist, da$ fiir i ___~ n

(~ (i), ~) = ~ (i, a),

Mehffache Rekursion. 501

dann gilt, falls fiir eine Zahl l

ist, ~ (/' a) = m

~- qJ(n,m).

Wenn also yJ (x, a) a]s Funktion des ersten Arguments den Wert m flit x =- 1 annimmt, so nimmt sie den Wert ~(n, m) fiir x----- v (co(n), l) an.

Aus dieser Tatsache, in Verbindung mit den Eigensehaften (a), (b) der Funktion y)(x, a) ergibt sich nun dutch vol]stiindige Induktion, da6 zu jedem Substitutionsterm g2, u~ . yr (a, h 1 (y~, ..., yr), ..., h, (y~, ..., y~), g (x)) es eine Stelle/~ gibt, so dab

~ ~. ~ ( a , 8 ~ (n , y , . . . . , y~) , �9 �9 8 , in , y ~ , . . . , y , ) , ~ (n , x ) ) = ~ ( ~ , a) ,

und dieses # entsteht aus ~2~ ul... y, (a, fll (n, y~ . . . . , Yr), �9 �9 8, (n, y~ . . . . . y,) (n, x)) derart, da6 darin a du~,ch 1, 8~ (n, y~ . . . . . y,) (i ---- 1, 2, . . . , s) dutch

2 ~. 3". h T.i+vJ ~ und ~ (n, x) dutch v (co (n), x) ersetzt wird. Speziell ist j ~ l

~%, . ,~ ( ~ , & ( % y , , . . . , y , ) , . . . , 8 , ( ~ , y , , . . . , y , ) , ~( . ,~) )

b h ~- -" , . . " "~ " " ~ + 1 ~ ~ �9 ~ u j + 1~ �9 . j = l J=l es ist also

~ ( n - ~ 1,a) ---- ~(r (n q- 1), a), wenn

co(n-k 1) ~ ,~ , ~,(1,2 l 3" ~ vj 2 z . 3 . . / - ~ v~ = . . . �9 . ~ j + ~ . . . . , p ~ , , , ( c o ( ~ ) , ~ ) ) j = l j~x

Dies bedeutet aber zusammen mit co (0) = 0 eine einfaehe (sogar primitive) Rekursion flit co (n), und fiir a ] l e n das Bestehen yon

(n, a) ---- ~fl (co (n), a).

Die Definition yon ~p(n,a) zeigt, da6 y~(n,a) eine ausgezeichnete (und sogar primitive) Ftmktion ist; nach dem Bewiesenen ist auch ~ (n, a) eine ausgezeiehnete Funktion.

q~(n,a) ergibt sieh auf diese Welse sogar als eine ausgezeichnete primitive Funktion. Damit haben wit zugleieh einen neuen, einfacheren Bewels des in , ,I" bewiesenen Satzes, dal~ sieh die eingeschaehtelte einfaehe Rekursion auf die primitive zurficldfihren l~l]t.

10, Die aUgemeine Definition D~ kann nach l~r. 8. mit Hil~e des Substitutionsterms in der Form:

[~ (n, . . . . . n~,a) ~- 1, falls n , . n ~ . . , n~---- 0, (n~ -4- 1, . . . , n, -4- 1, a) := Txx... ** ~ . . . v~ (a, 8~ (n,, . . . , n, , y~ . . . . , y,),

. . . . 8, (n~, . . . , n, , y~, . . . , YA, ~ (n~, x,, . . . , x~), cp(n~.-b 1, n~,x~ . . . . , x~_~) , . . . , cp(n~ -k 1, . . . , n~_~ + 1,n, , x~))

geschrieben werden.

~02 R. P6ter.

Die Wer te yon ~ mi t den ers ten k - 1 A r g u m e n t e n n~ + I . . . . . nk - ~ ~ 1 lassen s ich also aufbauen wie folgt:

~ ( n I + 1, . . . . nk -1 + 1 ,O ,a ) = 1,

( n l + l . . . . . ' * ~ - l + l , l , a ) = ~ , , . . , ~ , , , .~r(a,

fl~ ( n , , . . . , "nk - ~, O, Yl . . . . , y , ) , . . . , f l , (n 1 . . . . , n , _ , , O, Yl . . . . , Y , ) ,

q) ( n t , X I . . . . . Xk) , . . . , q) (n t -~- 1 . . . . , nk-- 2 "~- 1, n k - ~, x , , x~),

q~ (n I + 1 . . . . , n k - i -t- 1, O, x l ) )

= ~ , ' . . ~ k ~ , " . ~ , (a, f l t ( n , . . . . , n k 1 ,0 , Yl . . . . , Y , ' ) , . . . ,

p, (n, , . . . , m - ,, O, y, . . . . , y,), ~, (n, , x~ . . . . . z~), . . . ,

(hi -I- 1 . . . . , n k - , + 1, nk_ 1, z , , x~), 1),

UgW.

Man sieht, dal~ sich ein jeder W e f t r . . . , n ~ + 1,a) mi t Hilfe yon Subs t i tu t ionen so au ibauen lii~t, daft m a n dabei den in ~ , 1 . . . , ~ v i . . . ~ , v o r k o m m e n d e n Ausdruek q~(n! + 1 . . . . , n k - ~ + 1, n ~ , z ~ )

nieht zu ve rwenden braueht ; dafiir t re ten abe t auch Ausdriicke der Form

~ (n 1, . . . , n ~ - l , m , Yl . . . . . y , ) ( i -= 1, 2, . . . , s) auf, we m <__ n~.

Kons t ru ie re ieh also eine Funk t ion y (n~ . . . . . n~ ,a ) so, dab

y~(nl . . . . , n ~ , a ) = 1 fiir n l - n ~ . . . n k = O ,

dal3 sie ferner m i t yz . . . . ,~ y~ auch die Wer t e fl~ (n~ . . . . . nt.._ 1, -~, y~ . . . . , Y, (i ---- 1, 2, . . . , s) a n n i m m t ftir beliebigea m, daft sie endlich m i t x~ . . . . . xk auoh die Wer te ~ ( n , , x ~ . . . . . x~), . . . , ~(n~ + 1, . . . , nk -~ § 1 ,nr _~,z~,x~) a n v i m m t : so g ib t es ein to, fiir welches

~(n~ + 1 . . . . , n t _ ~ + 1, to, a) = q~(t h -4- 1, . . . , n , _ ~ + 1, n ~ , a ) .

Wegen der le tz ten F o ~ e r u n g , die im Spezialfall D~ nieht auf t r i t t , wird j e t s t die Defini t ion yon y kompl iz ier te r ausfallen: es kommen dar in aueh Einschachte lungen ve t , und to k o m m t auch in die Defini t ion hinein. Ioh werde abe t zeigen, dall sieh to auch in diesem Yalle als rekmrsive F u n k t i o n yon n~ definieren l~llt.

11. Sei

y (n~ , . . . , n t , a ) - - - - 1 , falls n z . n ~ . . , n~ = O, und t o ( O ) = O, so gil t fiir

~h.~tt . . . n~ -~ O:

(1) $' i n , , . . ., ~ t , a) = y (~t~, . . . , n ~ _ , , to (nr), a).


Fii~ �9 die Fortsetzung der Definition yon ~ und w mache icli zunichst den folgenden Ansatz:

~v(nl+ 1 , ..., n , + 1, a) ----

a, falls

/~,-v o (n k +

~p

~p (n,

V (hi -~ 1,

no (n~: § I ) = O,

1) (~,, . . . , n~_ l , m (n~ + 1),

(n~ + i , . . . , n ~ - , -+" I , ~r, (n~ + I), a) . . . . .

+ i . . . . . n~- i + 1, n ,+~(n~ + 1),a)),

falls 1 ~ z% (n~ -Jr- 1) ~ s,

�9 �9 % (nk § i) - ~-i + I, % <nk + i)-,,

+ I , . . . , nk_, + I , ar t (n~ -l- I), a), . . . , + 1, . . . , nk--~ -? 1,

g k - ( % ( . , + l ) - ~ ) - i (nk -~ 1), a) ,

(n, + 1, . . . , nk-1 + 1,

:~k-(~o (,~k+,)-~) (n~ + i), a) ) ,

+ 1, . . . , nk--1 -}- 1,

~-( '~o (~+')-')+ ~ ( ~ + i), ~)),

falls s ~- 1 < z% (n~ J_ 1) < s -~ l% 1 sons t .

Wkd in diesen Gleichungen flit eo eine relmrsive Funktion eines Arguments gesetzt, so ergeben sie eine k-fache Rekursion fib ~; die dutch diese definierte Funktion ~ ( ~ t , . . . , n k , a ) besitzt jedenfalts die ersten beiden der gewiinsehten Eigenschaften:

Erstens gibt es eine Stelle nk, wo ~ (n 1 + 1, . . . , nk-1 + 1, nk, a) den Wert a annimmt, es ist z. B.

(a) ~p (n 1 + 1 , . . . , nk-1 + 1, 1, a) = a.

Ist ferner

~(n~ -~- 1, . . . , ~k-~ + 1, [1, a) ---- Yl, ~(n l -k 1 , . . . , nk-1 + 1, 12, a) ----- y~,

. . . . ~(n 1 + 1 . . . . , n ~ - l + l r = y , ,

so ninunt ~ (n 1 -k 1, . . . , n ~ - i + 1, n~, a) aueh die Werte

~ ( % , . . . , n~_~, m, yl, . . . , y~) (i = 1, 2 . . . . . s)

bei beliebigem m an, denn es ist

(b) fl~ (n~, . . . , ~k-1, m, Yl, . . . , Y,)

(n~ + 1, . . , n~_ ~ + 1, 2~- 3~ / / ~J a). ----" �9 ' ~ j + l , j -~ - I

Ferner gilt (bei beliebiger Wahl der rekursiven Punkt ion co) der folgende I-Iilfssatz.

504 R. P6ter.

12. H i l f s s a t z : Es gibt eine rekursive Funktion v(u,v), so daft

(2) v ( n l + 1 . . . . n ~ _ l + l , u , v/ (n, + l, . . ., nk_l + l, v, a))

= ~ (n, + 1, . . . , n ~ _ l + 1, ~ (u, v), a).

Ftir u = 0 ist n/imlich die linke Seite = 1, also bes teht (2) fiir u = 0, fails

,,CO, v) = o

definiert wird. Sei v ffir kleinere erste Argumente als u + 1 schon so definiert , da$ (2) bestehe, so ist nach der Definit ion yon 9 :

~o(n l + l , . . . , n k _ , + l , u + l, ~p(n, + l . . . . . n k - l + l , v ,a ) )

v2 (n~ + 1, . . . , nk-~ -t- 1, V, a), falls ~o (u -4, 1) = 0,

+ 1) ( n l . . . . , ~bk-- 1, ;fl~l (U P~o,, + 1),

v ( n ~ + 1, . . . , hE--1 + 1, v ( ~ (U + 1),V), a) , " - ,

~(n~-4- 1, . . . , n k - x + l, v(~t ,+,(u + 1) ,v) ,a))

= ~ (n~ + 1, . . . . n~_~ + 1,

r + l v(ztJ (lt+l), v) 2~o (~ + ~). 3 ~ (~ + ~ ) . / / p ~ , a) ,

falls 1 ~___ ~ o ( u + l ) ~ s,

( n 1 + 1 , . . . , n,,o( u + 1 ) - , - - i + 1, n~ o (u + ~)-, ,

----- ~ ( n ~ + l . . . . , , k - 1 + 1, v ( z t l ( u q - 1 ) , v ) , a ) , . . . ,

+ + + , - , ) - (u+ v),

( v / ( n , + l . . . . , nk_~+l , v(~k-(~,o, ,~- l , - , ) (u+l) ,v) ,a))~

~ ( n ~ + 1, . . . , nk-~ + 1, v ( ~ - ( ~ o ( ~ + . , - , ) + ~

( u + l ) , v ) , a ) )

= ~p(n l + l , . . . , n k _ l + l ,

2"o (~ + I) k - (~o ( u ~ ) - s) + 1p~ " (~j (~ + 1), O, a),

falls s + l < ~ g o ( u 4 1 ) < s + k ,

1 ----- ~(n~2-, 1 . . . . , n ~ _ ~ + l , 0, a) sonst,

Cs ist also

(~1 + 1 . . . . . n~_~ + ~, u + 1, ~ (n~ + 1, . . . , n ~ - i + 1, v, a))

= w (n~ + 1 . . . . . n~_ l + 1, ~, (u + 1, v), a),:

Mehrf~che Rekursion.

und daher bes teh t (2) auch fiir u + 1, wenn

505

v, falls 7% ( u - 4 - 1 ) = 0,

r + 1 ~ 1), v) 2~o(~+1).3~1(u+ 1 ) . / / pj (~i(~+ , falls 1 ~_~ z% ( u + l ) _ < s,

�9 (u + 1, v) = k--(-~(,,+ 1)--s)+1 2~o (~ + 1>. H Pj ,

j ~ l

falls s + 1 ~ ~ o ( u A - 1 ) < s - t - k , 0 sons%

und dies bedeute t zusammen mit ~ (0, v) ~ 0 eine einfache Rekurs ion fiir (u, v). Damit ist der tIflfssatz bewiesen.

13. Es k o m m t nun darauf an, w als Funk t ion von n k so zu be- stimmen, dab die sich ergebende Funkt ion ~ die Beziehung (1)

q~ (n 1 . . . . , nk, a) ~-- ~ ( n l , . . . , n ~ - l , r (nk) , a)

allgemein erftillt. Um die Bedingung, welcher to hierftir zu geniigea hat, in rekuraiver

Form zu gewinnen, be t raehten wir ein best immtes Wer t sys tem hi-4- 1 . . . . , nk-1 ~- l , nk-b 1

und nehmen an, dab dutch eine Definition yon eo die Beziehung (1) fiir alle Wer tsys teme der ersten k Argumente yon % welehe VorgKnger jenes be t raehte ten Wer tsys tems sin& erftillt sei.

Dann ha t zun~cl~st y die folgende Eigenschaft : I s t fiix die be t rach te ten Zahlen n 1 ~- 1, . . . . nk-1 ~- 1 und gewisse Zahlen 11 . . . . . l~

~(n~ + 1 . . . . , nk-~ + 1, lj, a) = x~. ( j = 1, . . . , k),

so n immt ~ ( n ~ 1 . . . . , nk-~ ~ l , x, a) als Funk t ion yon x auch die

Werte (n I + 1, . . . , n ;_~ + 1, n~, x; . . . . , x~-~+l) (i ~- 1 . . . . , k - - 1)

an. Denn es ist ftir 1 <_~ i < k, auf Grund unserer Annahme:

~o(% + 1 . . . . . n i _ ~ + l , n ~ , x , , . . . , x ~ - ~ + l )

(c) = W(nl-4- 1 . . . . , n ~ _ ~ + l , n i , x ~ , . . . , x ~ _ ~ _ ~ , ~ o ( x ~ _ , : ) , x ~ _ t + ~ ) k - - i + l I.

---- ~p(n , - t -1 . . . . , n ~ _ , - ~ - l , 2 s+~ / / pja a). j = l

Is t ferner fiir eine gewisse Zahl

(n~ + 1 . . . . , n~_~ + 1, l, a) = x~,

so n immt ~(n~ + 1 . . . . . n~_~ + 1, x, a) fiir einen geeigneten W e r t yon x auch den W e f t ~(n~-4- 1 . . . . . n~_~ + 1, n~, xt) an. Denn es ist nach

unserer Annahme und nach dem Hilfssatz

~ (n~ + 1 . . . . . n~_ ~ + 1, n~, x~)

(d) ---- ~ (n~ + I , . . . , n,~_~ .4- 1, eo (n~), x, ) = + +

506 R. P6ter.

Aus (a), (b), (c) und (d) folgt nunmehr leicht durch vollsti4ndige In - dukt ion, dab es zu einem jeden Subs t i tu t ions term

9 , . . . . z ~ u l . . . V r (a, h z (y,, . . . , Yr) . . . . .

h~ (y~ . . . . , y~), 9 (Jq, . . . , x~) . . . . . 9k (x~))

eine Stelle # gibt , so daft

D n .. ~ ~ . . . . ~ (a, fl~ (n l . . . . . nk, y: . . . . . y~), . . . , fl~ ( ~ . . . . , nk, y: . . . . . y~),

~ ( n l , z , . . . . . z~) . . . . . q~(n~ § 1, . . . , n ~ _ l § 1, nk , x , ) )

=-= y ( n 1 § 1 . . . . . nk-1 -~- 1,/~, a),

und zwar geht dieses # aus ~2 n ..~,v~ ... :/~ derar t hervor, dab da r in a

durch 1, /9,-(n~ . . . . , nk, yp . y,) (i 1, 2, . . , s) du tch 2 ~- 3 ' ' k / I ~3" �9 ., ~ �9 P j + 1 , j = x

~ ( n l + l . . . . , n , _ l + : , hi , x : , . . . , x k _ ~ + , ) fiir i = 1, 2, . . . , k - - 1

dureh 2 *+' k--,+: ~. �9 / 7 pl ~, und ~ ( n I § 1, . . . , n~_ l -4- 1 , , ~ , x , ) d u t c h v @ ( n ~ ) , z l ) j = l

ersetz t wird. Speziell ist

T ~ l . . . ~k "~... ~, (a, fl~ ( n , . . . , nk, Yl, . . . , Y~) . . . . . fl, (n, . . . . . n~, y~ . . . . . Yr),

~ ( n l , X 1 . . . . . Xk) . . . . . ~ ( n I -~- l . . . . . nk- - 1 "~ 1, 7~,k, Xl) )

iv (n~ § 1 . . . . . n~_: + 1,

�9 ' .

, , . . . ( : , j = ~ j = :

2 ~ + : / ~ ; ; . . , 2 s+k-~ . I -~w~,~ ~. ( ~ �9 , j--~-I j = l

es ist also fiir das be t raeh te te Wer tsys tem n: + 1 , . . . , n~ + 1 :

~(n~ -{- 1 . . . . , n~ -4- 1, a) = iv(n~ -~- 1, . . . , n~ - i § 1, co(n~ + 1), a),

und daher gilt (1) auch fiir n: + 1, . . . , n~ § 1, wenn r

w ( n ~ , § = T n . . . z ~ . . . ~ r ( 1 , 2 ~.3 " 1 1 P ~ + , , . . . , s ,~ r v.

2 s + : k ~i s+k--: ~ zj / 7 p~ , . . . , ~ / / p ~ , �9 (~ (~), ~)).

/=I ~=1

Dies bedeu te t aber zusammen mi t ~o (0) = 0 eine einfache Rekurs ion fiir ~ (.n~) U n d zwar t r e ten darin die Wer te n t . . . . . n~_: nicht auf ; sie definier t a l so w als eindeutige rekursive Funk t ion yon n~. Fiir die so bes t ' r tnmte ~unk t ion o~ und die zugeh6rige Funk t ion ~v gilt also die Gleichung (1)' allgemein.

14. Es geniigt demnach, aul~er einfachen Rekurs ionen die in Nr. 1 ] angegebene Definit ion yon iv ( n , . . . , n~, a) zu behandeln.


Da in der Definit ion yon ~ ( n t -~-1 . . . . . nk + 1, a) auf tier reehten Seite auch Wer te ~v(n I ~- 1 . . . . . n k - i -~ 1, m, a) mi t m ~ nk auft re ten, kann diese als eine Wertver laufsrekurs ion nach n~ be t r ach t e t werden. Wird darauf das in , , I" behandel te Verfahren verwendet , dana wieder normiert (und die Fai lunterscheiduagen in der Defini t ion iihnlich wie in Nr. 7 zusammengefa•t) , so k o m m t man zu einer Defini t ion wie folgt:

r I . . . . . nk , a) : 1, falls n ~ . u s . . . n k - - 0 ,

(n 1 J.- 1, . . . , n~. -{- 1, a) --- o~ (n I . . . . . n~ ,a , ~1 (nl . . . . , n~, a) . . . . ,

$k--1 (n,, . . . , n~, a), ~ (n I -~- 1, . . . , n ~ - i -~- 1, n~, a)),

wo fiir i - ~ 1 , 2 , . . . , k - - I ,

~ ( n , , . . . , nk , a) .-~ ~ ( n I + 1, . . . , n ~ _ , ..~ 1, n , ,

7i') ( n , . . ., n~ , a , r (n~ + 1 . . . . . n ~ _ , + 1, n~, a)) , . . . ,

y i ' L , + , (n 1, . . . , n~, a, ~ ( n , - [ - 1 . . . . . nk_~ ~- 1, nk, a ) ) ) ,

wobei die Funk t ionen yJ i)9~) (i ---- 1, 2 , . . . , Ic - - 1; j ~- 1, 2, . . . . k - - i -{- 1) und a ausgezeichnete Funkt ionen sind, und W (n~, . . . , n~, a) ents toht dutch Einse tzung aus ~(n 1 . . . . . nk, a) und aus rekurs iven Funkt ionen .

Nun werde ieh den Pa rame te r a ganz aus der Defini t ion aussehal ten,

indem ich ihn mi t n~ zusammenziehe (iihnlich wie in Nr. 4 b o, b~, bs . . . . , b , zu einem P a r a m e t e r a zusammengezogen wurden). Sei

m = 2 n~ �9 3 a,

also (n, . . . . , n ~ _ , , n~ , a) - - X (n~ . . . . . n ~ _ 1, 2 ~k" 3~).

D a n a l~l~t sich die Funk t ion X(n~, . . . , nk-~, m) definieren wie folgt:

g(nL . . . . , nk-1 , m) ---- $(n , , . . . , % - 1 , ~0(m), ~ l (m) ) ---- 1, falls n 1 . . . nk-- ~ "~0 (m) = 0,

also jedenfalls auch dann, falls n ~ . . . n~_~ . m - ~ 0 ist. Und fiir

g 0 ( m + l ) ~= 0 ist

X(n~ + 1, . . . , n~_~ + 1, m + 1)

= $ (n 1 + I, . . . , n~_~ .4- 1, ~zo(m-{- 1 ) , = ~ ( m + 1))

= ~ ( n , . . . . . n ~ - l , ~ o ( m + 1) - 1, ~ ( m + 1), Z~ (n~ . . . . , n ~ _ ~ , m ) , . . . . g t - ~ (n~ . . . . , n ~ _ , , m ) ,

X (n, + 1 , . . , n~_ ~ + 1,. 2~o (~ § b - r . 3~ (~ + ~))),

~ ) Die Funktionen yJ0 ( ~ , : .., nk ' a, b) h&ngen eigentlich nur yon n~, a, b ab, kSnnten also in der Form y~o (n~, a, b) geschrieben werden. Dasselbe gilt fiir die

Fu~ktlonen. 2j(. 0 in der folgendon Definition yon V (n~ . . . . . n~_ ~, m).

508 R. P6ter.

wo fiir i = 1 , 2 . . . . , k - - 1,

Z, (n, . . . . n k - , , m) = Z (n~ + 1 , . . . , n, -1 ~ 1, n, , y~'~ (~,, . . . , ~ _ ~ ,

~o(m + 1) - - 1, ~1 (m -~ 1), Z (n, ~-1, . . . , n k - l + 1, 2 "~~ ~ I. 3"~ o~ ~ 1))) . . . . .

y(,~ 1 (n, . . . . . nk-1, go (m -[- 1) - - 1, a l ( m -~- 1),

x ( n l ~- 1 . . . . . n k - , + 1, 2"~0(~ + ~)-~. 3 ~ ( ~ + 1))),

~(t) I n �9 3 - k - i + 1 ~ J . . . . . . ~ k - 1 . ~ o ( m + l ) - l , ~ l ( m + a ) , Z ( n t + 1 . . . . . n k _ 1 + 1,~ n o ( m + 1 ) - l ' : ~ n x ( m + X ) ) ) ) .

Das ist w iede rum eine Wer tver lau is rekurs ion in m. Wird d a r a u f das sdbe Verfahren, wie vorh in flit ~ (n~, . . . , n~, a) angedeu te t wurde, v e r - wendet, so k o m m t m a n endlich zu folgender Defini t ion:

I ~/(nl, . . . , nk -1 , m) ~- 1, fails nl . . . nk_ l .m ---- O,

(n I + 1, . . . . n~_ 1 + 1, m + 1) = ~ (n, . . . . . n ~ - l , m, ,1, (n~ . . . . . n k - l, m) ,

. . . . ~k -1 (nl . . . . , ~ _ ~ , m), ~ (n~ + 1, . . . , n~ + 1, m)),

wo fiir i = 1 ,2 . . . . , k - - 1

I ~ (hi . . . . , n~_ ~, m) = ~ (n, + 1, . . . , m - ~ + 1, n~,

;ti ') . . . . . (n, + 1 , . . . , + . (~ )

�9 ~t~_, tn~, . . . , n t _ . , , m, V (n~ + 1 . . . . . n ~ _ , -t- 1, m ) ) ) ,

wobei die Funk t ionen ~.I i) (i = 1, 2, . . . . k - - 1; j ---- 1, 2 . . . . . k - - i) u n d u

ausgezeichnete Funk t ionen sind, a n d ~r . . . . . n~_~, m) en t s teh t d t t r ch Einse tzung aus ~ ] ( n l , . . . , ~'$k--l, ~'~) und rekurs iven Funkt ionen .

Wird hier s t a r t m wieder n~, s t a r t ~7 wieder ~, s t a r t ~ a u n d s t a r t

~o (i = I , 2, . . . , k - - 1 ; j ---- 1, 2, . . . , k - - i) ~n!~ gesetzt , so s t i m m t die ob ige

Def ini t ion mi t der Defini t ion D.~ der Einlei tung iiberein. Die allgemeine k-/ache Rekursion Idflt sivh also au[ die primitive Rekursion der Form D~ zuriick/iihren.

w

D i e k - t a e h e R e k u r s i o n o lme E insehaoh te lung .

15. Es e~hebt sich nun die ~rage , ob man die Def ini t ion D~ a td elne noch einfachere zuriickfiihren kann, insbesondere, ob m a n die E ~ - ' sehaehte lungen - - ebenso wie im Fal le der einfachen Rekurs ion --- vollst i indig ausschal ten kann. I ch werde zeigen, dal~ letzteres gewil~ n i ch t zutr i f f t , v ie |mehr gehSrt das Auf t re ten yon Einschaehte lungen z u m Weso~ der mehr fachen Rekursion~~ I n der Tat , ich zeige, da~ sieh jede m e h r -

10) Man bemerke, dab die Einschachtelung hier eine andere Rolle spie | t , ` a~, bei der einfachen Rekursion. Dort entsteht die Einschachtelung dadurch~ dab flit die Parameter Substitutionen effolgen, wobei auch die zu definierende Funktion


fache Rekursion ohne Einscl~achtelung auf einfache Rekursionen zuriickfiihren l~il~t. Durch diese. Tatsache wird die Bezeichnung ,,primitive k-fache Relcursion" fiir die Definition D~ motiviert.

Die k-fache Rekursion ohne Einschachtelung hat nach Normierung der Anfangswerte die Forint1):

(nl, . . . , n , , a) = 1, falls n ~ . % . . . n ~ = 0, 9 (nl + 1 . . . . , n~ + 1, a) = ~(nl, . . . , n~, a, 91 . . . . . ~ ) ,

D wo fiir i = 1 , 2 . . . . ,k ,

9, = 9(nl + 1, . . . , n~_~ + 1, n~, Pl (nl, . . . , n~, �9 .., ~ ' ~ , + , (~, . . . . , n~, ~)).

16-- Der Gedanke der Zuriickfiihrung yon D auf einiache Rekursionen wird am klarsten hervortreten, wenn ich sie zun~chst fiir einen Spezial- fall durchfiihre. Es laute die Definition

{ ~ ( o , n ) = ~ ( m + l , O ) = 1, ~ ( ~ + 1, ~ + ~ ) = ~ ( ~ , ,~, v (~ , ~(,~, ~)), ~ ( ~ + 1, ~)),

mad es ist zu zeigen, dal~ 9 (m, n) eine in bezug auf r162 und fl ausgezeichnete Funktion ist.

Falls n___~_ 1, so kann man q~(m4-1, n) aug der zweiten Gleichung ent- nehmen, indem n - 1 s ta t t n geschrieben wird; setzt man den so ge- wonnenen Ausdruck fiir ~ ( m + 1, n) ein, so wird

9 ( m + l , n + l) =

also wird ( p ( m + l , n + l ) dutch 9(m, f l(m,n)), q;(m, fl (m, n --1)), und ( m + l , n - - 1 ) ausgedriickt. Falls n ~ 2, so kann 9 ( m + l , n - - 1 )

wiederum aus der zweiten Definitjonsgleichung entuommen werden und so erh~lt man einen Ausdruck ffir 9 (m + 1, ~ + 1) mit Hilfe yon

~(m, fl (re, n)), 9(m, f l ( m , n - - 1)), 9 (m, f l (m,n -- 2)) und ~(m + 1, n -- 2). Dieses Veffahren sollte n-real iteriert und der zuletzt auftretende Weft 9 (m + 1, 0) aus der ersten Definitionsgleichung enbnommen werden. Dazu wiirde man aber eine Funktion benbtigen, die eine yon n abh~ingige Anzahl yon Argumenten besitzt. Um das zu vermeiden, ftihre ich dieses Verfahren an

v 2 (re, n) = I I ~ ( ' ~ ) , ~----o "~

substi~uiert werden kann (daher kommt in einer einfaehen Rekursion ohne Para. meter keine Einschaehtelung vor); die Definition D~ enth~t hingegea keine Parameter.

n) Der Parameter a kann bier mit der Methode des vorigen Paragraphen nioht ausgeschal~et werden, da diese Methode zu einer Rekursion mit zweifachen EinschachteIungen fiihrt. Das ist abet auoh nicht wichtlg: unser Verfahren fithrt auch ohnedem zu Rekursionen mi~ einem Parameter.

~lathemat4sche Annalen. 118. 33

510 R. P~ter.

der Wertverlaufsfunktion yon ~ (re, n) (in bezug auf das zweite Argument) dutch.

Zuni~ehst hat man die rekursive Definition yon ~0 (m, n) aufzuste|len.

~,(o,n) = / l p ~ - = ~,(n),

( m + l , 0 ) = p o = 2 ,

(man bemerke, dab sieh diese Oleiehung mit (1) wegen y ( O ) = 2

(m, n) = y (n), f a l l s m . n = 0

zusammenfassen l~Bt); ferner ist, wegen

(m, n) = =. (~v (m, u)) fur u ~ ~,

~o(m q- 1, n -~- 1) = v2(m + 1 ,n) . ~ ( ~ + 1 , ~ + i ) z-n+1

= ~ (m -~ 1. n) . ~o(~,n, ~(~.~(v,(~,~)), -~(~(~+ ,,,~,)) rn + 1

falls u >" fl (m, n), d .h . ~ (m, n) besi~zt eine rekumive Definition yon der Form

{ ~o(m,n) = y(n), falls m - n = 0, v2(m q- 1,n + 1) = (3(m,n,v 2 (m,u), v~(m q- 1, n)),

wobei -- und dies wird bei der Vermeidung yon Funktionen mit einer variablen Anzahl yon Argumenten yon lqutzen sein -- u beliebig, nut mit der einen unteren Einschrgnkung u ~__ fl (m, n) gewghlt werden kann, ferner y (n), ~ (m, n, w~, w~) in bezug auf die Ausgangsfunktionen r und ausgezeiehnete Funktionen sin&

Aus der zweiten Gleichung dieser Definition gewinnt man fur n :> 1

y ~ ( m + l , n ) = 8(re, n - - 1, w (m, u), Ip (m q- l, n -- 1)), falls u ~ fl (rn, n ~ 1),

also falls 12) u 2> fl (m, n) § fl (m, n -- 1),

v(,~ + ~, ~ + ~ ) = ~ (~, ,~, v (~, ~), ~ ( ~ , ~ - ~, ~ (m,~), v ( -~+ 1, ~ - ~))),

ein Ausdruck fiir ~o (m q- 1, n + 1) mit Hilfe yon v2(m,u ) und y~(m q- 1, n ~ l ) . Ieh zeige, dab es allgemeiner Iiir v ~ n eine Darstellung von

y)(m + l , n + 1) yon der Form

(2) ~ ( m @ l , n q - 1) = (~ , , (m ,n ,y (m,u ) ,~ (m+l ,n - -v ) ) ,

falls u ~__ Z fl (m, n - j) j = 0

ra) St~tt der Summe kSnnte ich bier und an mehreren Stellen weiter unfix das Maximum der entsprechenden Glieder gebrauchen; es is~ ja aueh, wie man leieht einsieht, max (a, b) eine 1.rekursive Funktion und max 8 (~, a . . . . . %) eine

c - -~ a - ~ d in bezug auf 8 ausgezeichnete ]?unktion.

Es ist

(1)

Mehrfache Rekursion. 51I

gibt, wobei 6~ (m, n, w,, w2) eine (in bezug auf ~, fl) ausgezeichnete Funktiou yon v, m, n, w~. w~ bedeutet.

Dies gilt fiir v = 0, falls O o (m, n, w 1 , w~) ~-- 6 (m, n, wl, w~) (und ftir

v -= 1, falls 6, (m, n, w I , w~) ~- 6 (m, n, w~, 5 (m, n -- 1, w,, w~.))) gesetzt

wird; nehmen wit an, 6o (m, n, wl, w~) sei fiir ein gewisses v < n bereits bekannt u n d e s gelte (2). Aus der zweiten Gleichung der Definition yon y~ (m, n) gewinnt man wegen n - v ~_~ 1

v/(m--~ 1, n - - v) = 6(re, n--(v--~ ]), yJ(m,u), ~(m--~- 1 ,n - - (v + 1))),

falls u ~ _ ~ f l ( m , n - v + 1)) also

~ ( m + 1, n + l )

= 6~(m,n,v/(m,u),6(m,n--(v--~- 1) ,p(m,u),v/(m-f- 1, n - ( v - F 1)))).

Wird also

gesetzt, so gilt (2) aueh ftir v + 1 start v. D.h. (2) gilt allgemein fiir v ___~ n, falls 6~(m, n,w~,w~) duroh die einfache Rekursion

I 6o (~, n, %, %) = 6 (m, n, %, w~), ] 6~+~(m,n, uk,w2)-= 6~(m,n,w~,6(m,n._(v+ 1),w~,w,))

definiert wird. Insbesondere gilt (2) ftir v----n; wegen ~(m-F. 1 , 0 ) = 7 ( 0 ) - - - - 2

gilt also speziell ftir u = 1 + ~ . f l ( m , n - - j ) = 1 + ~ f l ( m , j ) j----O j~--0

~ ( ~ + ~,~ + ~) = 6 . (~ ,~ ,~(~ , ~ + _r~(~,j)),2), j---o-

d.h. fiir die Funktion g (m, n) ---- ~ (m, n + 1) gilt die einiache Rekursion

z (o, n) = 7 (n + 1),

y, (m § 1, n) = 6,, (m, n, Z (m, ,~ fl (m,j)), 2), j ~ o

also ist ;~ (m, n), daher auch / 2, falls n = 0, (m, n) / Z (m, n --" 1) sonst

und (m, n) = ~. (~ (m, n))

eine ausgezeichaete Funktion. 17. Wird die obige Methode auf die Definition D angewandt, so

gelangt man zu einer (k -- 1)-fachen Rekursion ebenfalls ohne Einschachte- lung. Dieselbe weicht indessen yon D insofern ab, als sie nieht mehr

33 *

512 R. P6~r,

normiert ist. Deshalb betraehte ieh anstatt D eine etwas allgemeinere Defini t ion, n~mlich die folgende:

/ ~ ( n l , . . . , n k , a ) = y ( n , , . . . , n ~ , a ) , falls n 1 �9 n 2 . . . nk = 0, (p(n l~ - 1 , . . . , n k + 1, a) ---- or . . . , n ~ , a , T 1 , . . . , (P~),

D ' wo ffir i = 1 , 2 , . . . , k

I r = ~ (n, q- I, . . . , h i - 1 q- 1, n, , fl~) ( n l , . . . , n~, a) . . . . ,

Es ist n ich t komplizier ter , die obige Methode auf D ' als auf D anzuwenden; wird sie auf D ' angewendet , so en t s teh t unmi t t e lba r eine ( k - 1)-fache Rekur s ion wiede rum yon der l % r m D' .

Ich behaup te also, daft die durch D ' def inier te F u n k t i o n ~o (nl, . . . , n~, a)

in bezug auf ?, ~.,//J~) (i = 1, 2 . . . . . /c; j = 1, 2 , . . . , ]c - - i q- 1) ausgezeichnet ist, and setze voraus , dal~ diese B e h a u p t u n g (die fiir k ~ 1 offenbar gtiltig ist) flit k - 1 s t a ~ k bereits gilt. I ch bride die Wertver laufs- funkt ion yon cp (n 1 . . . . , n~ ,a ) der Reihe naeh in bezug auf die Argumente nj , . . . , n~, a, d . h . ich be t raeh te die Funk t ionen ~1 (n~ . . . . , n~, a), . . . , ~o~ (ha . . . . , n~, a), ~o (nl, . . . , n~, a), wobei

~ , (n~, . . . , n~ , a) = ~ (n~, . . . , nk, a), n t + 1

v2 t+l (n , , . . . . n ~ , a ) ~-~-o= p)v/' ' ' l . . . . . . t,J, nt+~ . . . . . %, a) ffir l = 1,2 . . . . , k - - l ,

a

~o (n~, . . . , n~, a) ~- H p~k <',~ . . . . . . ,~, J). j = o 2

N u n werde ich die rekurs iven Defini t ionen yon ~oa, . . . , ~%, y auf- stellen. .Die Defini t ion yon ~ wird yon einer e twas komplizierteren F o r m sein als die von ~0; es gilt n~mlieh flit l = 1, 2 , . . . , 1~

v2~(nl , . . . , n~, a) ~- ?~(nl, . . . , n~, a), f a l s n , . n ~ . . . n~ = 0, yh(n~ + 1, . . . , n ~ + 1,a) = ~ (na . . . . . n~, a, ~p~ . . . . , ~0~, y ~ . . . . , v;i~) ,

wo fur i = 1,2 . . . . , k l "--:-- i

( a } = + . . . . . + . . . . .

+ , . . . ,

u n d ffir i ---- 2 ,3 . . . . ,1

v?~ = y~(n~ q- 1, . . . , n ~ _ a ff- 1, n ~ , u . . . . . u, n t + a + 1 . . . . ,n~ q- 1,a);

bier kann u >" u~(n~ . . . . . n~,,a) beliebig gewghlt werden; dabei sind ?~, a~, ~ gewisse ausgezeiehnete F u n k t i o n e n (d. h. bis zum Ende dieses Pa rag r~phen s te t s : ausgezeichnete F u n k t i o n e n in bezug auf die Funk- t i o i e n ?, 0r und ~=) fl~, ). - - Bei der Funk t i on ~ wird d a n a diese Abweichung yon D ' wieder verschwinden.

Mehrfaehe Rekursiom 513

Die Gteiohungen ($) gelt~n fiir l---- I mit yt : y, % - - - - ~ und

etwa x~ ~ 0 (da ffir I ~ 1 kein u auftri t t) . Nehmen wit an, fie gel~en fiir ein gewisses l < k, D a n n ist znn~chst ~) ~iir % . n ~ . . . ~ ~ - 0

~'~/. + 1

~ot +t (hi, "" ", n~, a) = H P]~ (nt . . . . nz.j, ,r ~ . . . . . ,,~., a) ~_ r~ +1 (nl . . . . . nk, a). j~-o

Ferner ist, fails u 2> x~ ( % , . . . , n , , a),

(4) ~ +, (n~ + 1, . . . , nk + I , a)

= 7~+~(n~ q- 1 , . . . , n z + 1 , n z + l , n l + ~ + 1 , . . . , n~-+- 1, a)

�9 ,n"t (n t , ..., nt, a, r . . . . . , ,oft , , , o~ . . . . . ' / t l ) r n ~ + I + I

p , . ,./)a~- (n I . . . . , ak~ a , I p l t . . . . , tPl k , tPl 2 . . . . . g ' l ~) �9

bier ist, da

v2t (n, . . . . , n.~, a) = ~"l + 1 (lot +, (n l , . . . , nz , u, nt + 2 , . . . , nk , a)), falls u ~ nz + i :

~'~, = % 1 , ) . , + , ( . ~ . . . . , , ~ , o ) ( v , + , ( - , + 1, . . . , , , , ._, + 1, . , , l - - z + 1

(i) . . . . . . . . . . , , o ) ) )

= rr#~) (., . . , . ~ , ~ ( ~ + l , d , M l s i = 1,2 . . . . . l, l ~ t + l

u > ~?_ ~+, (n, . . . . , n~, ~);

W. a+: = an,+, (~ ' ,+ , (nt H- 1 , . . . , n,-I-" 1, n ,+ , , f l { ' + * ' ( n , , ...,n~,a), �9 - . , w - ~ v'o, . . . . , n~, a ) ) ) = n .~+~ ( ~ + ~ , ~+~);

y~t = =.~+t+ , (~o~+~ (n~ + 1, . . . , n ~ + l , n z + t + l , n ~ + = + 1 . . . . ,

n i - t H- 1, n, , #(o (n,, .., n~ a), e(') n~, a))) �9 ~ �9 ' "~ [ - ' k__ ~ + 1 (~v$1 ~ , , , ~

~,~+~+~(y~+~,~.), falls i = l + 2 , l + 3 . . . . , k ;

t - - f + l

. . . . ~ + 1, a))

z.~+a+t(~o~+~,~), fails i - - - - -2 ,3 . . . . . l, u > n ~ + t + l ,

wobei v A + ~, ~, . . . , to~ + ~, ~, ~e} + ~, ~ . . . . , ~ + t, ~ + t natiirlieh d u m h (3) definiert

wexden.

Sei u ~_ ~t~ + ~ (n 1 . . . . . n~, a), wo l (~

~ t + ~ ( n l , . . . , n~,, a) = • + .~13 t -~+ z (n t . . . . , n~ , a )+n~+~ + I ,

is) M~n be~mhte, dM~ flit nl+'x ----- 0 d~s Produkt in der folgenden Formel &us einem einzigen, zu ~ ~- 0 geh~rigen, Fsktor besteht.

514 R. P6ter.

so e rg ib t s ich aus (4) d u r c h E inse t zung tier ge fundenen Ausdriicke fiir ~z~, W},

~z + ~ (n1-4- 1, . . , nk § 1, a)

= ~ l+~(n , . . . . . nk, a, ~ t + ~ , l , . . . , ~ l+~,k , ~i+~,2 . . . . . Wi+~,l+~) m i t

or 1 (7~1, . . . , n~t , a , w l , . . . , Wk , W k + l , . . . , W k + Z)

gn l + l ( w / + 1),~n 14_1 + l (wl + 2), . . . . ~7~ t + ] + l (IVl 4- k - - l) )

D a m i t ist (3) m i t e n t s p r e c h e n d e n ausgeze ichne ten F u n k t i o n e n 71 + 1, ~ + 1,

zz + 1 auch fiir l -~-1 bewiesen,

Insbesondere erhiilt m a n aus (3) ftir l = k

~Pk (nl . . . . . q'k, a) - - Yk ( n l , . . - , n~, a), falls n 1 �9 n~ . . . n~ = 0,

yJ~ (n~ -~ l . . . . . n~ -}- 1, a) ----- ock (n 1 . . . . . n~, a, Y~l . . . . , YJk~, Y~'2 . . . . . Y~ik),

wo v2~, ---- w ( n l + - 1 . . . . . ~ , _ , + 1, n , , ~ t ~ ( k ~ . _ ~ + l ( n , . . . . ,nk, a))

fiir i = 1 ,2 . . . . ,k, k - - i

y ~ = ~p~ (n, + 1 . . . . , n, - 1 -4- 1, hi , u, .~. ., u, a) fiir i = 2, 3 . . . . ,/~

falls u ~ u~(n~ . . . . . n~, a).

18. B e i m 0 b e r g a n g y o n ~% zu v/ ist eine gewisse Vors ich t notwendig. Zuni ichs t ist

(nl , . . . , n~, a) = H p ~ ( ' q ' " "~'r = ~/(nl, . . . , n~, a), falls n~. n , . . . n~ = 0, j = 0

fe rner ist a

(5) y~(n~ + l, . . . , n ~ - ~ l , a ) = I I p ~ t , q + ~ , . . . , , ~ + ~ , ~ j = 0 " 3

a t = I I ?]k % .... , ,~,,~, v'~ ..... v'~, w~, .., v'~),

j=O

ialls u > ~ u ~ ( n ~ , . . . , n ~ , j ) flit j = 1 , 2 . . . . , k ; hier s t eh t j s t a t t a in ~ , . . . . , ~ , ~ , ~ . . . . . ~ .

D u t c h A n w e n d u n g y o n

y~ (n, , . . . , n~, a ) . = ~a (Y)(n~ . . . . , n~, u)) fflr u ~ a,

gewinn t m a n k - - i + 1

W~ = ~r~i,)_, + ~(,q . . . . ,v,,r ( V ( n l + 1 . . . . , n , _ ~ -~ 1, n , , u . . . . . u, u))

ffir i = 1 ,2 . . . . , k ; u ~ f l ( ~ ~

k - - i + 1

Y~ii = ~ (V (n, -~ 1 . . . . , n , _ , -}- 1, n i , u . . . . , u, u))

fiir i = 2 , 3 . . . . , k ; u>~>j,

Mehriache Rekursion, 515

Fi i r i < k b e h a l t e i ch d iese G l e i c h u n g e n u n v e r ~ n d e r t , f i i r i = k s e t ze

ich a b e r I i i r u den ( e r l aub ten ) W e r t

T ( n l , . . . , nk , a) = ~ (/~?) (n , , . . . , n k , j ) § ein: j = 0

v,k~ = ~?,(,~,, ,,lk,~)(~ (,1 + 1 . . . . . , ~ _ ~ + 1, ~ , ~ (n,, . . . , , ~ , a))) ,

v2'~k = =~ (~p (n l + 1 . . . . , n k _ l -~ 1, nk , z (n , . . . . , nk , a ) ) ) .

Mit de r B e z e i c h n u n g k- -~+ l

W(~) -= y~ (n 1 + 1 . . . . . n, _ ~ A- 1, n,., u, . . . , u) (i = 1, 2, . . . , k - - 1),

W(k) = ~ (n , + 1, . . . , n k - , + 1, ~ , ~ (n~ . . . . , n~, a ) )

e rhgl t m a n a l so

V'k~ = ~#~,) +~ (,,~ . . . . . ,~,~)('V '(~)) f i ir i ---- 1 , 2 . . . . , k - - 1,

v2~ ~ = rtj(~p(i)) f i i r i = 2, 3 , . . . , k - - I ,

W~rden d iese A u s d r t i c k e in (5) e ingese tz t , so wi rd

~v (n 1 ~ 1 . . . . , nk -~ 1 , a ) ---- (3 (n, . . . . , n~, a, ~(1) . . . . , v2(k) ) m i t

(~ ( n , , . . . , n k , a , w l , . . . , w,)

= / ~ / p ~ k ( * ~ . . . . . "*'J ' ~(~')(~1 . . . . . ",.~) % ) . . . . . "~*> % . . . . . .,,~) (~*)' "~ (w~) . . . . . .~ (~,)),

j = o i

fails u a l l e e r f o r d e r t e n B e d i n g u n g e n erf t i l l t , a l so gewiB, fal ls

k--~ (0 u > a (n~, . . . , n , , a) = ~ (z , (n~ . . . . . n~ , j ) + j + ~ f l , _ ; +~ (n , , . . . , n , , j ) ) .

j = 0 t--~-I

19, h u f d ie so e r h a l t e n e r e k u r s i v e D e f i n i t i o n y o n W:

(n~, . . . , n~, a) = V (n~, . . . , n~, a), fa l ls n~ .n~ . . . n~ = 0,

V (n, + 1 . . . . . n~ + 1, a) = ~ (n x , . . . , n~, a, y,") . . . . . y,(~)), k- -~ :~

wo y~(') = v / (n l + 1, . . . , h i - ~ + 1, n~, u, . . . , u ) f l i t i = 1, 2 . . . . . k - - 1,

W (~) ---- W (n~ -t- 1, . . . , n~_ ~ -4- 1, n~:, "~ (n~, . . . , n~, a)) ,

fa l l s u ~ a (n~ . . . . , n~, a)

kann m a n n u n m e h r d a s Y e f f a h r e n de r , , M i n d e r u n g y o n n~" (s iehe lqr. 16.)

anwenden . I c h bewe i se f i ir v ~ n~, u ~ a~ (n~ . . . . . n~, a ) :

(6) y~ (n~ -4- 1 , . . . , n~ d- 1, a)

-=- ~,, (n~ . . . . . n~:, a, ~(1), . . . , y~(~- ~), y (n~ + 1 . . . . . n~_ 1 ~ 1, n~ - - v,

�9 o (-~ . . . . . ~ , ~ ) ) ) ,

516 R. P6ter.

wobei ~ , a , , T~ ausgezeichnete Funkt ionen ihrer Argumente (darunter aueh v) s in& Dies gilt bereits fiir v = 0, falls ~o ---- 6, ao = a, ~o ~- T. Netmaen wit an, es seien fiir ein gewisses v < n k die F u n k t i o n e n ~ , a~, ~ (als Funk t ionen ihrer iibrigen Argumente) bekann t , so da~ (6) gilt. Aus der zweiten Definit ionsgleicbung yon ~ folgt wegen n~ - - v > 0

(n 1 -~- 1, . . - , nk--1 + 1, nk - - v, T, (n I . . . . , n~, a))

= ~ (n 1 . . . . . nk--1, n k - - ( v ~ - 1 ) , ~ , ( n 1 . . . . , n1 , ,a ) , V (1) . . . . , V (k -1 ) ,

v/ (n , -5 1 . . . . . n k - 1 + 1, n~ - - (v -6 1),

�9 ( . , , . . . , - + . . . , a ) ) ) ) ,

falls u ___~ a ( n 1 . . . . , n k - x , nk - - ( v + 1), T , ( n , . . . . , nk, a));

wird dies in (6) eingesetzt ,

V ( n , , . . . , n k - , , nk - - (v-~- 1), T,~(n, , . . . , nk , a)) = r v + x ( n 1 . . . . . n ~ , a )

u n d

O ~ ( n , , . . . , n ~ , a , w l . . . . , w k - 1 , (~(n, , . . . , n k - l , n ~ - - ( v -4- 1),

�9 : , ( , , . . . . , n~, a), w , , . . . , ~,~_~, w~)) = ~ + , (n~ , . . . , n~, ~, ~ , . . . , ~ )

gese~zt, so ergibt sich /fir

u >~_ a,~ ( n , , . . . , nk , a) .-f- a ( n , , . . . , n k - , , nl, - - (v ~ . 1), sv (n, . . . . , n~, a))

av+ i (mr . . . . , n~, a)

(n 1 q- 1 . . . . , n~ -4- 1, a)

= ~ + ~ ( ~ , . . . , n~, a, ~(~) . . . . , ~ r ~ (n~ -4- 1 . . . . . n~_ ~ + 1, n~ - ( v + 1),

d . h . (6) mi t v - b 1 s t a r t v. Wird also ~o du tch die e infache Rekursion

T o (n,, . . . , n~, a) = ~ (n, . . . . , n~, a),

Tv+l (nl, . . . , n~, ,a) = ~ (hi, . . . , n k - i , n ~ (v --1- 1), vo (n i . . . . . n ~ , a ) )

und dann (~ a n d a~ du tch die einfachen Rekurs ionen

/ ~o ( % , - . . , n~, a, w~ . . . . , w~) = ~ (n~, . . . , n~, a, w~, . . . , w~),

8 ~ + , ( n ~ , . . . , n ~ , a , w ~ . . . . , w~,) "----- 8, , (n~ . . . . , n ~ , a , w ~ , . . . , w~,_~,

~ ( ~ ; . . . . , ~_~ , ~ .-2 (~, + ~), ~, ( ~ , . . . . n~, ~), ~ . . . . , ~ _ , , ~ ) ) ,

{ ~ o ' ( , , , . . . , , , , a) = (, ( , , , . . . , n~, a),

a~ +~ (n, , . . . , n~, a) = a~ (n~ . . . . , n~,, a)

-F a ( n ~ , . . . , n ~ - x , n~, .--- (v -~- 1), v~ (n~, . . . , ha, a))

definier~,~ s o sin4 ~ , a~, ~ ausgezeichuete F u n k t i o n e n und (6) gilt fiir v ~ ~n~, u: ~ ~ (n~ . . . . , n~ , a).


20. Insbesondere ergibt sich aus (6) flit v = n , , u ---- a~ k (n 1 . . . . , nk, a) die /olgende ( k - 1)-fache Rekurs ion:

p (n 1 . . . . . nk, a) = W (n x . . . . . nk, a), fails n L �9 ns . . . n~ = 0,

~ ( n l § 1 . . . . , nk § 1 ,a ) = ~ k ( n l . . . . . n k , a , ~p<l), . . - , V ~ - , ) ,

~ ) ( n l § 1, ~176 *, nk - -1 § 1, O , ' ~ n k ( n l , * � 9 nk,a))), wo fiir i = 1,2 . . . . , k - - 1

k - - z + 1

~p(') = ~p (n t § 1 . . . . , n , _ l -t- 1, n,, ank (nl, . . . , nk, a ) , . . . , a~, (n, . . . . . n , , a)).

Hie r ha t nk ebenfalls die Ro]le eines Paramete rs . Man kann abe t n~ m i t a na~h der in Nr. 4. erw~iJanten und aueb in Nr. 14. angewandten

Methode in einen P a r a m e t e r b -~ 2 nk. 3 a zummmenfassen , m i t Hilfe der Funk t ion

( n , , . . . , n , _ ~ , b) = ~ ( ~ . . . . , n k _ ~ , ,~o (b), =~ Ib)), so dab

~ o ( n l , . . . , n k - - l , n ~ , a ) ---- ~(n , , . . . , h a - l , 2 % . 3 a ) .

Diese F u n k t i o n li~i~t sich definieren wie folgt:

(nl . . . . , n , - x , b ) = r * ( n l , . . . , n k - l , b ) , fails n 1 . . . n k_l - - O,

~(n I -~ 1, . . . , nk-~ ~- 1, b ) = r162162 . . . , nk_~,b,$~, . . . , ~k--1),

We fiir i = 1 , 2 . . . . . k - - 1

. ~ R (0. t - ~t ~ (n~ + 1, . . , m - ~ + 1, , , , , ~ l ~o~ . . . . , n~_ 1, b), . . . ,

fl~')*_, (n, . . . . , n , _ , , b)),

w o b e i ~ * , ~ * und f l F ( i = 1,2 . . . . , k - - l ; j---- 1 , 2 , . . . , k - - i ) ausgezeichnete Funk t ionen sind.

wird also durch eine ( k - 1)-faehe Rekurs ion yon der Form D' definiert ; nach der Indukt ionsvorausse tzung ist daher 8 eine ausgezeichnete

F tmk t ion in bezug auf die FunkCionen ~ , ~ , ~,1 , and so auch in bezug n (-~ also grit dasselbe flit die F u n k t i o n au~ ~, ~ , r~ ,

~o(n, . . . . . n , , a ) - ~ ~ , , ( g , , ( . . . ( ~ r ( - , ( , . (n, . . . . , n , _ , , 2 "~ �9 3a>) ) . . . ) ) ) ,

wie b e h a u p t e t wurde.

Sind demnach insbesondexe die Funk t ionen y, a, fljo in D ' 1 - rek~s iv , so is t es auch ~0. W e a n m a ~ demnach yon den Funkt ionen 0 and n-~-1 ausgeht und durch Subs t i tu t ionen und mehrfaohe Rekurs ionen ohne Ein- schachtelung neue Funkt ionen bildet, so ents tehen lauter 1-rekursive Funkt ionen:

Die nicht-eingesohachtelte mehr/avhe Rekursion ]iihrt aus der Klasse der 1-rekursiven Funktionen nicht hinaus.

518 R. P~ter.

Daraus folgt nattirlich auch, dal~ im allgemeinen aus der Definition D s

die Einsehachtelungen nicht ausgeschaltet werden kSnnen, da Acker- mann 3) ein Beispiel fiir eine 2-rekursive Funktion gegeben hat, die nicht 1-rekursiv ist. Demnaeh ist D~ im wesentlichen die einfachste Form, auf welche die k-faehe Rekursion gebracht werden kann.

w

Das Diagonalverfahren. 21. Die Zuriickftihrung auf die Definition Ds ermSglicht eine sehr

einfache Anordnung ailer k-stelligen k-rekursiven Funktioneff in eine ab- gezi~hlte Reibe:

(F ) ~o(n~ . . . . . n~), ~ (n~, . . . , ~ ) , . . . , ~ ( h i . . . . , nk), . . .

(wobei eine Funktion auch 5leers vorkommen ]:ann). Betrachtet man die m-re Funktion r . . . . , n ~ ) = ~(m, n l , . . . , n~) als eine Funktion der k ~- 1 Argumente m, n~ . . . . , nk, so gewinnt man eine Funktion, die nieht k-rekursiv sein kann. Sonst wi~e n~m]ich aueh ~ (n 1 . . . . . nk), also auch ~ (nl, . . . , n~) -~ 1 eine rekursive Funktion, es g~be demnach eine feste Zahl m so, daI3 %~ ( n l , . . . , n~)~-1 mit ~ ( n l , . . . , nk) iden- tisch ist. ])as ist aber unmSglich, da die beiden F~m~tionen ffir n~ --~ m verschiedene Werte besitzen.

Nun werde ich diese Anordnung wirklich angeben: es wird sich her- ausstellen, dal~ die Funktion rp(m,n I . . . . . n~) darch eine (k q-1)-fache Rekursion definiert werden kann. Also fiihrt die (k-1- 1)-faehe Rekursion fiber die Klasse der k-rekursiven Funktionen hinaus.

22. In w 2 hat es sich herausgestellt, dal~ man von den 1-rekursiven Funktionen ausgehend, dutch eine endliche Kette yon Substitutionen und Rekursionen der Form D3. shmtliche k-rekursive Funktionen definieren kann.

In ,,II" (w 1, S. 45--49) wurde bewiesen, dal3 sieh jede I-rekursive Funktion dutch eine endliche Kette yon Rekursionen der Form

{~ (0) = 1 (R) ~o (n A- 1) -- ~ (n, ~v (n)),

Substitutionen und Umbenennungen der Argumente gewinnen l~tl~t, wenn man start 0 und n ~ 1 yon den Funktionen

ausgeht. Die Umbenennung der Argumente l~llt sich natfirlich als Spe- zial~all der Substitution auffassen, falls man alle nStigen Argumente zu den Ausgangsfunktionen hinzunimmt.

betrachte , Form D.~. tionen.

Mehrf~che Rekursion. 519

Die durch (R) definierte Funkt ion ~(n~) en ts teh t durch die Ein- setzung:

(n~) = V' (n~, n~, . . . , n~)

aus der Funk t ion ~ (n~, n~ . . . . . n~), die du tch folgenden Spezialfall von D~ definiert wird:

/~ (n~ , . . . , n~) --~ 1, falls n~.n~ . . . n~ ---- 0,

I ~ ( ~ + ~ , . , . , n~ + ~) = ~ ( ~ , w (n~, n~ . . . . , ~,)).

Ferner , wenn m a n sich auf hSchstens k-stellige Funk t ionen beschr~nlr~, so genfigt es, auch Subs t i tu t ionen nur zur Bildung yon hSchstens m a x (2, ]r stelligen Funkt ionen zu verwenden. Ich nehme an, dab k ~ 2 ist; fiir ]r = I wurde die Behaup tung schon in , , I I " (w 2, S. 4 9 - - 5 3 ) bewiesen.

I c h gehe also yon den Funk t ionen

(A) ~,, n~, . . . , ,~, p~l, n~ , ~,,~ (n~)

aus, die ich sgmtl ich als k-stellige Funkt ionen der Argumente n 1 . . . . , n~ und verwende Subs t i tu t ionen uud k-fache Relrursionen der 8o erhal te ich sukzessiv alle k-stelligen k-rekurs iven Funk-

'23. Ich setze also

% ( n l , �9 � 9 n k ) = n , . . . . , ~ - 1 (n~ . . . . , n k ) = ~ ,

~ (~j, . . . . . ., ~ k ) = p , l , , ~ k ~ 1 ( n l , , n~) = n ~ ,

~k + ~ ( n , , . . . , n~) = ~,~1 (~) .

Fiir m ~ k Jr 2 definiere ich durch Rekurs ion in bezug auf m, welche Funk t i on als ~ (n I . . . . . n~) gel~en soll. Es sei also ~ , (n l . . . . . n~) fiir

s ~ m bereits bekaunt , dann ents tehe r 1 . . . . . nk) fiir z o ( m ) = 0 dutch Subst i tut ion, und zwar so, dal~ in die LeersteUen yon ~ 1 (m) (n~, . . . , n~) die Funk t ionen ~,~ (~) (nl, . . . , nk), �9 �9 ~ k + 1 (~) (nl . . . . , n~)

eingesetzt werden. Fiir ~0 (m) ~ 0 ents tehe ~ (n I . . . . . n~) durch eine Reku~sion der F o r m D 8 und zwar so, daI~ darin fiir g (nl, . . . , nk, a~, . . . , a~)

die F unk t i on ~ o (m) (nl . . . . , n~_ l , To ~. p~ . . . p~k)l fiir i = 1, 2 . . . . , k - - 1 ;

j = 1, 2, . . . , k - - i an Stelle yon ~0 (nl, . . . , nk, a) die F u n k t i o n

~) (n~, . . . , ~ - 1 , p ~ " p~) ~ n (i - - 1) (~ k - - t) +j

gesetzt wird. (~SJ ~ ist das ( i - 1).2(2 ]~-- i ) -~- j - te Olied in der Reihenfolge

520 R. P6ter.

In der so definierten Folge (F) kommt eine jede k-stellige /~-rekursive Funktion mindestens einmal vor, und zwar mit einem Index ~ k + 2. (Dies sagt nur fiir die Ausgangsfunktionen (A) mehr aus als die ur- sprtingliche Behauptung.) In der Tat gilt das fiir die Ausgangsfunk-

k . 1

tionen (A), da ftir m = 0, 1 . . . . . k-~ 2 m' ---- 3 ~. /-] p~+ ~ gewil~ grSl~er i ~ O

als ]r 2 ist, also r (n~ . . . . . n~) aus r (nt, . . . , n~) dutch die ,,identische Substitution" entsteht (n~mlicb dutch Einsetzung yon n~ fiir n~ . . . . , n~ f t i rn , ) , und so mit diesem identis~h ist. Entbiilt femer die Folge (F) die Funktionen a (n~, . . . , n~), fl~ (np . . . , nk), . . . , ~, (n~ . . . . , n~) mit einem Index ~ ]~ + 2, ist also ftir gewisse i, j~ . . . . . j~ ~ / r ~- 2

(n, . . . . . n~) = ~ , (hi , . . . , n~) , /~ , (~,~ . . . . . n~) = ~ , (,~, . . . . . n~) . . . . .

/ ~ (n, . . . . . n~) = ~oj~ ( . , . . . . . ~ ) .

so gilt

(# , (~, . . . . . ~ , ) , . . . , / ~ k (n , . . . . . n~)) : ~ (n, . . . . , ~ ) , k

WO ~' : a i . H P I t �9 - I l = l

also ist aueh die aus ~t, fl~ . . . . . /~ dutch Substitution en~st~ndene Funk- tion in der Folge (F) enthMten.

Im Rekursionsschema a(nl,..., n~, a~, ,.., a~) und

~ ( .~ , . . . . n~, a) ~or . N u n steUige k-rekursive Funktion

D 8 kommen auflerdem die

entsteht abet ~o(nl, . . . , nk,

die 2 k - stellige Funktion (/r ~- 1)-stelligen Funktionen

im allgemeinen eine (k ~ r ) -

a~ . . . . . at) aus der ]~-stelligen �9 . . , n k - ~, no (n~), n~ (n~), . . . ,

an Stelle yon nk; nehmen

---- 1, 2, . . . , ]~ - i der Reihe

k-rekursiven Funk~on ~o (nl . . . . , nk) -- ~ (n I,

g,(n~)) dutch Einsetzen yon p:~. p~z . . . p:"

wit an, daft ~ , ~ ~ fiir i---- 1 , 2 , . . . , k - I ; j naeh aus

so enCstehen, wo. die FunkCionen ~, ~jo schon mit einem Index ~ / c ~-2

in (F) vorkommen; daft es also solche u, v J ~ k ~-2 gibt daft

x (n , , . . . , ~ ) = ~ , (n~, , . . , n J ; )~') (hi . . . . . n~) = ~ , , (n,, . . . , n~).

Dann gilt ~ die aus ~, flJ~} mit Hilfe des Rekursionsschemas D~ ent- stehende Funktion:

~ ( n ~ , . . . . n~) = ~ . (n~ . . . . , n~), w o w = 2" H

|

also ist diese auch in der Folge (F) enthalCen.

Mehrfache

24. Die Definition der Funktion lautet explizit aufgeschrieben:

[ n~, falls m =-0,

l~,ekursion. 521

~ ( n 1 . . . . . n~) = qz (m, n~ . . . . . ,~)

nk falls m = ]~-- l ,

n~ ,, m = k + l ,

~( - , (~), v ( ~ ( ~ ) , ~ , , n ~ ) , . , ~ ( ~ ~ 1 (~), ~, , . . . , ~ ) ) ,

falls m ~> k + 2, m ungerade,

1, falls m ~ k-f- 2, m gerade, n~.n 2 . . . nk = 0,

el(m, n l , . . . ,n~) = ~ (zro (m), n l - - 1 , �9 nk-1 -- 1, p~ k-1 .q~ 'p1(~''1,.1 ....... k) �9 "" Pqlk--l(m'~'~l'''"nk)k--I " Pkq~(m' n 1 . . . . , n k _ l , n k - - 1 ) ) ~

falls m :~ k + 2 , m gerade, n~.n~ . . . n~ ~ O, wo fiir i = 1, 2 . . . . . k - - l ,

~ , (m, n , . . . , n~) = ~ (m, n , . . . , h i - ~ , n~ - l ,

~(~r(~_~)(~_,) + 1 (m), n, -- 1, . . . , n~- i -- 1, 2

2 ~o 'k - - 1 " ~l-'q) (m, "1 . . . . . nk - - I, nk -- 1)) )

Diese Definition ist tats~chlich eine (k-~ 1)-fache Rekursion, und damit ist die Behauptung bewiesen:

Die (k 4-1)-[ache Reku~sion fiihrt is die Klasse der k-rekursiven Funktionen hinaus.

Es treten sogar bei dieser Rekursion auf der rechten Seite aul3er den Werten yon ~ lauter 1-rekursive Funktionen auf. Das iindert sich auch dann nicht, wenn die Definition auf die primitive Form zuriick- geftihrt wird. Es l~Bt sich also jede ( /~- 1}-rekursive Funlction aus 1- rekursiven Funktionen dutch Einsetzungen und dutch sine einzige solche

Definition D 8 aufbauen, worin ~ sowis sii~tliche ~(p 1-rekursiv sin& Werden die einze]nen Sehritte, die bei der Zuriietdiihrung der obigen Definition von ~ auf die primitive Form D s nStig sind, n~iher betrachtet, so ist daratm leicht einzusehen, dal~ jede (k -- 1)-rekursive Funktion in der Farm

(~1 . . . . , ~ ) = 7 (~, . . . . . ~ , ~ ( 0 1 ( ~ . . . . , ~,} . . . . , 0 , _ ~ ( ~ , . . . . . ~))) 9eschrieben werden kann, wobei q~ (nl, . . ., n~- l) dutch sine Reku~sion van

dev l~o~a D~ de]iniert wi~d und dabei sam~liche Funlctianen ~, fl~P, 7I und ~ 1-rekursiv sind.

522 R. Pdter.

w

Die explizite Form.

25. Nun .werde ich beweisen, da[~ eine jede k-rel~ursive Funkt ion v 2 ( n l , . . . , hi) in der ,,expliziten" Form

n , ) = (x, nl , .

geschrieben we~den kann, wo o~ (n) eine 1-~ekursive Funkt ion und B (m, nl, . . ., nz) eine 1-rekursive Beziehung ist (d. h. eine Beziehung yon der Form

(m, n l , . . . , n~) = 0

mit 1-rekursiven fl), /iir die es zu jedem n~ , . . . , nz ein m gibt derart, daft B (m, n~, . . . nz) zutri/fl; sogar wird sich ergeben, dal~ ffir jedes solche m

yJ (n,: . . . , n~) = cr (m)

gilt. Diese Behauptung werde ich (ira Hinblick auf das Schlul3ergebnis des vorigen Paragraphen) zun~iohst fiir eine Funktion beweisen, die duroh eine Rekursion Da:

~0(nl, . . . , nk) = 1, fails n 1 .n 2 . . . nk = 0, (n 1 + 1, . . . , n~ + 1) = ~ (n~, . . . , n~, ~0~ . . . . , ~k),

wo fiir i = 1, 2 , . . . , k

(') (n, + 1, . . , n ~ _ + 1, n~)), = ~ (n~ + 1 . . . . , n ~ _ l + 1, n~, f~, ( n , , . . . , n~, ~ �9 1

�9 . . , . . . . . + . . . ,

~,/~Jo (fiir i ---- 1, 2 . . . . . k - 1; j ~- 1, 2 . . . . . k -- i) rekursiv,

definiert wird. Der Grtmdgedanke des Beweises - d e r . wie in der Einleitung schon

erw~ihnt, yon I-Ierrn v. Neumann stammt - - ist folgender: zu jeder gegebenen Stelle (n~ . . . . . nk) gibt es eine ,,Berechnung" des FunkCionswertes yon cp an dieser Stel]e, d. h. eine endliche Folge yon Gleichungen der Form

~n(~t), . . . , n~ ~)) = w (~) (t ---- 1, 2, . . . , 1),

die aus Dz direkt oder vermSge friiherer Gleichungen tier Folge zu ent- nehmen sind, wobei n~ ~ ~ - n ~ , . . . , n(kz)- - nk ausf~llt; ist umgekehrt eine solche Berechnung gegeben, so kann man daraus den Wert yon q0 (n~ . . . . , n~) _ ( n (~) - - w (~ ablesen. Stat t ,,Gleichung r ~ , . . . , n(~ ~)) - - w (t)'' kann man bier ebensogut ,,(k ~- 1)-tupel (n~ 0 . . . . , n(~ ~, w(t)) '' sagen. Ordnet man nun alle (k ~-1)-tupel und die endlichen Folgen yon ( / r 1)-tupeln auf geeignete Weise in eine abgez~hlte Folge an, so stell~ sich die Eigensc, haft einer ~olge yon (k-~-1)-tupeln, eine Berechnung yon r (n~, . . . , n~) zu sein, als eine rekursive Beziehung zwischen dem Inde~ m der betreffenden Folge in jener Anordnung und n~ , . . . , n~ dar, und man gewinnt r (n~ . . . . , n~) ebenfalls in rekursiver Weise aus m.


26. Zuerst ist also folgender H_ilfssatz zu beweisen: Z u jed~r Stel le n 1 . . . . . nk gibt es eine endliche Folge

( i ) n~ , . . . , n~ ~), w(1)),

. . . , (F) (I)

n l . . . . . ~b (/), W (/))

yon (k 4- 1)- tupeln m i t n~ ~ = n 1 . . . . , n~ ~) = nk u n d yon [olgender g igenscha]t

B ( , ,Berechnungse igenseha#"): E s ist ]iir t = 1, 2, 3 , . . . , l entweder

o una w " ' = 1,

oder n~ t) . n~L).., n i t) ~ 0 und zuf]leich gibt es Zahlen 1 ~ ul . . . . . u,, < t

derart, daft w (') = ~r ) - 1 , . . . , n~ t ) - 1, w(~ ' ) , . . . ,w (Uk) ) ,

und [fir i = 1, 2 . . . . . k (t) nj , falls j < i,

(u~) (t) n~ = n, -- 1, falls j = i,

~'~-*t ~ - - 1 . . . . , - - 1, w(~'*~), falls i < j__~ k.

I s t (F) eine ~'olge der Eigenscha/ t B , so gilt / i ir t = 1, 2, . . . , 1

w( ' )= . . . ,

Die erste Behauptung gilt offenbar fiir n ~ . % . . . n , = 0 (man wghle als (F) die Folge mit dem einzigen Glied (n,, . . . , n~, 1)). Angenommen, dab sie fiir alle Vorgiinger der Stelle (nl, . . . , nk) gilt, wo n w . n ~ . . . n~ =~ O, so gibt es zun~chst eine Folge (F,) yon ( k + l)-tupeln yon tier Eigen- schaft B mJt einem letzten Glied v o n d e r Form

(% . . . . . nk- 1, nk - - 1, wk),

ferner weitere Folgen (F,), . . . , (Fk-~) yon der Eigenschaft B, so dab das letzte Glied yon (F,) die Form

(n,, . . . , n , _ , , n~-- 1, fl~,9 (n , - - 1 . . . . . nk-- 1, wk) . . . . .

besitzt (i = l, 2, . . . , k - - 1). Setzt man diese Folgen (F,) . . . . . (Fk-~), (F~) hintereinander und fiigt das (k q-1)-tupel

(n , , . . . , n~,, o,. (n , - - I , . . . , n ~ , - I , w , , . . . , w~,))

hinzu, so gewiant man eine Folge (F) yon der verlangten Beschaffenheit. In der Tat folgt die Eigenschaft B fiir das letzte Glied der Folge aus seiner Konstruktion, fiir die iibrigen Glieder aber aus der Eigenschaft B derjenigen Folge (F~), der das betreffencle Glied angehSrt, so da$ die BehaupCung auch fiir die 8telle (n,, . . . , n~) zutrifft.

524: R. P6ter.

Die zweite Behauptung gilt zun~ichst fiir n~ t) �9 n~ ~ . . . n~ ) -= 0 (also z. B. fiir t ~ 1), da dann auf beiden Seiten 1 steht. Es sei die Behauptung

flit alle u ~ t ( ~ l) start t giiltig und es sei n(~ ~ �9 n~ t) . . . n (t) ~ 0; dann gil t sie auch fiir t. In der Tat ist zun~chst

(u 7r . (t) (t) (t) w ( ~ ) = r *),.. . , n~ ) = q ( n l , . . . , n k _ 1 , n~ -- 1),

also gilt ftir i = 1, 2 . . . . , k -- 1

~ ) ( u t ) (u t ~ (u i ) �9

. . . j 7~t_1, 1,

o( f ) I ~b (t) ,t~ ~) _ . �9 . . , p k - ( ~ 1 - - 1 . . . . , 1, ~ ( n i t) . . . . , n ~ ) _ , , n(~ ) - - 1 ) ) ) ,

daher nach der Definition yon

w (') = ~ (n~ ~) - - 1, . . . , n(~ ') - - 1, w("~), . . . , w ( ~ ) )

= v ( ' T , . . . , - i ' ) ) .

27. Einer Zahl m ~_~ 1 ordne ich das (k-~ 1)-tupel

( ~ (m) . . . . , ~ (~), ~0 ( m ) ) zu; dann ist jedes (k + 1)-tup'el (wenigstens) einer Zahl ~ 1 zugeordnet

worden, n~mlich das (k + [)-tupel (n 1 . . . . . n~, w) der Zahl m = 2 w �9 3 ,h . . . p ~ . -- Ferner ordne ich jeder Zahl m ~ 2 auch eine endliche Folge y o n (k-~ 1)-tupeln zu; die Folge n~mlich, deren Olieder der Reihe nach den nichtversohwindenden Exponenten in der Primfaktorendarstellung y o n m zugeozdnet wurden. Dann ist jede endliche Folge yon (k-~ 1)-tupeln (wenigstens) einer Zahl ::> 2 zugeordnet worden; n~imlich die Folge, de ren Glieder der Reihe nach den Zahlen ml, . . . , m~ ~ 1 zugeordnet wurden, t ier

�9 ~'~l Zahl m 2~1 " 3'~ ..- P~ ~ 1.

Der Zahl m wurde dann und nut dann eine Folge yon der Eigen- schaft B zugeordnet, wenn folgendes zutrifft:

(1) m i > 2,

(2) es i s t f t ir t ~ m entweder

(2, I) ~t (m) ----- O, oder/4)

(2, 2) n~t (m)'g~t(m) . . . ~ t ( m ) = 0 und got (m) ~-- 1,

(2, 3) oder aber : ~ t ( m ) . : ~ t ( m ) . . . n~ t ( m ) ~ 0 und zugleich gibt es Zahlen u~ . . . . , u~ ~ t -- 1 derart, dab

(2, 31) g~ (m). n ~ (m) . . . n ~ (m) ~: 0 und

~) Ioh setze tier einfschen Schreibweise halber

~ehrfache Rekursion, 525

VII

v VII

§

I VII ~ ~ ~ ~ ~

~, VII ~ : ~ I~ ~

e

II

M a t h e m a t l s c h e A n n a l e n . 113.

+

~ 0

v ~CS

r

v

v

34

.I

+

.i

II

II §

li A

g t.4

d

526 R. P6ter.

Die der Zahl m zugeordnete Folge gilt dann und nut dann als e/ne Berechmmg yon ~ (nl, . . . . n~), d .h . /1~ letztes G1/ed hat dann und nur dann die Form (nj, . . . , n~, w), falls auBer B (m) noch folgendes zutrffft16): es ist iiir i = 1, 2 , . . . , k

~i~ (m) (m) = n~, d. h. falls

k

be~teht. Dies ist wiederum eine rekursive Beziehung B (m, n~, . . . , n~). 28. Aus dem I-Iilfssatz folg~ nun e~ten~, dab es zu jeder Stelh

( , , . . . , n~) eine Zahl m gibt, ftir die B (m, n , . . . , nk) zutrifft; zweite~s, daB, falls m eine beliebige (etwa die klemste) Zahl mit dieser Besohaffen- heir ist, so gilt,

gesetzt, ~ir iedes ~i . . . . , n~

e (n,, . . . , n~) = ~ (m), insbesondere

wie zu Beginn dieses Paragraphen behaup~et wurde. Es sei nun W (hi, . . . , n~) e/he beliebige k-rekursive Fun]~ion. Nach

dem Sohlu~ergebnis des vorigen Paragraphen gilt dann eine Darstellung

( - , . . . , n,) = ~ ( ~ , . . . , n,, ~ (~, (~ . . . . . n,) . . . . . ~ (-~ . . . . . n,)))

~ t 1-rekursiven ~, (~ . . . . . 8~, wobei IP durch eine Rekursion yon der b/sher betrachteten Form definiert wurde. Es gibt also eine 1-rekursive F u n ~ o n ~ und e/he 1-rekursive Beziehung B, so dab

10 Cn~ . . . . . n~) = ~ (m)

fttr jedes m zutrifft, ftir welches B (m, nl . . . . , n,) gilt, und dab es ein solches m gibt. Daher gilt,

B (m, (~i (nt . . . . , n~), . . . , ~ (n,, .. . , he)) = B' (m, n, . . . . , he)

gesetzt, ( n . . . . , n,) = ~ (~i . . . . . ~ , ~(m)) .

is) Hier bedeu~et die ~unktion )t (m) fiir m ~ 2 den Index r des grSBten Primteilers /~r yon m; R (0) ~- R (1) -- O. Der rekursive Cherakter yon ~ (m) kann z. B. aus der Daratellung

(m)---- 2: sg 2:n.(m)

entnommen werden; vgl. auch G~del, a. a. O. ~), S. 182, Definition 7. - - Man k~nnte den Gebraueh der Funktion ~ (m) ]eicht vermeiden, e~wa dadurch, dab man eine Folge (F) yon .(k-~ 1)-tupeln auch dann als eine Bereehnung yon @ (n~ . . . . . n~) betraehtet, falls ein (nieht notwendig das letzCe) Glied yon (F) die Form (n i . . . . . n~, w) hat.


fiir jedes m, fiir das B' (m, n I . . . . , nz) best, eht, und es gibt -- ftir jedes nl , . . . , nz - - ein solches m.

Man setze nun

B" (m, ,~ . . . . n:) = B' (=i (m), n, . . . . . nz) & 7 (n~ . . . . , n~, ~ (~i (e))) = =o (m);

dann ist B" -- ebenso wie B' -- eine 1-rekursive Beziehung. Offenbar gibt es Iiir jedes n I . . . . . n( ein m, liiz das B"(m, nl ,- . . , n:) zutrifft,

ni~mlich 3 ~o. 2 r("~ ..... -z ,~(~o)) falls B' (m o, n~ . . . . , n~) der Fall ist. Ist ferner m eine beliebige solche Zahl, so gilt zun~chst B' (~, (m), n~ . . . . , n:), also

. . . . . - , ) =

femer Y (n l , . . . , n,, r162 (~1 (m))) = =o (m); d. h. es gilt fiir jedes solche m

~/(n,,..., n~) = ~o (m), insbesondere

. . . . = =o (B" .1 . . . . , . , ) ) ) ,

wodurch die Behauptung des Beginns dieses Paragraphen auc]l im allgemeinen Fall bewiesen wurde.

29. Aus dem Beweis ergibt sich, dal3 die ,,k-rekursive Beziehung" y~ (n~ . . . . . n:) ---- 0 mit 17)

(s x) (B (x, n, ..., n:) & =o (x) = 0)

gleichbedeutend ist. Daraus folgt nach den Ergebnissen yon G6delXS), dab

V' ( n . . . . , n~) -= 0

eine arithmetische Beziehung ist.

iv) ( B x ) A ( x ) bedeutet wie iiblich: oa gibt eine Zahl x, ftir die A(x)gilt. is) A. a. O. g), Satz VII, S. 191.

(Eingegangen am 29. 6. 1936.)

Documents

Über die mehrfache Rekursion