PROBLEME DER HILBERTSCHEN THEORIE DER HOHEREN STUFEN VON REKURStVEN FUNKTIONEN

7o13

ROZSA Pt~TER (Budapest) (Vorgelegt yon L. KALMs

Einleitung !.

1. Unter rekursiven Funktionen werden diejenige zahlentheoretische Funk- tionen verstanden, welche von gewissen Ausgangsfunktionen ausgehend durch endlich viele Substitutionen und Rekursionen definiert werden k6nnen. Dabei kann der Begriff der Rekursion auf verschiedene Weisen abgegrenzt werden; so gelangt man zu verschiedenen Funktionenklaggen, die in der mathematischen Grundlagenforsehung bereits vielmals angewandt wurden. Die Untersuchung des Zusammenhanges der verschiedenen rekursiven Funktionenklassen wurde zuerst dutch die Art angeregt, wie HILBERT I das Konfinuumproblem in Angriff genommen hal. Hier handett es sich bekanntlich um die Vermutung, dab es zwischen dem Abz~ihlbaren und dem Kontinuum keine M~ichfigkeit gibt; und da die Menge der zahlentheoretischen Funktionen yon der M~tchtigkeit des Kontinuums ist, wollte HILBeRT jene Vermutung dadurch beweisen, dal~ er den immer gr61~eren transfiniten Zahten der zweiten Zahlklasse Rekursionen immer ,,h6herer Art" zuordnet, und dann z e i g t : die Annahme, daI~ die durch immer h6here Rekursionen definierten zahlentheoretischen Funktionen die Menge s~tmtlicher zahlentheoretischen Funktionen ersch/Jpfen, kann zu keinem Widerspruch ftihren. In diesen Untersuchungen wurde der Begriff der rekursiven Funktion yon hSherer Stufe eingeffihrt: man unterscheidet zwischen Funktionen der I-ten, lI-ten, IlI-ten Stufe, usw., je nachdem zu ihrem At~fbau blol~ Funktionen yon Zahlenvariablen, oder auch Funktionen yon Funktions- variablen, yon Funktionsfunktionsvariablen, usw. zugelassen werden (die Werte jeder dieser Hilfsfunktionen sind dabei jedoch Zahlen).

2. Zur Ausftihrung des Hilbertschen Programms w~ire vor allem not- wendig zu zeigen, dal~ die Zuiassung immer h6herer Stufen die entstehenden

1 D. H~LBERT, Uber das Unendliche, Math. Annalen, 95 (1926), S. 161-190.

248 R. PI~TER

Funktionenklassen immer erweitert: dal~ es z. B. rekursive Funktionen der !I-ten Stufe gibt, die auf der I-ten Stufe nicht definiert werden kSnnen. ACKERMANN" hat das ftir den Fall bewiesen, wo man sich auf einfache Rekursionen beschr~inkt (d. h. wobei die Rekursion nach einer einzigen Variablen verl~iuft): er hat n~imlich gezeigt, dal~ die a-re Funktion, die man dutch sukzessive Iterationen aus der Addition gewinnt, angewandt auf a und a, s~imtliche einfach-rekursiven Funktionen der I-ten Stufe majorisiert, und auf der ll-ten Stufe dutch einfache Rekursionen definiert werden kann.

Aber ACKERMANN hat ftir seine Funktion auch eine rekursive Definition auf tier I-ten Stufe angegeben, wobei die Rekursion ,,zweifach" ist, d. h. nach zwei Variablen simultan verl~tuft (in solchem Fall heigt die definierte Funktion ,2-rekursiv" ). Werden sowohl auf der I-ten, wie auf der If-ten Stufe auch mehrfache (nach mehreren Variablen verlaufende) Rekursionen zugelassen (und somit ,,k-rekursive" Funktionen ftir beliebige /c definiert), so ist es bis heute noch nicht entschieden, ob die Zulassung der II-ten Stufe die Klasse der rekursiven Funktionen der I-ten Stufe erweitert oder nicht.

3. In einem Vortrag am InternationaIen Mathematikerkongrefa in Oslo (1936) babe ich behauptet, dal~ die Klasse der mehrfach-rekursiven Funktionen der I-ten Stufe mit der Klasse der einfach-rekursiven Funktionen der II-ten Stufe identisch ist. Ich konnte ngtmlich beweisen, daft sich eine jede mehffache Rekursion der l-ten Stufe auf der lI-ten Stufe auf einfache Pekiarsi0nen auflSsen lgtl~t 3 (den allgemeinen Beweis dieser Tatsache gebe ich in w 1); ferner hatte ich eine sehr verwickelte Methode zur Zurtickftihrung der ein- fachen ,,primitiv-rekursiven" Definition einer Funktion der II-ten Stufe auf eine mehrfache Rekursion der I-ten Stufe (meine Notizen tiber die letztere Methode sind w~ihrend des Krieges verloren gegangen). Eine Rekursi0n heifit dabei primitiv, wenn die in der Rekursion nicht teilnehmenden Variablen (,iParameter" genannt)unver~indert bleiben, also keine Einsetzungen ftir die Parameter erf01gen (jedoch kOnnen die Parameter auf der lI-ten Stufe ,,ge- bunden" sein); und e s ist mir frtiher gelungen zu beweisen, 4 dal~ auf der l-ten Stufe s~imtliche Rekursionen, in welchen ftir die Parameter die ver- wickeltesten (sogar yon frtiheren Werten der zu definierenden Funktion abhangigen) Einsetzungen erfolgen (,,eingeschachtelte Rekursionen" genannt), auf einfache primitive Rekursionen und Substitutionen aufgel/3st werden k/Snnen. Die am Osloer KongreI5 ausgesprochene Behauptung beruhte auf der Annahme,

W. ACKERMANN, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Annalen, 99 (1928), S. 118--133.

R. P~TER, Rekursive Funktionen (Akademischer Verlag, Budapest, 1950), S. 97--102. R. PATER, l]ber den Zusammenhang der verschiedenen Begriffe tier rekursiven

Funktion, Math. Annalen, 110 (1934), S. 612-=632. - - Siehe noch: A rekurziv ftiggv6nyek elm61et6hez (Ungarisch mit deutschem Auszug), Matematikai ds Fizikai Lapok, 42 (1935), S. 25--49.

HOHERE STUFEN VON REt~URSIVEN FUNIs 249

dab diese Aufl6sung auch auf der II-ten Stufe m6glich ist. Aber in gewissen - - f i i r die II-te Stufe cha rak te r i s f i schen- F~illen wtirde das gleiche Auf- 16sungsverfahren die Definition einer unendlich-vi~elstelligen Funktion ( g e n a u e r gesagt: einer Funkfion mit einer ver~inderlichen Anzahl von Variablen) erfor- dern, wie in w 4 vorliegender Arbeit gezeigt wird.

4. In w gebe ich eine durchaus einfache neue Methode zur Zurtick- ffihrung der primitiv-rekursiven Definition einer Funktion der II-ten Stufe auf eine mehffache Rekursion der I-ten Stufe. Die Methode l~l~t sich ohne weiteres auch auf solche eingeschachtelten Rekursionen anwenden, die ~ihnlich wie auf der I-ten Stufe gebi!det werden, n~imlich auf solche, wobei nur an Stelle vor~ Zahlenvariablen Einschachtelungen erfolgen; sogar dann, wenn es sich urn eine mehrfache Rekursion der lI-ten Stufe handelt; dies sieht man deutlich am Beispiel des w 3.

Die betrachtete Art einfache eingeschachtelte Rekursion l~il~t sich auf der II-ten Stufe sogar auf Substitutionen und primitive Rekursion zurtickfiihren.

So scheint es im ersten Augenblick, als ob die ll-te Stufe gar nicht mehr liefern k6nnte, als die I-re.

8. Es kann jedoch auf der II-ten Stufe auch eine neue Art eingeschachtelte Rekursion auftreten : eine solche, wobei Einschachtelungen auch an den Stellen der Funktionsvariablen eff01gen. Wie das Beispiel in w 4 zeigt: wenn die Methode in einem solchen Fall angewandt wird, so erh~ilt man auf der l-ten Stufe die mehrfach-rekursive Definition einer Funktion 0 yon unendlich vielen Variablen; d .h . es h~ingt v0n einem der Argumente ab, wievielstellig bei diesem Argument 6 ist. Eine solche Funktion kann auch durch Substitution einfach-rekursiver Funktionen aus einer einstelligen Funktion erhalten werden,. welche durch eine transfinite Rekursion vom Typus co w definiert wird.

6. So liegt es nahe zu glauben, dal~ die unendlich-vielstellige Diagonal- funktion ga der mehrfach-rekursiven Funktionen der I-ten Stufe ~ (welche sich von allen mehrfach-rekursiven Funktionen der I-ten Stufe unterscheidet ) eben- falls zu den rekursiven Funktionen der II-ten Stufe geh6rt; diese Diagonal-- funktion l~il~t sich ja ebenso wie 0 mit Hilfe einer mehrfachen Rekursion mit variabler Vielfachheit (oder mit Hilfe einertr~/nsfiniten Rekursion vom Typus a~) definieren. K6nnte man das beweisen, so h~itte man ein Beispiel ffir eine rekursive Funktion der lI-ten Stufe, welche nicht zur Klasse der-rekursive~ Funktionen der I-ten Stufe gehOrt.

Betrachtet man aber n~iher die ,,unendlich-vielfache" Rekursion, welche. unsere Funktion d, und jene unendlich vielfache Rekursion, welche die Diagonalfunktion ~ definiert, so entdeckt man einen Unterschied, den ich folgenderweise bezeichnen werde: die Definition von ~p ist ,,vollz~ihlig-mehr-

5 R. PI~TER, Zusammenhang der mehrfachen und transfiniten Rekursionen, Journal of Symbolic Logic, 15 (1950), S. 248--272.

250 R. PI~TER

fach", die Definition von d daffir ,,zerstreut-mehrfach". Ergibt sich nfimlich nach der Angabe eines gewissen Argumentes, daft ~, dabei z.B. r-stellig ist, so massen (far n~. n2.. . n r + 0 ) zum Aufbau yon ~o(nl, n2 . . . . , n~) sowohl solche Funktionswerte angewandt werden, wobei das erste Argument kleiner als nl ist, wie auch solche, wobei das erste Argument n~, das zweite kleiner als n ist, und so weiter ltickenlos ganz bis zum Funktionswert ~ (n~, . . . , n,._l, n,.--1) 2. Bei der Definition yon 6 gibt es aber eine ganz bestimmte Zahl k, so daft, wie grog auch r sein mag, wenn sich d" nach der Angabe eines gewissen Argumentes als r-stellig ergibt, im Aufbau yon d(m~, m , , . . . , m,) blofi solche frfihere Funktionswerte teilnehmen, bei welchen h0chstens k tier Argumente (aber an anderen Stellen andere) kleiner als das entsprechende m~, m~, . . , oder m,. sind, wghrend die frtiheren Argumente den entsprechenden m~, m~, . . , gleich sind.

7. In w 5 werden offene Probleme beztiglich der ,,zerstreut-transfiniten" Rekursion dargelegt. Die Frage, ob es uneinschmelzbare Zwischendinge zwischen den transfiniten Rekursionen vom Typus rd ~ mit endlichem k und zwischen der vollz~ihligen Rekursion vom Typus m ~~ gibt, lautet gewissermaben ~hnlich, wie das Kontinuumproblem.

Zum Beweis, daft die If-re Stufe umfassender als die I-te ist, bietet sich auger dem Diagonalverfahren eine Ausdehnung des Ackermannschen Beispiels. Das Ackermannsche Majorisierungsverfahren kann aber, wie in w 5 nahegelegt wird, far mehrfache Rekursionen nur soviel ergeben, daf5 es eine durch k + 1 einfache Rekursionen der II-ten Stufe definierte Funktion gibt, die keine k-rekursive Funktion der I-ten Stufe ist (was auch viel einfacher eingesehen werden kann); so kommt man aber auch nicht zu einer Funktion der If-ten Stufe, welche von s~imtlichen mehrfach-rekursiven Funktionen der I-ten Stufe verschieden ausfallen, n~imlich s~imtliche solche Funktionen insgesamt majori- sieren wtirde.

Man gewinnt den Eindruck, dab die Ausdehnung des Begriffes der rekursiven Funktion der I-ten Stufe, wie man es auch versucht, ganz nattirlich die Einftihrung einer ver~inderlichen Anzahl yon Variablen, einer ver~inderlichen Anzahl yon Definitionsgleichungen erfordert. Daft es bisher nicht gelungen ist, die meisten Probleme der II-ten Stufe zu 10sen, h~ngt damit zusammen, dab man sich auch auf der II-ten Stufe auf Funktionen mit einer festen Anzahl yon Variablen beschr~nkt, welche durch eine feste Anzahl yon Substi- tutionen und Rekursionen definiert werden.

II.

8. Ich werde folgende Zeichen benutzen: far Zahlen und Zahlvariablen kleine lateinische Buchstaben (wenn die Zahlenvariablen gebunden sind, vom Ende des Alphabetes) ; far Funktionen und Funktionsvariablen kleine griechische Buchstaben ; far Funktionsfunktionen grobe lateinische Buchstaben. Gebund~ne

H~HERE STUFEN VON REKURSIVEN FUNICTIONEN 251

Variablen werden in jenem Sinne verstanden, wie in einem Integral b

dx

die Variable x gebunden ist: der Wert dieses Integrals h~ingt nicht yon x, sondern yon ~f(x) als Funktion von x und yon den Zahlen a und b ab. Ein Ausdruck, der yon mehreren Variablen abh~ingt, kann als Funktion von beliebigen seiner Variablen aufgefaI~t werden; um zu bezeichnen, welche diese Variablen sind, benutze ich das yon CHURCh 6 eingeffihrte Zeichen ). So bedeutet z.B.

die Funktion a ~ als Funktion de s Funktionsfunktion

A (~; b)

eingesetzt, wobei ~p eine einstellige Funktionsvariable ist, zahl~ntheoretische Funktion von a und b, 1st hier z.B.

A(~; b) = ~(b~),

so ist

Exponenten; und wird das far r in eine

so entsteht eine

A (,~ x[a~]; b)~-a ~.

Die verschiedenartigen Variablen werde ich auch in den Folgenden durch einen Strichpunkt trennen.

Bezaglich der allgemeinen Kenntnisse aber rekursive Funktionen berufe ich reich auf mein Buch, 7 worin diese zusammengefalSt wurden. Die gebr~iuch- lichsten Funktionen der elementaren Zahlentheorie haben sich alle als einfach- primitiv-rekursiv auf der I-ten Stufe erwiesen, so z.B. auch die in den Folgenden benutzten Funktionen

P0 - - 2

p,,§ = die n-l- 2-te Primzahl ,

exp~(n)--:der Exponent yon p(~ in der Primfaktorenzerlegung von n,

max (n~, . . . , n l , ) ~ d a s grOf3te yon m , . . . , nl..

6 A. CHURCH, A set of postulates for the foundation of logic, Ann. of Math., 34 (1933), S. 863.

Siehe Fugnote ~

252 R. P~TER

w 1. Aufl~sung der mehrfachen Rekursionen der l-ten Stufe auf einfache Rekursionen der ll-ten Stufe

1. In einigen Spezialf~illen habe ich bereits gezeigt, 8 wie sich die mehr- fachen RekurSionen der I-ten Stufe auf einfache Rekursionen der ll-ten Stufe aufl6sen lassen. De r allgemeine Beweis kann genau so geffihrt werden.

Die allgemeine k-fache Rekursion l~l~t sich auf folgende ,Normalform" zurtickftihren 9 (ftir nl. n~... n~, = 0 k6nnte der Wert yon , ( n , , n~ . , . . . , nj.) beliebig gewahlt werden) :

-(nl , n~, . . . , nj. ,)=0, falls n l . n 2 . . , n j~- - -0

-(n~ + 1 , . . . , n,~ + 1) = p ( n l , . . . , n,~, ~ , - , . , . , ~ ) ,

wo f~ir i ~ - 1 , 2 . . . . ,k

{~L :{27(n1 -~ - 1 , . . . , n,:_ 1 ~- I, n~, 7~i)(nl , . . . , n/c, ~(nl - ~ l , . . . , /r/k_: + I, n k ) ) , . . .

.(o . . , , ( n ~ + 1, , n~ ~ + 1, nk))), �9 �9 . ~ y h - ~ ( n j ~ . / 7 / :~ . .

wobei die Funktionen fl und 75 ~ ftir i = 1, 2 . . . . . k - - 1 ; j ~ - 1, 2 , . . . , k ~ i aus den in der ursprtinglichen (nicht normierten) Definition angewandten Funk- tionen (aus den ,,Bausteinen" yon , ) d u r c h einfache primitive Rekursionen der I-ten Stufe und Substitutionen aufgebaut werden k6nnen.

Nun werde ich diese Definition auf k einfache Rekursionen der II'ten Stufe aufl0sen. Sei k > 1. Werden die Funktionen

, ( n , xx . . . . , x,,_~), , ( n ~ + 1, n~,x~ . . . . . xk_~), . . . , - ( n ~ + 1 , . . . , n~ 2 + 1, n,,:_~, x,)

durch die Funktionsvariablen r r . . . . , ~-1 ersetzt, so ergibt die Definition start -,~ - -(n~ + 1, . . . , nj~_~ ~- 1, m.) eine Funktionsfunktion A0(%,.. . , 5o~-1; n~,..., nk):

Ao(fpa, , . ., ~k- l'~ n l , . . . , nl,-1, O ) = 0

A o ( ~ l , . . . , ~k:l; n l , . . . , n~-l, nT~-~-1)=

,a(nl , . . . . , nk, B1 , . . . , Bh-1, A0(f~l, .-.., ~0k-1; h i , . . . , nk)),

wobei fiJr i = 1, 2 , . . . , k - - 1

B , = ~ , ( ~ , ~ ~ , , , A , , ( ~ . . . . , ~ , ~ ; n l , . . , n , , ) ) , . .

. ( 0 [ n . . . . . . . . . . . yk-~ ~, ., n,~, Ao(~, , q~,,x; n~, ., nk))).

Man sieht leicht, dab

A o ( , ~ x ~ . . . x,~ ~[,~(n~, x ~ , . . . , x,~_~)], Z x ~ . . x , _ ~ [ , ( n ~ + I , n~ , x~ , . . . , x~_~)],.. .

. . . , ~,Xa[a(na~- 1 , . . . , nl~-~- l, nk-1, X1)]; n l , . . . , n~) ~ cr 1 , . . . , n~-x ~- 1, n~)

gilt. Ftir n~ ~ 0 steht n~imlich an beiden Seiten O; und wenn die Behauptung ftir ein n~ bereits gilt, so ist

s Siehe Fufinote ~. 9 R. P~TE~, Uber die mehrfache Rekursion, Math. Annaten, I13 (1936), S. 489--527

HOHERE STUFEN VON REKURSIVEN FUNts 253

A o ( f l x l . . . xk_l[c~(n~, x l , . . . , x~._~)],...,2x~ [e(n~ § 1 , . . . , nk_~ ~- 1, n,~_l, Xl)];

; n l , . . . , n,,: 1, n~. 4- 1 ) =

= 9 ( n l , . . . . . . , n,,, B ' I , , B'~_I, Ao (~X~ . . . . . . x,._~[~(n,, xl, , x M ) ] . . . .

. . . , 2 xl[c~(n~ -k i , . . . , n~_:} q- 1, nj~_~, x l ) ] ; n ~ , . . . , m . ) ) ~

- = b~(//1 . . . . , / / , , , B~, . . . , B 7 - 1 , ~z(//~ -~- 1 , . . . , nt~ 1-~- 1,/ /1~)),

wobei ftir i ~-~ 1, 2 , . . , k - - 1

B ~ = ~(n~ + 1 , . . . , n ~ _ ~ + 1, n,:, 7~'~(n~ . . . . , n~., ~ ( n l + 1 . . . . , n , , ~ + 1, n , , ) ) , . . .

,(o , . . , ~ ( n , + l , . . . , + l , n~) ) ) ~ ; �9 �9 "~ [ k - i V l l ~ ' ' / / Ic~ / / k - 1 ~ -

nach der Definition yon ~ ist daher

d(n~ . . . . , m,,, B~, . . . , B;~_~ , c~(n~ q- 1 , . . . , nT,._~ q- 1, &~) )

So fibertragt sich die Behauptung yon nk auf n~-k 1 ; demnach gilt sie allgemein.

Die beiden Gleichungen

c c ( n ~ , . . . , nlr - - O, falls nz. n~... nk_~ = 0

~ ( n l q- 1 , . . . , na,_~ q- 1, m , ) = Ao(Xx~. . .x,.. l[a(na, x~ , . . . , x,,, ~)],...

�9 . . , ; .xd ,~(n , + 1 , . . . , n,~_., + 1, n,, 1, x0 ] ; n ~ , . . . , n,3

ergeben eine k - - l - f a c h e Rekursion der II-ten Stufe ftir a.

2. Ich werde abet jetzt die Einsetzungen von 2xl. . . x,~_~ [,~ ( n , x ~ , . . . , x~_~)],..., ~x~[c~(nz-k 1 , . . . , n~_~-k 1, m,--~, x0] f~ir q~l,.. . , q~,--~ schrittweise ausftihren ; so gelange ich fiber lauter einfache Rekursi0nen zu c~.

Sei also

A~ ( ~ . . . . . ~ 2; n ~ , . . . , nk-~, O, n~,)-~ 0

A ~ ( ~ , . . . , 9~_2; n l , . . . , n~,._~; n~,~ ~ + 1, n~,,) ~ -

- - - A o ( q ~ , . . . , q:~:_~, 2 x~[A~ (9~, . . ., q ~ ; n~ , . . . . n~_~, xO]; n, . . . . . n,.),

A,_,(~,. . . , q~,_~; n~ . . . . , &~_~, O, nk_~, n~.) = 0

A ~ ( ~ , . . . , ~ / , r -~- 1, //~;=1, //1,)=--

= A ~ ( q ~ , . . . , ~fk-a, )ox~x~[A~ ( ~ 1 . . . . , ~,,:_~; n~, . . . , n,__~, x~, x~)]; nz , . . . , n~.),

ffir O < i < k

A,~(q~,..., q~,.-1-~; nl . . . . , n,~ ~_~, O, m,-+l , . , . . . , n~,) = 0

A,:(5~ ~;-1 *;//1, .- . , n~_~_,, n~_,q- 1, &~+~_r n~ . ) -

m A,: 1((t91 . . . . , ( p ] c - 1 [ , I ]~Xl �9 �9 .x,:[A~(cp~,..., ~ J ~ i r i , X l . . . . , X,:)] ; / / i , . . . , / / ' 0 ,

zuletzt A~-:I(O, n.2,.. . , //k) : 0

Ak ~(nz q- 1, n. , , . . . , n , . ) = A,~_,a(2X~... x~-i [Ak-1 (n~, x l , . . . , xg-l)] ; rta . . . . , / /~).

17 Ac/a Mathematica

254 R. P~TER

So ist A k . l ( n l . . . . . n,,) eigenttich keine Funktionsfunktion mehr, sondern eine zahlentheoretische Funktion. Ich behaupte, dab

A,, 1 ( n l , . . . , n t . ) = ~ ( n , , . . . , m )

gilt�9 Das ergibt sich leicht aus folgendern

HILFSSATZ. F O r r = 0, 1 , . . . , k - - 1 g i l t

A, . -1 ( n l @ 1 . . . . . 1 , . @ 1, 1, .+1, . . . , n,,:) = A,~_l_,.()~x1 . . . . x,~ 1 [A,~_I (1ll, x l . . . . . x l , . - , ) ] , . . .

. . . , Zxl . . .x ,~_~.[Aj~ 1 ( n 1 @ 1 . . . . . n,,_l + 1, n,., x l , . . . , x~;_,.)]; n l , . . �9 n~,.).

Dies ist nfirnlich ffir r - - -O trivial; und falls die Behauptung far ein r < k 1 bereits gilt, so folgt dutch Einsetzung von n,.+~4- 1 ffir n,.+l

A,,. l (nl 4 - 1 , . . . , n,.+, 4- t , 11,.+,_, . . . . . 11;..) = A M ,.(Zxl. �9 x,,._ ~ [A (n~, x~ . . . . , xT,,-1) , . .

�9 " v f l x ~ . . , xj~_,.[A~,:_l(n~ 4- 1 , . . . , n,._~ 4- 1, n,., x , , . . . , x,.~ ,)];

; 111, �9 � 9 T/,.+I 4 - 1, n, .+~, . . . , 11#).

Hier kann abet die rechte Seite nach der Definition auch als

A,, ,-1-0.+I)()~X1 �9 . �9 x , : - I [A,:-I (11j, Xl . . . . , X/ , ' - l ) ] , �9 �9 �9

. . . . Lx~. . . x,, , [A,~-i (n t 4 - 1 , . . . , 11,.-1 4 - 1, 11~ , x~, . . . , xk_,.)],

, Zy , . . .y~ l_~.[Aj,_~_,.(2x~.., xj, ([A~,,_~(11,, x~ . . . . , x~,_,.)],...

. . . , ,~x~. . . x~. , [A~ ~(1114- 1 . . . . ,11~_: 4 - 1, n, , x~, . . . , x~.: ,)];

; n ~ , . . , n,.+~, y ~ , . . . , y~,_~_,.)] ; 11~,..., n,.,)

geschrieben werden, und nach der Annahrne ist darin

A k - 1 r('~Xl - . - Xlc-1 [ A I : - I (111, x , , . . . , Xl,. 1)], . . , ~ . x ] . . . Xl . ._r [ ~ k - I (111 4- 1 . . . .

. . . , n,.-1 4 - 1, n , , x~ . . . . . xj, ~)] ; n ~ , . . . , n ,+l , y ~ , . . . , Y~.,-I-,) ~ -

Al~_~(th 4 - 1 , . . . , n , .4 - 1, 11,+i, y~, . . . , Y~-1 ,);

so ist endlich (die gebundenen Variablen y ~ , . . , yj._ j , wieder rnit x~ , . . . , xj.,_~_,. bezeichnet)

A~_l(n~ 4 - 1 . . . . , n,+t 4- 1, n,,+2, . . . , m,)

A,..-1-(,.+I)(Zx~. . . x,.,-1 [A,,: l ( n l , x~ . . . . , x,~, ~)] . . . .

. . . . 2x~. . . x ~ - , . [ A ~ , - l ( t h 4 - 1 , . . . , 11,.-14- 1, n, , x~, . . . , x,~ ,)],

, Z x ~ . . .x~, 1-,.[A,~-~(11~ 4- 1 , . . . , n,. 4 - 1, 11,.+~, x~, . . . , xj._~_,.)] ; n l , . . . , m.).

Die OtHtigkeit des Hilfssatzes fibertr~gt sich also yon r auf r4- 1, solange r < k - - 1 ist; und demnach gilt der Hilfssatz allgernein.

3. Speziell ft~r r ~ k - - 1 ergibt der Hilfssatz :

A,;_l(nl 4- 1 , . . . , n~_~ 4- 1, n~,) ~ A0(Lx~ . x~_a [AM (n~, x~ , . . . , x~;_l)],...

. . . , ZXl[A~,.~l (n~ 4- 1 . . . . , m~-,_, 4 - 1, m~-~, x~)]; n~ . . . . , n,,).

Nun kornrne ich zurn Beweis yon

n,,)---.(11,,..., 11,3. Erstens gilt diese .Behauptung ffir n t . n . ~ . . , nl,:=O. In diesern Fall ist nftrnlich c~(n~,..., m . ) ~ O ; und falls das erste verschwindende Argument n,.+t ist, so

HOHERE STUFEN VON REKUt%SIVEN FUNKTIONEN 255

5st der Wert von Aj~- l (n l , . . . , nj.) mit dem Wert yon A#_~, an einer solchen Stelle idenfisch, wo far die r-I- 1-te Zahtenvariable 0 eingesetzt wird ; an einer solchen Stelle ist aber nach der Definition der Wert yon A~-l-r auch 0.

Nehmen wir jetzt an, dal5 die Behi~uptung bereits far alle Vorg~nger einer Stelle ( n l @ l , . . . , n ~ - t - 1 ) gilt (als Vorg~nger werden solche Stellen betrachtet, wo das erste Argument nl, oder das erste Argument n;@ 1, das zweite n~, usw., endlich wo das erste Argument n~-b 1, das zweite n2@ 1 . . . . , alas k - - l - t e n~-l-~ i, und das k-te nj. ist). Dann ergibt sich aus dem Hilfs- satz f(ir r = k - - 1

A1,,-1(r/1 @ 1, . . . , nk-[- 1 ) = Ao(,tx, . . .x, 1[Cr . . . . ,'X/r-l)], �9 . �9

�9 . . , ~'Xl[~;g(nl@ 1 , o . . , //1._2 @ I , //1;-1; Xl) ] ; nl . . . . , Y/I.-).

Von der rechten Seite hat es sich aber in Nr. 1 bereits herausgestellt, dab sie mit c~(n~-t-1,..., n~,@l) identisch ist. Es ist also tatsachlich

A,,_~(n~ @ 1 . . . . , n,. ~- 1) : - ~(n~ @ 1 . . . . , n,.,-t- 1).

So ist es gelungen, die Funktion a(n~, . .... n~..), welche urspranglich aus gewissen schon frtiher definierten , ,Bausteinen" dutch eine k-fache Rekursion definiert wurde, durch k einfache Rekursionen der IX:ten Stufe zu definieren. Da aber sfimtliche mehrfach-rekursiven Funktionen der X-ten Stufe yon 0 und n @ 1 ausgehend dutch eine endliche Kette yon Substitutionen und mehrfachen Rekursionen der I-ten Stufe aufgebaut werden k6nnen, folgt daraus, dal3 sich diese Funktionen alle auch durch Substitutionen und einfache Rekursionen tier II-ten Stufe aufbauen lassen. Dabei hat man auf der II-ten Stufe zu den Grundfunktionen 0 und n@ 1 auch die Grundfunktionsfunktionen

VI(Y-J~ ; a ) : (p(a) , V g((~; a l l a.2) : ~[~(al, a2) . . . . , gi(cfl; a~ . . . . , a z ) - - - ~ ( a l , . . . , a i ) , . . .

hinzuzunehmen.

w 2. Zuriickflihrung der primitiven Rekursionen der ll-ten Stufe auf mehrfache Rekursionen der l-ten Stufe

1. Betrachten wit nun ein einfaches ,der ll-ten Stufe. Sei

W O

~nd

Beispiel einer rekursiven Funktion

6(0, a) = a

~ ( n + 1, a ) = B(,~x[~(n, x)]; n, a),

B (~; 0, a) = ~ (a ~) B@; n+ 1, a) = C(,~x[8@; n, x)]; n, a),

c ( f ; o, a) = ~(a) c(~; n + 1, a) = ~ (c@; n, a)).

256 R. PI~TER

2. Ich nenne diese "Rekursionen primitiv, obwohl der Parameter a yon' und B in B(;Cx[a (n, x)] ; n, a) und in C(,~x[B(~; n, x)]; n, a) nicht unver~indert

geblieben ist. Eine solche Bindung des Parameters ist aber unvermeidlich auf der ll-ten Stufe. Denn die Definition soil eine zahlentheoretische Funktion ergeben, durch Vermittelung gewisser Funktionsfunktionen. Es treten also im Aufbau der definierten Funktion auch Funktionsvariablen auf; diese mfissen aber zum Schlug verschwinden. Verschwinden sie blog dadurch, dab bekannte Funktionen far sie eingesetzt werden, so h~tte man yon Anfang an statt Funktionsvariablen diese bekannten Funktionen anwenden kOnnen, und so. h~tte man garnicht aus der I-ten Stufe heraustreten sollen. (Vgl. die Methode der ,,Rtickverlegung der Einsetzungen" in der Beweistheorie.) Durch eine Rekursion verschwindet aber eine Funktionsvariable blog dann, wenn die: zu definierende Funktion, mit kleineren Werten der Rekursionsvariablen, als Funktion gewisser Parameter far sie eingesetzt wird.

In der Definition yon B (oder von cr k6nnte freilich ein frfiherer Funk- tionswert auch far eine Zahlenvariable eingesetzt werden. Ein solcher Fall l~if~t: sich aber immer auf einen Fall, wo die Einsetzung des frfiheren Funktionswertes, (als Funktion gewisser Parameter betrachtet) ftir eine Funktionsvariable erfolgt, und auf Substitutio.n zurtickffihren. Betrachten wit z.B. folgende Definition:

a)

n + 1, a) = BI( ; n, a), a). Sei

so ist C~(q), 4; a)=C(qs; ~p(a),a),

BI((~; n -~ 1, l]) - - Cl((fl, 2 x [ B l ( ~ ; n, x)]; a).

3. Nun kehren wir zuriick zur obigen Definition von a(n, a). Diese Definition ist darum eine Rekursion der II-ten Stufe, weil darin auger der ztt definierenden zahlentheoretischen Funktion a(n, a) auch die Funktionsfunktionen B(~;n,a) und C(q);n,a) vorkommen. Offenbar braucht man aber diese Funktionsfunkti0nen zur Definition yon a(n,a) nicht far eine beliebige Funktion q; sondern nur ffir gewisse spezielle (selbstverst~indlich mit der zu definierenden Funktion r in einem gewissen Zusammenhang stehende) Funk- tionen; z.B. braucht man die Funktionsfunktion B nur far q~=),x[a(n, x)]. Eine Funktionsfunktion geht aber ftir eine spezielte Wahl ihrer Funktionsvari- ablen in eine Funktion yon Zahlenvariablen fiber. Daher kann man versuchen, die Definition yon a sozusagen auf die l-te Stufe zu fibersetzen, indem man die Funktionsfunktionen B und C durch jene zahlentheoretischen Funktionen ersetzt, die aus ihnen durch Einsetzung derjeniger speziellen Funktionen far q~ entstehen, far die man jene Funktionsfunktionen z u r Definition yon a(n,a} braucht. (Falls dabei B oder C far mehrere, ffir q5 eingesetzte, spezielle Funktionen gebraucht wird, so wird sie nattirlich durch mehrere zahlentheore- tische Funktionen ersetzt.)

H O H E R E STUFEN VON REKURSIVEN FUNKTIONEN 257

Dieser Zurackffihrungsgedanke l~il3t sich aber nicht ohne weiteres durch- fahren. In der Tat, man kann start der Funktionsfunktion B(rf; 1l, a) nicht die zahlentheoretische Funktion

~(~, a ) -B(~ .x [~(n , x)]; n, a) durch Rekursion definieren, da B(~; n, a) durch Rekursion nach seinem zweiten Argument n definiert wurde, und n kommt in #(n, a) auch als Argument yon 2x[a(n, x)] vor. Wird daher

f l (n+ 1, a )=B(2x[ ,~ (n+ 1, x)]; n + 1, a)

mit Hilfe der zweiten Rekursionsgleichung yon B berechnet, so erh~.lt man

#(n-t- 1, a) = C(2x[B(2y[e(n + 1, y)]; n, x)]; n, a)

und bier kann man start B(2y[cc(n-[- 1, y)] ; n, x) nicht die Funktion ~ einfahren {auch nicht durch Verwendung der zweiten Rekursionsgleichung yon ~, die nur

,@(n + 1, a) = C(2x[B(2~y[B(2z[e~(r!, z)]; n, y)]; n, x)]; n, a) =- = C ( 2 x [ 8 ( ~ y [ ~ ( n , y)]; n, x)]; n, a)

ergibt, wobei man B(~.y[~(n, y)]; n, x) wiederum nicht durch ~ allein aus- dracken kann).

Daher soll die Rekursionsvariable n yon B yon dem mit ihr zuf~illig zusammenfallenden Argument n yon ,~x[c~(tl, x)] unterschieden werden, d .h . .es soll statt der obigen Funktion #(n, a) die Funktion

~'(nl, ,~, a ) = B(,tx[~,(n~, x)]; n.~, a) betrachtet werden. Mit Hilfe dieser Funktion l~13t sich die.zweite Rekursions- gleichung tier Funktion c~(n, a) wie folgt schreiben:

c~(n + 1, a) = ~(n, n, a). Ferner gilt nach der ersten Rekursionsgleichung der Funktionsfunktion B(~o; n, a) die Gleichung

;(n~, o, a) --B(~x[~(n~, x)]; O, a) -----~(n~, a~), und nach der zweiten Rekursionsgleichung von 13,

~(n~, n~ + 1, a) = B(,tx[~(n~, x)]; n~ + 1, a) = = C(2x [B(2y[e(th, y)]; n2, x)]; n~, a ) = C().x[/~(/~I, n2, X)]; tr/,2, a).

SO braucht man zur Definition der Funktion #(n~, n~, ~z)(start der Funk- tionsfunktion C(,;c; n, a) fiir eine beliebige Funktion q~) nur die .zahlentheore- tische Funktion

~,(n~, n~, a) = C(,tx[~(n~, n~, x)]; n~, a).

Nun ist es aus dem gleichen Grunde wie vorher nOtig, die Rekursions- variable n~ yon C yon dem mit ihr zuf~llig zusammenfallenden Argument n.~ yon 2x[,~(n~, n.2, x)] zu unterscheiden, d .h . start dieser dreistelligen Funktion 7 die vierstellige Funktion

258 R. P~TE~

zu betrachten. Mit Hilfe dieser Funktion lfigt sich die zuletzt far #(nl, n~ & 1, a} erhaltene Oleichung wie folgt schreiben:

i~(n~, n._, + 1, a ) = 7 (nl, n~, n2, a);

ferner gelten nach den Rekursionsgleichungen der Funktionsfunktion C(~; n, a} die Gleichungen

7(n,, n,, O, a) = C(;+X[~(nl, //,, x)]; 0, a ) = 9(nl,//~, a) ) ' (a , n,, n++ I, a) = C(~x[~(n, , n+, x)]; n:++ 1, a) - -

tJ(n~, no-, C(2x[#(n~, n~, x)]; ha, a)) = #(n~, n~, ;~(n~, n~, n:~, a)).

4. Die hiermiI erhaltene simultane Definition cr ~ ( a + 1, a) = ~ ( n ~ , a , a), /~(n~, o, a) =- ~ (hi, a~'), ,~,(n~, n~ § t, a)--:~(n~, a , n=,, a), :,(n~, n~, o, a) = ~(n~, n~, a), ~'(a, n~,, n+ + 1, a) = / r n~, 7 ( a , a , n+, a))

der zahlentheoretischen Funktionen e, fi und 7 1NSt sich leicht zu einer 4-fachel~. Rekursion zusammenziehen: als vierte Rekursionsvariable wird der ,,Index '~ dieser Funktionen auftreten. Ein jeder Funktionswert ist bier n~imlich entweder mit Hilfe eines an frtiherer Stelle angenommenen Wertes, oder mit Hilfe einer ,,fr~iheren" Funktion definiert.

Sei also

o'(n~, n~, n:~, 0, a ) ~ ~(//,, a), ct(nl, //2, //,;, 1, a) = ~(nl , /12, a),

~(n~, n~,//+, i § 2, a ) = ~(n~, n~, n:+, a).

(Die ,,Indexvariable" i liege sich tibrigens auch in n3 einschmNzen: mar~ k6nnte 6 auch folgenderweise definieren:

d(nj, n~,, 3 n+, a) = e (n~, a),

d(n~, no., 3na-? 1, a )~ - C;(n~, no-, a),

d'(na, no_, 3n:~ + 2, a ) = 7(nl, n:~, n:~, a) ;

dann w~ire d 3-rekursiv.) So lautet die Definition von 0:

d(0, n~, n:+, 0, a) = a

d(n~ @ I, n2, n3, O, a) : 6(n~, n, , n.3, 1, a)

d(n~, O, n3, 1, a) ~ d(n,, O, n~, O, a )

d(n~, n,, + 1,//3, 1, a) : d(//1, n+, //3, 2, a) r n,,, O, i@2, a ) : d ( / / ~ , n2, O, 1, a) d(n~, n~, n ~ - 1, i@2, a) : d ( n ~ , n2, n,~, 1, d(n~, n=,, n3, i-~2, a))

Hi:iHERE STUFEN VON REKURS!VEN FUNETIONEN 259

und das ist tats~ichlich eine 4-fache Rekursion der I-ten Stufe. Dabei ist z. B.

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

So entsteht a(n, a) durch eine einfache Substitution aus d, demnach ist sie eine mehrfach-rekursive Funktion der l-ten Stufe.

5. An diesem Beispiel werde ich auch genau nachprtifen, dal~ die durch O(nl, n2, n~,0, a) definierte Funktion tats~chlich ftir beliebige n~,n3 mit der dutch die ursprtinglichen Rekursionen der II-ten Stufe definierten Funktion a(nl, a ) indent i sch ist. Die Behauptung lautet

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

Dies gilt ffir nl~---0, da in diesem Fall auf beiden Seiten a steht. Nehmen wir an, dal~ sie bereits ffir ein n~ gilt. Dann werde ich, urn ihre G~ltigkeit ffir n l + 1 zu zeigen, wegen

, (n~-k 1, a) = B(2x[e(nl , x)]; n~, a) und g(n~+ 1, n._,, n~, 0, a) = ~(n~, n~, n:, 1, a)

gleich allgemeiner

(2) B(;~x[~(n~, x)]; n.,, a ) = ~(nl, n~, n~, ~, a)

ffir jedes n~ beweisen. Dies gilt f~r n ~ - 0 , da nach den D.efinitionen und nach der Annahme

in diesem Fall auf der rechten Seite

d(n~, O, n3, 1, a) ~ d ( n l , O, n:~, O, a 2) =cc(n~, a~),

also auf beiden Seiten u(n~, a 2) steht. Nehmen wit an, dal~ f~r ein n2 bereits (2) gilt. Um auf m,+ 1 zu schliel~en, beweise ich wegen

B(;~x[a(n~, x)]; n~-k 1, a ) = C(,~x[B(,~ y[a(n~, y)]; n.2, x)]; n.,, a) und

ct(n~, n2+ 1, n~, 1, a) =g(n~ , n~, n=,, 2, a) gleich allgemeiner

(3) C(2x[B(2y[~(n~, y)]; n,, x)]; n:~, a) ~-d(n~i n.,, n~, 2, a).

Das gilt ffir n ~ O , da in diesem Fall nach den Definitionen und der letzten Annahme auf der rechten Seite

d(nz, n~, Oi 2, a ) = d ( n l , n:2, o, 1, a) = B(~x[a(n~, x)]; n.,., a)

steht, und auch die linke Seite damit identisch ist. Nehmen wir an, dag (3) bereits ffir ein n3 gilt.. So gilt es auch ffir na-k 1, denn nach den Definitionen und Annahmen ist

rJ(n~, n2, n:~+l, 2, a )=d(n~ , n~, ha, 1, d(n~, n~, n:~, 2, a))

= B(,~y[c~(n~, y)]; n2, C(.~x~[B(2y~[~(n~, y~)]; n.,, x~)]; na, a)) = = C(~x[B(2y[,~(n~, y)]; n2, X)]; n~+ 1, a).

Damit ist (3), dadurch (2) und dadurch (1) allgemein bewiesen.

260 R. PETER

6. Allgemein lautet die primitiv-einfach-rekursive Definition einer Funk- tionsfunktion :

A (991 , . . . , 99,.; O , a l , . . , a s , b j , . . . , b 0 ~ - B ( q ~ l , . . . , 99,.; a l , . . . , a~., b1 . . . . , b 0

A ( 9 9 ~ , . . . , 99r; n - b 1, a~ , . . . , a.~, b~, . . . , b~)

- ~ C ( 9 9 ~ , . . . , 99,, f i x 1 . . , x ~ [ A ( 9 ~ , . . . , 99,.; n, a~ , . . . , a~, x~ , . . . , x0];

; n , a l , . . . , a . , b l . . . . , b O.

Dabei sind

B(991,. . . , %. ;a~ , . . . , a~, b~, . . . , b 0 und C(99~,..., 99,, 99,+1; n, aj . . . . , a~ ,b~ , . . . , b 0

fr~her definierte Funktionsfunktionen (wobei %+a eine t-stellige Funktions- variable ist). Es komme diese Definition als ein Tell der Rekursion II-ter Stufe einer gewissen zahlentheoretischen Funktion ~7 vor. Dann soil die Funk- tionsfunktion A nach dem vorller verwendeten Gedanken durch Einsetzung gewisser speziellen, von ~7 abh~ingigen, Funktionen ~ , . . . , .~,. (n~imlich derje- nigen, f~r welche die Funktionsfunktion A zur Definition von ~ gebraucht wird) durch eine zahlentheoretische Funktion

e . ( c ~ , . . . , c,~, n , a ~ , . . . , a.~, b ~ , . . . , b 0 ~ A ( ~ . . . . , ~,.; n , a ~ , . . . , a~ , b~ . . . . . b 0

ersetzt werden, wobei C~ . . . . . c, die in ~ . . . . , ~. insgesamt vorkommenden Variablen sind (unter denen die Rekursionsvariable yon A gewifi nicht vor- kommt, da diese sonst yon der entsprechenden Variablen C unterschieden werden mug). Ffir diese Funktion ~ gewinnt man aus den Rekursions- gleichungen yon A die Definition

c~(c~, . . . , c , , O, aa . . . . , a.~, ba, . . . , b 0 - - B ( ~ , . . . , ~,.; a~ . . . . , a.~, b~ . . . . , b~)

c~(c~ . . . . . c , , n q - 1, a~ . . . . , a s , b l , . . . , b t ) ~ -

- C G , . . . , . . . x , [ a G , . , " x 0 ] '- . . ~ . , / / , a l , . . . , a . ~ , X 1 , . . . , ,

; n , a ~ , . . . , a.~, b~ . . . . , b 0

= C G , . . . , c,,, n, a , x , . . . , x 0 ] ;

; n , a ~ , . . . , r b~ . . . . , b 0.

Hier soil man analog f~r B G ~ , . . . , ~ , . ; a ~ , . . . , a~, b ~ , . . . , b O eine zahlentheore- tische Funktion ~(cl, . . . , c , , a ~ , . . . , a,~., b t , . . . , b 0 einftihren ; so lautet die erste Definitionsgleichung von c~

c~(c~ . . . . . c,, 0, a~ . . . . . a~, b~ . . . . , b~) ~ d(c~, . . . , c,,, a~ , . . . , a.~, bl, �9 b0.

Ffir

C ( ~ ] . . . . , ~F, ; ~ X l ~ X ' [ ~ ( C l , ' * ~ C,,, n , a l , , . . , a.q, X l , . . . , x~)]; ]~, a I . . . . . a.q, b l , . . . , b 0

kann man aber nicht unmittelbar eine zahlentheoretische Funktion ,/(c~ . . . . , c~,, n , a~, . . . , a~ , b~ . . . . , b t ) einftihrdn, sondern man hat zuerst, falls die Funktionsfunktion C ( q~ , . . . . . 99~,, 99~.+~ ; n~ a~ . . . . , as , b~ , . . . , b 0 durch Rekurs ion definiert wurde, die Bezeichnung der Rekursionsvariablen in C (nicht aber innerhalb 2 x~ . . . x t [c~(c~ , . . . , c , , n , a~, , , a~ , X l . . . . x0] ) in eine neue Variable m

H~HERE STUFEN VON REHURSIVEN FUNB;TIONEN 261

abzu~ndern, und far die so aus

C ( ~ 1 , . . . , ~ . , ,~ x 1 . . . x ~ [ ~ ( c ~ , . . . , ct~, 1l, a l , . . . , a s , x 1 , . . . , x,)] ; a l , . . . , a s , b l , . . . , b t )

entstehende Funktion eine Bezeichnung wie y ( C l , . . . , c,~, n , a l , . . . , a s , b t , . . . , b t ~ m )

einzuffihren. Um aber die Definition flieser Funkti0n wirklich aufzuschreiben, h~itte man jedesmal dasjenige von n , a l . . . . , a~ , b l . . . . . b~ durch eine Bezeichnung anzugeben, das als Rekursionsvariable der Funktionsfnnktion C dient; und dies far s~mtliche in der Definition yon r l vorkommende Funktionsfunktionen (da man s~mtliche Rekursionsgleichungen II-ter Stufe yon r/ braucht, um ihre mehrfach-rekursive Definition I-ter Stufe angeben zu k6nnen). Dazu kommt noch die Komplikation, dag die Funktionsfunktion C zuweilen dutch Substitu- tion entstehen kann. Um also die Zurfickftihrungsmethode der vorigen Nummer allgemein aufschreiben zu kOnnen, mOgte man eine variable Anzahl yon voneinander abh~ingigen Fal!unterscheidungen in einer Formelfolge aufschreiben kOnnen, das geht aber ohne irgendeinen neuen bezeichnungstechnischen Oedanken nicht. (Es handelt sich um eine technische Schwierigkeit yon der Art, vielleicht um eine noch grOl~ere, als jene, die man fiberwinden maf~te, falls man etwa den Multiplikationssatz der Determinanten ohne die Determinanten- bezeichnung aufschreiben wollte.)

Indessen scheint es mir ohne eine allgemeine Angabe der Reduktions- methode plausibel zu sein, daft dieselbe Methode, die in der vorigen Nummer :far einen Spezialfall durchgeftihrt wurde, ff3r jede primitiv-einfach-rekursive Definition II-ter Stufe anwendbar ist.

Es k0nnen also s~imtliche primitiv-einfach-rekursiven Funktionen der II-ten $tufe auch als mehrfach-rekursive Funktionen tier 1-ten Stufe definiert werden.

Der Gedankengang lNSt sich ohne weiteres auch auf h0here Stufen fiber- ~ragen; so lassen sich z. B. die primitiv-einfach-rekursiven Funktionsfunktionen der IlI-ten Stufe auch als mehrfach-rekursive Funktionsfunktionen der II-ten :Stufe definieren.

w 3. Anwendung der Methode auf eingeschachtelte (sogar mehrfache) Rekursionen, wobei sich nur Zahlenparameter ver~indern

1. Zur Analogie der eingeschachtelten Rekursion der I-ten Stufe k~nnen auf tier II-ten Stufe z.B. solche Definitionen gebildet werden:

,~ (0, a) = a

~(n + 1, a ) = B ( ~ x [ ~ ( , , x)] ; n, a), wobei

wo J und C bereits definierte Funktionen sind; oder um gleich

B (~; o, a) = ~ (a)

B(~o; n + 1, a)=J(;~x[B(~; n, C(~; n, a, B(~ ; n, x ) ) ) ] ; n, a),

eine mehr-

262 R. P ~TEI~

fache eingeschachtelte Rekursion der II-ten Stufe zu betrachten:

- (0 , a) = a ~(n+ 1, a ) = B(~x[-(n, x)]; n; a, a),

wobei B(cp; m, n, a ) = ~(a~), falls m.n = 0

Bqt; m + 1, n + 1, a) =J(,~x[B(~; m, B(r m § 1, n, x), a)]; m, n) und

J(~; O, a) ~ (a) j (~ ; n + 1, a ) = ~(J(~; n, a)).

Verwenden wir unsere Methode auf die letztere Definition. Sei

B()~X["(nl, X)]; n2, ha, a ) = fiQll, n.~,//3, a)

(man mug die erste und zweite Zahlenvariable yon B(Lx[cc(n ,x)];n ,a ,a) , die zufftllig mit der ersten Variablen yon a in.2x[c~(n, x)] bzw. mit der dritter~ Zahlenvariablen yon B(,~x[~(n, x)]; n, a, a) iibereinstimmen, yon jenen Variabler~ unterscheiden, da sie beide Rekursionsvariablen von B sind; dann ist

~(n + 1, a) ~(n, n, a, a), und

/~(nj, n.~_, n3, a) =B(22[a(n~ , x] ; n.,, n3, a) = a(n~, a~'), falls n~.nz=O,

#(n~, n~-t- 1, n3§ 1, a ) : B ( 2 x [ e ( n ~ , x)]; n.,§ 1, n~§ 1, a)

J(2x[B(Zy[a(n~, y)]; n,j, B(2y[a(n~, y)]; n.2§ 1, n:~, x), a)]; !12, n~)

- -J( ; ,x[Z(n , , n~, g(n~, n._,§ 1, n3, x), a)]; n~, n3 )=

= t(nl, nz § 1, na, n~, a), wobei L(n~, O, n3, n~, a) beliebig, z.B. als 0 definiert werden kann, ferner

,(nl, n~4- 1, n3, n~, a)=J(;~x[g(n~, n._,, #(ha, n.,.§ 1, n~, x), a)]; n.~, hi)

ist, also /~(nl, n,2~-- 1, n3, O, a) - -J(2x[ f i (n l , n.,_, ,?,(n~, n.,.@ 1, n3, x), a)l; 0, n3) =

= #(n~, n~, ~(n,, n~ + 1, n~, n3), a), t(n~, n~§ 1, n~ n , § 1, a ) = J ( 2 x [ f ( n ~ , n.2, fi(nx, n~@ 1,ha, X), a)]; n4@ 1, n~)=

= ;~(n~, n~,/~(n~, n~4- 1, na,J(,~x[f(n,n2,#(n, n , § 1, n~, X), a)]; n~, n3)), a ) =

fl(nx, n~, fi(nl, n.2 @ 1, n3, t(nl, n2, n3, n4, a) ), a). Somit erh/~lt man die folgende simultane Definition far die zahlentheoretische~ Funktionen e, fl und t :

o,(0, a) = a, .(n~ + 1 , -a )= ~(n~, n~, a, a), fi(n~, n~, n3, a ) = i~(n~, a~), falls n~.n3=O, #(n~, n., 4- 1, n3 § 1, a) ~ ~ (n~, n., 4- 1, n3, n.,, a), ,(n~, n ~ § ~, n~, o, a) = ~(n~, n~, ~(n~, n~,- ~, n~, n~), a), t(n~, n_,§ 1, n~, n~§ 1, a)=,3(n~, n~, ,6~(n~, n~§ 1, n3, ,(n,, n.,, n3, n4, a)), a).

H(3HERE STUFEN VON REI~URSIVEN FUNKTIONEN 263

Wird ~(nl, n~, n~, < , o, a) = c~(n,, a),

(n~, n,, n3, < , 1, a) = 9 ( < , n,, n~, a),

d(nl, &, ha, &, i + 2 , a ) : t(nl, n~, ha, &, a) gesetzt, so l~l~t sich d genau so, wie in Nr. 4 des w 2 dutch eine mehrfache (bier 5-fache) Rekursion der I-ten Stufe definieren; und aus d ergibt sich t~ zum Beispiel durch die Substitution:

r a) = d(nl , 0, O, O, O, a),

2. Die einfachen eingeschachtelten Rekursionen der betrachteten Art tassen sich auf der IMen Stufe auch leicht auf uneingeschachtelte Rekursionen und Substitutionen aufl0sen.

Betrachten wir zl B. das erste Beispiet tier vorigen Nummer, worin die eingeschachtelte Rekursion

B(~p; o, a) = ~(a) B(q~; n @ 1, a)=J(Z)c[B(qv; n, C(~; n, a, B(cf; n, x)))]; n,a)

teilgenommen hat. Wird eine Funkfionsfunktion C~ durch Substitution aus C und aus d e r Grundfunktionsfunktion V(~; b) : ~0(b) wie folgt definiert :

G(,p, ~v; n, a, 0 ) = ~'(C(~; n, a, W(O))), so lautet die zweite Definitionsgleichung von B:

B(tp;n -k 1, a) =J(2x[G(r 2y[B(~; n, y)]; n, a, x)]; n, a),

Bildet man also durch Substitution aus J und G die Funktionsfunktion

A(~, ~; n, a) =j(~.x[G (~, "~; n, a, x)]; n, a), so kann B durch die primitive Rekursion

B(~e; o, a) = ~(a) B(~o; n+ 1, a)=J, (9 ,2x[B(9; n, x)]; n, a)

definiert werden. Jedoch gibt es auf der Il-ten Stufe eine neue Art yon Einschachtelun-

gen ; und yon diesen ist es zu erwarten, daft sie von der Klasse der rekursiven Funktionen der Men Stufe hinausffihren.

w 4. Einschachtelungen an den Stellen der Funktionsvariablen

1. Das Charakterisfische der II-ten Stufe ist, daft hier auch Funkfions- variablen als Parameter auftreten; etwas Neues ist davon zu erwarten, wenn diese neuarfigen Parameter sich bei einer Rekursion ver~indern.

Handelt es sich urn eine einfache Rekursion, so kann eventuell auch dieser Fall auf primitive Rekursion und Substitutionen aufgel0st werden; mit der selben Methode, wie das auf der I-ten Stufe geschehen ist. 1~

~o Siehe Ful3note 4.

264 a. P~TER

Wenden wir diese Methode z. B, auf die folgende Definition an: a) B(r

A(q~; n 4- 1, a) ~-- C Q~x[A (2 y[A (q~ ; n, y)]; n, x)]; n, a),

wobei B und C fraher eingef~ihrte Funktionsfunktionen sind. Hier ist

A(q~; 0, a ) = B(q~; a),

A(q:; 1, a) = C(2x[A(2y[A(c~; O, y)]; 0, x)]; 0, a) =

-~ C(2x[B(2y[B(q); y)]; x)]; 0, a),

Man sieht, daft sich die Werte von A(~o; n, a) durch Ineinanderschachtelungen yon B(q:; a) und C(q~; n, a) aufbauen, wobei far n in C(q~; n, a)verschiedene Zahlen eingesetzt werden. Wird also eine Funktionsfunkfion D(~; 0, a) dutch

D (q~; 0, a) : q~ (a) und far n =~: 0

i B (2x[D(~; expl(n) ,x)];a), falls e x p 0 ( n ) : 0 , D(q:; n, a)

C()~x[D(q~; exp,(n), x)]; expt(n), a) sonst

definiert, So kommen unter den Werten von D(q~; n, a) auch die Werte von A(q~; n, a) vor: man beweist genau so, wie auf der l-ten Stufe, dal~ es eine 1-rekursive Funktion z(n) der I-ten Stufe gibt, far welche

A(q:, n, a ) = D ( ~ ; z(n), a)

gilt. (Die Definition von D ist noch keine primitive Rekursion, l~il~t sich abet - - genau so, wie die ~ihnlichen ,,Wertverlaufsrekursionen" der I-ten S t u f e - auf primitive Rekursion und Substitution aufl0sen.)

2. Aber z. B. bei der Rekursion

A (q:; 0, al, a2) : B (q:; al, a~)

A(ff; n 4- 1, a~, a~) - - C(2xy[A(2z[A(~; n, x, z)]; n, a~, y)]; n, a~, a~)

versagt unsere Methode. Betrachtet man bier den Aufbau von

a (r O, a~, a2), A (q); 1, a~, a.~), A (q~; 2, az, a t ) , . . . ,

so sieht man, dag darin zwar ebenfalls Ineinanderschachtelungen von B und C auftreten, aber um diese sukzessiv bilden zu k(Snnen, haben wir immer mehr Variablen einzuffihren. Z.B. ist

A(q~; 1, a~, a~ )= C(~xy[A(,~z[A(q~; O, x, z)]; 0, al, y)]; 0, a~, at)

: CQ~xy[B(Zz[B(~; x, z)]; ax, y)]; 0, a~, a,,).

Hier hfingt das innerste B(q~;x, z) von 2 freien Variablen (x und z) ab, aber

B(~Z[/~(q~; X, Z)]; al, y)

bereits von 3 freien Variablen: x, a~ und y. Im Aufbau von A(q~; 2, aa, at) wird auch eine 4-stellige Funktionsfunktion angewandt, usw. Daher kann man hier mit endlicher Variablenanzahl keine Funktionsfunktion D angeben, welche s~imtliche Bausteine im Aufbau der Werte yon A annehmen warde.

HOHERE STUFEN VON REI{URSIYEN FUNtiTIONEN 265

Wenn man die betrachtete Methode zur AuflOsung der Einschaehtelungen einer mehrfachen Rekursion anwenden will, so versagt sie bereits auf der I-ten Stufe.

3. Wurde aber die Funktionsfunktion B(r m, n, a) (oder A(~; n, a) in Nr. 1 dieses Kapitels)zur Definition einer zahlentheoretischen Funktion e ver- wendet, so kOnnte man doch glauben, dal3 sich die Definition yon ~ durck die in Nr. 3 vom w 2 eingeffihrte Methode auf eine mehrfache Rekursion der I-ten Stufe zurtickffihren l~tBt.

Sei z.B. (urn gleich eine mehrfache Rekursion zu untersuchen) die vollst~indige Definition von r

a ) : a

r -q- 1, a) ~ B(,~x[~(m, x)]; m, a, a), mit

und

B(q~; m, n, a)~q?(a), falls m.n ---0

B(~; m 4- 1, n § 1, a) ~ J(2.x[B(2.y[B(9~; m, y, a)]; m q- 1, n, x)]; n, a)

o, o ) - -

n + 1, a) = n, o)).

Nach tier genannten Methode h~itte man hier

~(mo-ff 1, ao) = B(2x[e(mo, x)]; ml, ao, ao) = ~(mo, m~, ao, ao)

zu setzen, wobei

t~(mo, ml, n, ao) ~ B(2x[cr x)]; ml, n, ao) ist, also

~(mo, ml, n, ao) ~ e(mo, ao), falls ml.n = 0

~(mo, ml-F 1, n q- 1, ao) ~- B(2x[e(mo, x)]; ml q- 1, n q- 1, ao) =

=JO~x[B(2y[B(2z[~(mo, z)]; m~, y, ao)]; m~ q- 1, n, X)]; n, ao)

~J( , t x[BO:y[#(mo, m~, y, ao)]; m~+ 1, n, x)]; n, ao).

Hier wird f~ir 9~ in B(9:; m, n, a) nicht 2x[a(mo, x)], sondern ;~oy[~(mo, m;, y, ao)J gesetzt, so hat man auBer / /auch

~'(mo, m~, m~., n, ao, a~) - - B ( 2 y [ ~ ( m o , m~, y, ao)]; m~, n, a])

einzuff]hren; damit ergibt sich

d(mo, m]-1- 1, nq- 1, ao)=J( ,~x[y(mo, m~, m~ + I, n, ao, x)]; n, ao)

' (mo, ml, m~ q- 1, n, n, ao), falls

J(,t x[#' (mo, m~, m2, n, ao, x)]; r, ao) ~ ,(too, ml, m~, n, r, ao)

gesetzt wird. (Dabei hat sich clas zweite Argument vermindert.)So lal~t sich ,: mit Hilfe von d durch folgende Rekur, sion nach r definieren:

266 P~ P t~TEI~

t(mo, m,, m._,, n, O, ao) ~J (2x[ f l ' (mo , ml, m.,, n, a, x)]; O , a o ) =

- - fl' (mo, ml, m2, n, ao, ao)

t(mo, ml, m2, n , r + l, ao) J(2x[fl'(mo, m ~ , m , , n , a , x ) ] ; r + l, a o ) ~

o' _ .... o, x ) ] ; r, ao)) = , (mo, ml, m. , ,n,a, , ,J( x[t~(mo, m~,m~,n, ~-

=f l ' (mo, m,, m.,_, n, ao, ,(mo, ml, m2, n, r, ao)).

Aber in der rekursiven Definition yon fl' muB ftir ~ in B ( ~ ; m , n, a) wieder eine andere Funktion eingesetzt werden als bisher; d ies erfordert die Ein- f0hrung neuer Funktionen /~" und t':

fl'(mo, ml, m.2, n, ao, a~) ~ B (2 y[fl,(mo, 1771, y, ao)]; m.2, n, aj) =

fl(mo, m~, a~, ao), falls m.~_.n ~ o ,

fl' (too, m~, m._, ~ 1, n + 1, ao, a 0 ~ - B ( 2 y [fl(mo, m~, y, ao)]; m2-- 1, n + 1, a 0

~J(2x[BO~Y[B(;~z [#(mo, m~, z, ao)]; m~, y, aO]; m.~+ 1, n, x)]; n, a~)

~ J ( , ~ x [ B ( ~y[# (too, m~ m,_,, y, ao, aO]; m,,+ 1, n, x)]; n, a~)

=J( ;~x[y ' (mo, m~, m.,, m., + 1, n, ao, a,, x)]; n, aO ~-

- - t'(mo, m~, m.,, m,, + 1, n, n, a,,, aO.,

(dabei hat sich das dritte Argument vermindert); wo

;R" (m0, _ , m~, m,~, m~, n, ao a~, a,,) ~ B (2 y[fl'(mo, m,, m2, y, ao, a0]; m~, n, a~)

und

t (too, ml, m.) m~, n, r, ao, a 0 = J ( 2 x [ , (mo, ml, m~, re.j, n, ao, a~, x)], r, a 0

ist. Hier kann t' wieder mit Hilfe von fl" durch eine Rekursion nach r d e f t

niert werden; die rekursive Definition von fl" erfordert aber die Einftihrung neuer Funktionen fl'" und t",: und so fort. So mtissen unendlich viele, immer mehr-stellige Funktionen eingeffihrt werclen, wobei immer neue Argumente als Rekursionsvariablen auftreten. Man gelangt zu einer eleganteren Bezeichnung, falls man fl~ statt fl, fl., statt ~' fl" ~,, fl~ start usw. schreibt, und die Funktion c~ selbst auch dutch fit, bezeichnet; so ist fl.~ eine Funktion yon 2 s + 2 Argu- menten, yon denen die ersten s + l durch mo , . . . ,m~ , die s + 2 - t e durch n, die letzten s (ffir s ~ 1) durch a o , . . . , a~-i bezeichnet w e r d e n . Aus dem gleichen Orunde soll

,,~(m0,..., m.~+9_:, n, r, a , , , . . . , a.~.) ~J(2x[f l~+2(mo, . . . , m.~+.,_, n, a , , , . . . , a~., x)]; r, a.~)

gesetzt werden, so dab to die bisher dutch t, t~ die bisher durch t' bezeich- nete Funktion bedeutet, usw. Wird also auch der ,,Index" s als eine Variable betrachtet, so gelangt man zu einer Art Funktion, bei welcher es von einem Argument abh~ingt, wievielstel!ig die Funktion ist.

Die Definition yon ~.~. lautet als0:

~o(mo, n ) ~ c~(mo, n)

. . . . .., ~ .. . , a.~_l)]; m~.~, n, a0; .~.~+l(m~, m.,+l, n, ao, . a.~) = B(2y[,~,.~(m,,..., m , y, a,,

HOHERE STUFEN VON REIffURSIVEN FUNET'IONEN 267

d a h e r ist

,z(mo ~- t , ao) = B ( 2 y [ e ( m o , y)] ; mo, ao, ao) = B(2y[#o (mo , y)] ; mo, ao, ao) --~

= #, (mo, too, ao, ao).

Aus den rekurs iven Defini t ionen der Funkt ionsfunkt ionen B und J gewinnt man e ine Art rekursive Defini t ion ftir die Funkt ionen ~.~ und ~8 wie folgt :

A(m,, , n ) - - , ~ ( m o , n)

~,~+1 '~ (rno, �9 �9 �9 m8+1 , n, ao . . . . , a~) ~ B (2y [Re (mo, . . . , m~, y, ao, . . . , a.~51 ) ]; m.~+l, n, a~) ~ -

= ~.~(m 0 . . . . , m~, a.~, ao . . . . , a8_i), falls m.~+j �9 n 0

o'38+~(m0, . . . , m~, m8+[+ 1, n + 1, ao . . . . , a s ) =

=B(~ . y [ ,~8 (mo , . . . , ms, y, ao, . . . , m,~+l @ 1, tz-} - 1, a8) =

~ J ( , ~ x [ F~ff~y[B(,~z[~4m,, . . . . , m~, z, ao, . . . , a~ ~)1; ms+~, y, as)];

; ms+~ + 1, n, x) ]; n, as) ~ -

:- . J ( 2 x [ B O ~ y [ , Z + ~ ( m o , . . . , m.~+l, y, ao, . . . , a J ] ; m8+a -I- 1, n, x) ] ; n, as) =-

-~J(Xx[#8+2(mo, . . . , m~+~, m~+~ + 1, n, a o , . . . , as, x)] ; n, as) =

I .~(mo,. . . , m8+1, ms+l @ 1, n, n, a o , . . . , a8),

~und

~(m,, , . . . , m.,~+2, n, O, ao, . . . , a . ~ ) = J (2x[#.,.+,,(mo, :. . , m~+2, n, a,,, . . . , a. , x)] ; O, a.~) =

= ~+2 (too, . . . , m~+,,, n, ao . . . . . a.~., a.~)

,~(m,, . . . . , m.~+2, n, r § 1, ao . . . . , as) = J (,~x[#~+2(mo, . . . , ms+,,, n, ao . . . . . a.~, x)] ;

; r + 1, a.~) ~ -

" ~ 1 7 6 "~ ~ " ~ = g§ (too, m8+a, n, ao, . . . , a ~ , J ( ~x[r m~.§ n, ao, . . . , a~; x)]; r, a 8 ) ) =

= g+o ( m o , . . . , m.~+~, n, a o , . . . , a~., , ~ (mo , . . . , m~+z, n, r, a o , . . . , as)).

S o m i t erh~ilt man die fo lgende s imultane Defini t ion for die Funkt ionen c~,~'~ ~ n d t,s :

a (0, ao) ~ ao,

(z (m,, -[- 1, ao) = ~1 (mo, mo, ao, ao),

flo(mo, n) - - - ~ ( m o , n),

#8+l(mi,, . . . , m8+~, n, ao, . . . , a s ) = #8(too, . . . , m~, as, ao, . . . , a8-1), falls m . , ~ . n = O,

~8+1 ( too , . . . , m.;i ms+~ + 1, n + 1, a o , . . . , a8) = t~ (mo . . . . , m.~+l, m,.+l + 1, n, n, a o , . . . , as),

"8 (m,,, . . . , ms+.,, n, O, ao, . . . , as) #.~+.~ (mo, . . . , m.,.+~, n, ao, . . . , a~, a,.),

~.~(mo,. . . , m.~+2, n, r + 1, ao . . . . , a.~) =

= #8+'~ ( t o o , . . . , m8+.2, n, a o , . . . , as, ,8 ( t oo , . . . , m~+~, n, 1; ao . . . . , as)).

4. Fassen wir nun diese Defini t ionen zusammen. Sei

6(mo, . . . , m.~.+2, r, O, s, n, ao . . . . , a, 0 -= a(mo, ao),

d ( m o , . . . , m.,.+,2, r, 1, s, n, ao . . . . , a.~) ~ - ~,(mo, . . . , m8, n, ao, . . . , a8-1),

a(mo, . . ., m.~+2, r, i + 2 , s, n, ao . . . . , a.~) = l~(mo, . . . , m~+., , n, r, ao, . . . , a8).

268 R. PNTER

So lautet die Definition von d (ftir Argumente, von welchen 6 an der betrach- teten Stelle nicht tats~ichlich abh/ingt, kann freilich beliebiges gesetzt werden) :

~r(O, ml, . . . , m~2, r, O, s, n, a, , . . . , a,) = a~,

6(mo q- 1, nh . . . . , m,~+2 , r, O, s, n, ao, . . . , a,) ---- d(mo, mo, m.2, m:~, r, 1, 1, ao, am, ao)

d(mo, ml , m_,, 1, 1, O, n, ao) = d(mo, ml, m~, r, O, O, n, n)

d(mo, . . . , m~+a, r, 1, s 4- 1, n, ao, . . . , a.~+l) = 6(m,,, . . . , m~+o , r, t, s, a~., ao, . . . , a s - l ) ,

falls m~+l. n = 0

d(mo, . . . . m, , m.~+l + 1, m.~+2, m.~+3, I", 1, s ~- 1, n + 1, ao, . . . , a~+l) =-

= d(mo, . . . , m~+l, m~+t ~- 1, n, 2, s, n, am, . . . , a )

6(m,~ . . . . . m , ~ , O, i + 2, s, n, a,, . . . , a 0

d(m,~ . . . . , ms+~, O, O, O, 1, s q- 2, n, am . . . . , a,., a.~, a.~),

a(m,,, . . . , m~+2, r + 1, i + 2, s, n, am, . . . , aO =

-~- cr(mo, . . . , m~+2, 0, O, r @ l, 1, s + 2, n, ao, . . . , a~;

; d(mo, . . . , m,+2, r, i + 2, s, n, am, . . . , a,), a.,);

und daraus ergibt sich ,z dutch die Substi tut ion"

c~(mo, ao) = d(m~, . . . , m,~+e, r, O, s, n, ao, . . . , a~)

far beliebige m:, . . . , m.~+2, r, s, n, a~, . . . , a,, etwa als

(mo, = (mo, o, o, o, o, o, o,

Die Funktion d ist eigentlich unendlich-vielsteilig" genauer, es hangt vor~ ihrem Argument s ab, wievielstellig sie bei gegebenem s ist. Ihre Definition ist eine unendlich-vielfache Rekursion: die Rekursion verl~iuft zwar b e i jedem s nach den 5 Variablen too, m~, r,i , s (too vertritt dabei die Rekursionsvariable yon ~, ebenso m~ eine Rekursionsvariable yon B, und r die Rekursionsvariable yon J) , dabei bedeutet aber m~ ffir jedes s eine andere Variable.

5. Die Definition yon d kann auch als eine transfinite Rekursion vom

Typus co ~~ formuliert werden. Das kann z .B. so geschehen, dab

),(m) = d(expo(m), e x p , ( m ) , . . . , exp,_~+7(m))

gesetzt wird, so dal3

H ,'It d(mo, . . . , m,~+2, r, i, s, n, a0 . . . . . a,~) " " ': . . . . . . . \.~ 3"=0 "~ r , j : s+7 ] )

gilt. So ergibt sich speziell

o~(m, a) = d(m, O, O, O, O, O, O, a) ~ - 7(2 ~"- 19").

Aus der Definition von d erh~ilt man ffir 7 eine solche Rekursion, wobei eine Stelte m dann als VorgSnger einer Stelle n betrachtet wird, wenn die erste unter den Primzahlen

Po, P~, P~, . . . .

H~HERE STUFEN VON REKURSI~/EN FUNKTIONEN 269

welche in den Primfaktorenzerlegungen yon m und n mit verschiedenem Expo- nenten teilnimmt, in de r Zerlegung yon m einen kleineren Exponenten besitzt, als in der Zerlegung yon n. Eine solche Anordnung der Zahlen ist aber vom Typus ~o ~.

w Offene Probleme

1. Nach Nr. 5 yore{} 4 scheint die II-te Stufe geeignet zu sein, zahlen- theoretische Funktionen, die durch Substitution aus solchen Funktionen entste- hen, welche durch transfinite Rekursionen vom Typus ~ angegeben wurden, ohne transfinite Rekursionen zu definieren.

Die ,,Diagonalfunktion" der mehrfach-rekursiven Funktionen der I-ten Stufe (welche yon s~imtlichen mehrfach:rekursiven Funktionen der I-ten Stufe verschieden ist ), ist aber auch eine Funktion dieser Art. ~ K0nnte man die Diagonalfunktion auf der II-ten Stufe definieren, so h~itte man einen Beweis daftir, dal3 die lI-te Stufe eine weitere Funktionenklasse liefert, als die I-re.

Betrachtet man aber die Definition der Diagonalfunktion n~iher, so sieht man, dal~ diese unendlich-vielfache Rekursion ,,vollz~ihlig-mehrfach" ist, in dem Sinne, da l die Rekursion an jeder Stelle, wo keine der Rekursions- variablen 0 ist, nach s~imtlichen auftretenden Rekursionsvariablen verl~iuft. Die Definitfon yon unserem 8 kann dafter ,,zerstreut-mehrfach" genannt werden, da diese Rekursion bet jedem s blol nach 5 der s + 6 Rekursionsvariablen ver- l~iuft (aber bet verschiedenen s nach anderen). Die Definition anderer Funk- tionen der II-ten Stufe kann auch immer auf eine solche Rekursion ohne Funktionsvariable zurackgefahrt werden, welche an jeder Stelle nach Variablen einer ganz bestimmten Anzahl verl~iuft: diese Anzahl h~ingt yon der Struktur der urspranglichen Definition (der II-ten Stufe) ab.

Wenn es gelingen wfirde, die Diagonalfunktion der I-ten Stufe auf tier II-ten Stufe zu definieren, so h~itte man ein Beispiel for eine vollz~ihlig- mehrfache Rekursion, welche sich auf zerstreut-mehrfache Rekursion und Substitution zurackfahren lifit. Es ist sehr fraglich, ob dies bet einer so wesentlich vollzihlig-mehrfachen Rekursion m6glich ist, wie die Definition jener Diagonalfunktion.

Es w~ire freilich auch m6glich, dat~ unser 8 und ebenso beliebige Funk- tionen der II-ten Stufe - - wenn die bisherigen Methoden auch versagen - - auf irgendeine Art doch dutch mehrfache Rekursionen der I-ten Stufe (oder, was auf dasselbe lierauskommt, dutch transfinite Rekursionen yore Typus oJ ~, wobei k endlich ist) und Substitutionen definiert werden kOnnten; dal sich also die zerstreut-vielfachen Rekursionen noch auf endlich-vielfache Rekursionen aufl6sen lielen. Dann wfirde die II-te Stufe nichts Neues gegenfiber der I-ten Stufe liefern. Dies scheint abet auch nicht wahrscheinlich zu seth.

n Siebe F:Jl3note~.

18 Acta Mathematica

270 R. P~TER

Auch an sich ist das Problem interessant: gibt es gewisse Zwischendinge zwischen den transfiniten Rekursionen vom Typus m ~ mit endlichem k und der vollz~thligen transfiniten Rekursion yore Typus co ~ - - n~mlich die zer- streute (d. h. auf zerstreut-mehrfache, an jeder Stelle nach 1, oder nach 2, oder nach 3 , . . . Variablen verlaufende Rekursionen tlbersetzbare) transfinite Rekursionen yore Typus ~.~o; oder lassen sich die zerstreut-transfiniten Rekur- sionen vom Typus o90' auf jene vom Typus ~o ~ aufl/3sen; oder l~.13t sich etwa die vollz~thlig-transfinite Rekursion vom Typus o) ~~ auf zerstreute aufl0sen ?

Dieses Problem lautet gewissermal~en fthnlich, als jenes : ob es Zwischen- M~ichtigkeiten zwischen dem Abz~ihlbaren und clem Kontinuum gibt; aber im Gegensatz zur Kontinuumhypothese scheint es wahrscheinlich, daf5 es hier tats~chlich uneinschmelzbare Zwischendinge gibt.

2. Dieselbe Methode, wodurch aus einer Definition der II-ten Stufe die Funktionsvariablen ausgeschaltet wurden (und welche bei gewissen Einschach- telungen zu zerstreut-transfiniten Rekursionen geffihrt hat), kann auch auf die Definitionen zahlentheoretischer Funktionen der III-ten Stufe, zur Ausschaltung der Funktionsfunktionsvariablen angewandt werden, SO erh~ilt man bei gewissen Einschachtelungen zerstreut-transfinite Rekursionen der II-ten Stufe. Wird auf eine solche Rekursion dieselbe Methode, nun zur Ausschaltung der Funktions- variablen, noch einmal angewandt, so ftihrt sie zu einer zerstreut-transfiniten Rekursion yon hSherem Typus. Vollz~ihlig-transfinite Rekursionen sind auch yon h0heren (endlichen) Stufen nicht zu erwarten. Es ist sehr fraglich, ob sich die Diagonalfunktion der I-ten Stufe auf irgendeiner Stufe yon endlicher H~3he definieren l~tl3t.

Jedenfalls erhebt sich die Frage, ob sich eine vollz~ihlig-transfinite Rekur- sion auf zerstreut-transfinite Rekursion yon hOherem Typus und Substitution zurtickfahren l~gt ?

Es w~ire auch interessant zu untersuchen, welche Typen der transfiniten Rekursionen (oder eventuell andere Arten der allgemeinen Rekursion) far die verschiedenen Stufen charakteristisch sind.

3. Gelingt es auch nicht, die Diagonalfunktion der I-ten Stufe auf der II-ten Stufe zu definieren, so bietet sich noch ein Weg zu zeigen, dab die II-te Stufe mehr zahlentheoretische Funktionen umfagt als die I-re: die Acker- mannsche Majorisierungsmethode. 12

Der Orundgedanke dieser Methode ist, dab AC~ERMANN die ,,Bausteine" einer zweistelligen eingeschachtelten einfachen Rekursion der I-ten Stufe durch monoton nicht-abnehmende Majoranten ersetzt; diese nehmen nicht ab, wenn ein jedes ihrer Argumente durch das grOgte ersetzt wird, und so kommt er zu einer Majoranten der dutch die betrachtete Rekursion definierten Funktion, welche (start der verschiedenen neuen Bausteine die grN~te yon ihnen genom-

12 Siehe Ful3note2.

HC~HEHE STUFEN VON RENURSIVEN FUNI4.TIONEN 271

men) etwa so definiert werden k6nnte:

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

Wird bier die Rekursion aufgel0st, so sieht man, dai3

(o, a) = ~(a), ~(1, a) = ,8(#(... ) '(~'(a))...)),

ist; hier handelt es sich also einfach urn Iterationen von fl(a), wobei es yon n abh~ingt, wievielmalige Iteration den Wert von c~(n, a)ergibt . Daraus folgt leicht, dab wenn man, aus einer Majoranten der im Aufbau der einfach-rekur- siven Funktionen zu Grunde genommenen Funktionen ausgehend, durch Iterationen immer neue Funktionen 9o~, c?2 . . . . bildet, dadurch eine solche Funktion 90.,, erh~ilt, welche ftir ein geeignet gew~ihltes n eine beliebige einfach- rekursive Funktion tier I-ten Stufe majorisiert.

Den Gedankengang auf eine k-fache Rekursion (yon ,Normalform") angewandt, wtirde man als Majorante der dadurch definierten k-stelligen Funktion zun~ichst eine Funktion erhalten, welche dutch eine Rekursion etwa folgender Form definiert wird:

e(nl . . . . , m) = max (n~ . . . . , n,..), falls n l . . . nz; ~ 0

~Z(n 1 - ~ - I . . . . , n k @ - l ) - - : # ( - o ( n l , i ~ ( ~ 1 ( / . ~ ( ~ z 2 ( . . . / ~ ( c z k : , ) . . . ) ) ) ) , . . .

�9 ..', #(-1(9(-~(. . . :~(-,, ~)-. .)))))) , wobei Rir i ~ 1, 2 , . . . , k - - 1

~(a) = ~(n~+ 1 , . . . , n~+ 1, n~+~, a , . . .~a) , und so speziell ffir i = k - - 1

,~k-i = ~.,(n~ § 1, . . . , n~_~ § 1, n~)

ist. Ganz innen kommt hier tiberall eben czk_~=a(nl+ 1, . . . . nk-~4- 1, nk) vor; und ist n~ :t: 0, so kann das durch einen genau so aufgebauten Aus- druck als die rech te Seite der zweiten Definifionsgleichung ersetzt wet- den, mit dem einzigen Unterschied, dab statt - ( n l + l , . . . , n ~ ~4-1, n~;) darin a ( n x + l , . . . , n ~ _ ~ 4 - 1 , m~-- l ) steht. Ist bier n k - - l @ 0 , so kann c~(n~+ 1, ..., n~_~ + 1, n~.--1) wieder dutch einen ~thnlichen Ausdruck ersetzt werden, usw., bis man nach n~: + 1 Schritten zu einem Ausdruck kommt, wo innen

c~(n~ 4- 1 , . . . , m-1 + 1, 0) = max (n~+ 1, . . . , n~_l 4- 1)

steht. So entsteht ~(n~4- I , . . . , n~.§ 1) dutch n~4- 1-malige Iteration an der Stelle max(n~+ I , . .... n~._~4- 1) aus

~(~o(n~, ~ ( ,1 . . , ~ ( -~-2(~00)) . . . ) , . . . , ,~(~. . . , ~(~._2(9(x)))...))), and daher kann a auf der lI-ten Stufe mit Hilfe der durch

I@, 0, a) - a

I(~; n + 1, a ) : ~0(I(~; n, a))

272 R,P~TER

definierten Iterations-Funktionsfunktion durch die k - - l - f a c h e Rekursion

a(nl, . . . , n~,) ~ max (nl . . . . . nl,:), falls /h.lz.~.., nl~ ~ 0

~ ( n l + t . . . . , n,~+ 1) = =

;nk@I, max (nl@ 1, .~., nk_1-[- I))

definiert werden, wobei far i ~ 1, 2 . . . . , k - - 2

ai(a) =- a (n l@ 1 , . . . , hi@ 1, n,:+l, a, . . . , a)

ist (n~ ist bier keine Rekursionsvariable mehr; NoB ein Parameter). Wtirde nun zuerst eine Majorante s 0 ( a ) d e r Grundfunktionen far #(a)

gesetzt, dann mit der dadurch definierten IZ'unktion u(na . . . . ,nk) die ein- stellige Funktion d~(a) - -cq(a , I . . . . a), usw., so k6nnte man Funktionen co(a), e,'~(a),~;(a) . . . . erhalten, unter welchen Majoranten einer beliebigen k-rekursiven Funktion ),(n~...,nk) der' I-ten Stufe vorkommen warden (in dem Sinne, dag ftir ein geeignetes m, falls max (n~ . . . . . n~:) genfigend grog ist, 7 ( n l , . . . , nk) < ~,~(max (n~ . . . . , n~) gilt).

a, , . (n l , . . . , n k ) = a(m, n ~ , . . . , n,,:)

gesetzt, erg~ibe sich far diese Majorantenfunktion der k-rekursiven Funktio- nen der I-ten Stufe eine k-fache Rekursion der lI-ten Stufe. Diese Rekursion liege sich auch auf k einfache Rekursionen aufl6sen; und als k-t-1-te maitre noch die einfache Rekursion far I dazukommen. (Dal~ es abet eine 1-rekur- sive Funktion der lI-ten Stufe gibt, welche auf der I-ten Stufe nicht k-rekursiv ist, erfordert nicht einen so langwierigen Beweis: es ist bekannt,~adaf5 es eine k@ 1-rekursive Funkfion der I-ten Stufe gibt, welche nicht k-rekursiv ist, und diese k + 1-rekursive Funktion 1/~l]t sich nach {} 1 auf k-k 1 einfache Rekur- sionen tier II-ten Stufe aufl6sen.) Im Aufbau einer Funktion der II-ten Stufe kOnnen jedoch nut Rekursionen yon einer endlichen Anzahl teilnehmen. Auf diesem Wege kann man daher keine Funktion der II-ten Stufe erhalten, welche die k-rekursiven Funktionen der I-ten Stufe far alle k insgesamt majorisieren wfirde.

(Eingegangen am 9. Oktober 1951.)

13 Siehe FuBnote 9

HOHERE STUFEN VON REIs FUNKTIONEN 273

HPOBdlEMbI TEOPIAH FIA21BBEPTA PEKYPCIABHBIX OYHKI~IAIYl BBICI 1 IIAX KJIACCOB

P. F I3T3P (By~anemT)

(P e a to M e)

Apn4)MeTnnecKue qbyn~:~uu, KOTOpble MOFyT 6BITB lqQCTpOeHHbl Ha HeI~OTOpblx OCHOBHblX t~ynKt~n~i nyT~M Kone~aoro ~ c a a gaMemeHni~ n peKypcni~, HaabmaroTc~ peKypcnBnb~Mn r Pasnuano onpe~eans nOH~THe peKypcnu noayqnM paaHHe Kaaccbi dpynKtmi4 (l<OTOpbIe qaCTO n rpaan pOIlb 13 Hccae~oBaHn~X ocnoBann~ MaTeMaTnKH). I/Iccne~oBaamo c ~ z u paaanqnsix ~aaccoB peKypcnBnr~ix ~0yHKL~n~i ~aa TO2IHOK TOT MeTO~, KOTOpBIM F , zs6epT~ XOTe3 pemnTb npo6neMy KOnTnHyyMa. PeqL r l~T O rnnoTe3e, coraacno l<OTOpO~ ~e~3y CqeTHBIM MHOM~efiTBOM 14 MHOM~eCTBOM KOHTnHyyMa He Cyltl, eCTByeT npoMe~yTOqHblM MH0~KeCTB. Tan ~aK MHO~eCTBO apnqb~eTnqecKnx qbynKL~n~i eCTb MHO~eCTBO MOII~HOET~I ~OnTnHyyla, Fnab6epT XOTeY/ ~o~aSaTb rr~noTe8y TeM, qTO K 6oaee BBICOKHM TpaHC@HH!~ITHblM qnc~aM o n p e ~ e ~ e T pe~ypcnn ,,6oaee BbICOKI/Ie a !/l 170Ka3blBaeT~ ttTO npe~no~on<enne, coraacuo ~OTOpO~y apnqbMeTHqecKne ct~ynKt~n , onpeAea6HHb~e Bce 6oaee BbICOKH/~iI4 pe~ypcnnmn, ucqepb~Ba~OT MHo~eCTBO Bcex apuqb~eTuqec~ux Mtlo~ecTB, He Be~T K a6cypay~y. B aTnX ncc.~eaoBanu~x 6buTo onpeaeaeno non~TUe pe~ypcnBnb]X ~yH~RU~i BBICmnX ~accoB: O r R ~ X uaacca I, IL IIl u T. a- ro~opnm COOTBeTCTBeHrlO woMy, qTO B nocTpoe~nn np~nru~a~ow yqacTue auras qbymr 3anuc~iRne OT qI, IC~leHUOFO nepeMennoro, rain npnHr~atoT yqacTue n qbyn~auu, 8 a s n c ~ n e OT qbyn~t~nonaab~bix nepeMeHnsix, qbyn~t~no qbyH~t~noHaa~nb~x nepe- MeHHbIX 14 T. ~.

/ la~ TOrO, qTO6~I s~moaaaTs n p o r p a ~ y Fna~6epTa, Hya<HO n p e ~ z e scero aogaaaT~, qTO ss~ctune ~aaccs~ ~aroT n aoBsie r Hanpn~ep, ;~o~aaaT~, ~TO cymecTsyeT pe~yp- c ~ n a ~ dpyn~L~ ~zacca I1, ~r He ~ o ~ e T 6blTb onpe~ezena, ~ ~r I. A ~ e p ~ a n ~ ao~aaaa 3TO, ecnn orpaHnqnTbC~ cayqaeM o;mo~paTnb~x pe~ypcn~i (~or~a pe~ypcnn nponaso- ~TCn no OaHOMy nepe~enHo~y). Ho ~syx~paTnoii pe~ypcne~i n s ~aacce I ~O~eT 6S~TS onpe~;eaena pe~ypcnn AgicepMaHa. Ecan pa3pemu~ ~norogpaTnbm peIcypcnn, no n a c T o ~ i ~ 3enb ne paapem6n BOnpoc: flBa~eTcn-an rc3acc II o6mnpnee gaacca I. I~aar aTO ~a~ paapemenn~ ~TOH npo6neMbt MeTog; Ma6pnaartna Auuep~ana He FO~nTC~I.

Ha ~ e ~ y u a p o ~ n o ~ ~aTe~aTnqecKo~ uonrpecce B Oczo B 1936-OM FO~y asTop yTsep~- ~ana, qTO ~noro~paTHO pe~ypcuBn~te q b y ~ a n ~aacca I TO~/~eCTBennB~ O~nO~<paT~hl~ pe~yp- CH~IM Khacca ]]. ~)TO yTBep~eHHe OCHOBbIBa.rIOCb Ha TOM npe~noao~ennn , ~TO ~aK n B K~acce 1, 4 B K~acce 11, ~O~HO 0~HoKpaTHBIe ,,BIr pe~ypc~n CBeCT!/I K ,,HpklMI/ITHB-

Hb~M" pe~ypcnn~ (n KOTOpblx nepe~ennbie ne yqacTsy~o~ne s pe~ypcnn OCTa~O~C~i Hen3~en- HBIM!~I); /Xo~cagaTe~bCTBO 6blaO oqeHb C~OY~HO n OTHOCgII~Hec~I I< ae~y 3anncn npona:m BO ~ p e ~ nominal

Ce~iqac a/3TOp nnepsr~e n y 6 a ~ y e T o6u4ee ~oKa3aTe~bCTB0 TOFO, qT0 r~Horo~paTno peuypcnsnble qbyHra~nn ~aacca I MOryT 6bITb onpel~eaenH ~ Knacce I10~HOKpaTHBI~I4 pe~yp- tHUMB; n ~a~T OqeHb npocTo~i HOBbli~ MeTO~ cBe~enn~ i3pIJMnT~BHbIX O&ltoI~paTnblX pe~ypcu~i xaacca II ~ ~HoroupaTnhiM p e ~ y p c n ~ ~aacca L 9TOT ~eTO~ ~O~eT ynoTpe6a~TSC~ a s Taunx cayqa~x supanaeHu~ (n ~an ~HOroupaTnMX peuypcn~i), UOTOpSm CTpOnTC~ nO MeTO~y CTpOeHn~ BKpaluIeHHBIX peuypc.~i enacca I, F~e BKpan~IeHttb~e 8HaqeH~ BcTpeqar0TC~ a~mb Ha ~ecTax qHc3IeHHblX nepeMeHHbiX.

Ho ~a~ Knacca 11 xapa~TepHa BO~3MOMCHOCTb ~ p a n n e n a ~ HOBOFO Tnna: ~or~a ~ p a n - zennHe 3Haqean~ qbrwypnpy~T na MecTe c~yn~tmonaabnb~x nepezaenustx. E c n , ~b~ XOTI/IM npnBeCTn Tat<ytO pe~ypcn~ ~ Ilpai~InTHBno~i cTapbti~ n~tn HOBhI~ ~eTO~O~, ny~gnO ncnoa~- aOBaTB TaKyro qbynr~u~o, OT 0RHOFO apryMeHTa ~r 8a~CnT cuonsgn~n n e p e ~ e n n s ~ n o6aa~aeT cl)ynKttnn npn ~anHo~ apryMenTe.

274 R. P~TER: H(JHERE STUFEN VON REKUIISIVEN FUINKT!ONEN

HoBa:a (~y~K~u:~ ~ BCTpeqamlRaqc~ np~a npHMeHea~H HOBOrO MeTolla~ MOX<eT 6hXTb ~xaaa rlp~ rtoMom~I 6ecl<oaeuHo-~paTHo.~ pei<ypct~H i~nH Tpauc)aH~THOii pe~<yr~cHe~i THna ~o~o HaBeCTuO, a ~rO o n p e ~ e n e ~ e , , /marouanh~o~ et~yu~u~" ,#, BblBO~fllJJ, e~l I48 Knacca I, ~a~oe n<e. Ho onpe~eneuue p , ,nonuoe", B TO Bpem~ RaR oupe~eaeuu~o 6 ~10~<eT 6blTb ]l, aH0 Haa- ea~ue ,,pacuhme~uo~i" 6eCROgeqHo-KpaTHO~ Ua~, COOTBeTCTBeHPiO, Tpa~C{~II~HTHOI~ f3eRypcuI, I, Ta,< i<aR nocne Toro, Ka~ ~a~,~ RaguM RaKofi-TO apry~e~w, ~p o~asbmaeTc~ t~ym<Rgei~ r n e p e - ~enm,~x, TO B onpe~eaenn~ ,p (n , + 1 , . . , , n~ + 1) np~nnMaeT yuacT~e u Tahoe a~auen~,~e % ROTOpOe oua n p u n i ~ a e T npu nepsoM apry~enTe n~, ~ TaK0e, ROTOp0e ona. np~uu~aeT npn n~ + 1, nr ~ e p ~ i x a~yx apry~enTax u T. ~. 6ea npo6eaa , ~o ~(n~ -t- 1 . . . . . n~_~ + 1, n~),

t~ TO gpeM9 Ra~: B onpeae~iennn d p e w p c n ~ na Ranchos ~ecTe nponcxo~lnT np~ n o ~ o . ~ oripe,~e.rl~Hvioro ,-iHc~ia iTepeMeHHblX, HOB pasvihlM MecTax no pagHblN nepe~eaubiM. T a ~ M o6paaoM oqeu~, coMi~m-e.~bHO, MOX~nO nn OrlpeRe.~HTb B Kaacce 11 qbyn~anm % BblXOa~mylo I~S i~:lacca I.

g CB~an c DTHM BOaHnRalOT n caMn no ce6e nHTepecvlble npo6~embl. ECTb .rill n p o - ~e .yTOqnt ,m c'reneHn Me*~y pewpc~i~Mn ~ npn ~OHeqHOM k ( k - - ~paTnt,IMU ~aacca 1) u nO.rlttblM~I TpaHCC~HHHTHblMH T~iiIa co ~o, KOTOpble He MOryT 6blTb BglFITI:,I HH B O~Hy Ha H,VlX. 9' (3~Iecb M0>RHO qyBCTBOgaTb HeI<OTOpOe CX0~CTB0 C I~O~Hg~T~IeM Bonp0ca l~po6,aeMbl KOHTHHyyMa. HOB IIpOTHBOIIOJI0YlZHOCT IlpO60i-Me KOHTHHyyMa~ 3~eCb l<a)~eTc91 BepoftTHMM CyLRecTsoBaH~e

npo ie~yTourmlX c'renerae~). Henba~ a n n o n w m penypcum T~rla 0% CBeCTU Ir pacn~n~uuoi l p e w p c ~ u 8~mmero

THna? (H B cB~a~ c aTOM onpeaenuT~ ~ a r o n a a 6 n y m tl~yn~tmm p e c a n ne ~ ~nacce II, TO B ~a~oM ma6ypib ~l~cme~ i<zacce?) Bilbao 6~,~ n~Tepecno uccne~o~a'rb ~ To, " rpanc~nn~T~ie

p e w p c H n I<aROFO THrla xapagTepnM ~af~ BI:,ICtlIHX ~:aaccoB.