\(\begingroup\)
Ich möchte hier eine kleine Einführung in die Theorie der rekursiven Funktionen geben. Es handelt sich ausschließlich um Funktionen, deren Argumente natürliche Zahlen sind: 0,1,2,3,... .
Der Begriff der rekursiven Funktion dient vor allem dem Zweck, Funktionen, die prinzipiell mit Hilfe eines Algorithmus berechnet werden können (berechenbare Funktionen), von solchen Funktionen abzugrenzen, die nicht berechenbar sind.
Wir werden im folgenden definieren, was man unter rekursiven Funktionen versteht.
Solche Funktionen sind, wie die Definition zeigt, berechenbar.
Sind mit den rekursiven Funktionen alle berechenbaren Funktionen ausgeschöpft?
Man weiß es nicht, aber Alonzo Church (1903-1995) meint, ja.
Diese Behauptung ist als Churchsche These bekannt, beweisen kann man sie nur, wenn man den Begriff "Berechenbarkeit" näher konkretisiert.
Das geht, solche Konkretisierungen gibt es sehr viele (Turing-Maschinen, Register-Maschinen, Loop-Programme). Es hat sich herausgestellt, daß alle irgendwie denkbaren Begriffe von Berechenbarkeit auf Turing-Maschinen zurückgeführt werden können, und daß für einen solchen Begriff von Berechenbarkeit die Churchsche These richtig ist.
Auf den Zusammenhang der rekursiven Funktionen mit Turing-Maschinen möchte ich indessen nicht näher eingehen, sondern schränke mich darauf ein, rekursive Funktionen zu definieren und ihre Eigenschaften zu untersuchen.
§ 1. Primitiv rekursive Funktionen
Wir betrachten Funktionen f(x1,...,xn), die von n Argumenten abhängen, die natürliche Zahlen sind, und deren Werte ebenfalls natürliche Zahlen sind.
Um anzugeben, wieviel Argumente eine Funktion f hat, sprechen wir von einer n-stelligen Funktion. Es gibt auch 0-stellige Funktionen, die überhaupt keine Argumente haben, dies sind die Konstanten, also die natürlichen Zahlen.
Unter diesen Funktionen zeichnen wir eine besondere Teilmenge aus, die wir primitiv rekursive Funktionen nennen.
Nur die Funktionen heißen primitiv rekursiv, die diese Eigenschaft aufgrund von endlich vielen Anwendungen der Regeln 1. - 5. besitzen.
1. Die 0\-stellige Funktion, die gleich der Konstanten 0 ist, ist primitiv rekursiv.
2. Die einstellige Funktion s(x) = x + 1, die Nachfolgerfunktion, ist primitiv rekursiv.
3. Die n\-stellige Funktion I_m^n, die das m\-te Argument auswählt: I_m^n(x_1\,...\,x_n)=x_m,
ist für m=1,...,n primitiv rekursiv.
4. Wenn f eine n\-stellige und g_1\,...\,g_n \ m\-stellige primitiv rekursive Funktionen sind, dann ist die Funktion h=f ° (g_1\,...\,g_n), die durch
h(x_1\,...\,x_m)=f(g_1(x_1\,...\,x_m),...,g_n(x_1\,...\,x_m)) definiert ist, eine m\-stellige primitiv rekursive Funktion.
5. Wenn g eine n\-stellige und h eine (n+2)\-stellige primitiv rekursive Funktion ist, dann ist die durch
f(x_1\,...\,x_n,0)=g(x_1\,...\,x_n) und f(x_1\,...\,x_n,y+1)=h(x_1\,...\,x_n,y,f(x_1\,...\,x_n,y))
definierte Funktion f eine (n+1)\-stellige primitiv rekursive Funktion.
Wir untersuchen nun die arithmetischen Grundoperationen +, - und * auf primitive Rekursivität.
Für die Addition x+y kann man die zweistellige Funktion Add(x,y) durch
Add(x,0)=x, Add(x,y+1)=s(Add(x,y)) einführen, die nach den Regeln 2., 3. und 5. aus der einstelligen Funktion g(x)=I_1^1(x)=x und der dreistelligen Funktion h(x,y,z) = s(I_3^3(x,y,z))=s(z) gebildet ist.
Die Multiplikation x*y wird durch die Funktion Mult(x,y) gemäß
Mult(x,0)=0, Mult(x,y+1)=Add(Mult(x,y),x) geliefert.
In der Regel 5. ist dabei g die einstellige Funktion, die überall gleich 0 ist: g(x)=0, sie ist wegen der Regel 1. und der Regel 4. für m=1 und n=0 primitiv rekursiv, und die Funktion h mit
h(x,y,z) = Add ° (I_3^3, I_1^3)(x,y,z)=Add(z,x) ist primitiv rekursiv wegen Regel 3. und 4.
Weil die Funktionen nur Werte ≥ 0 haben dürfen, kann man die Differenz x - y nicht als Funktion einführen, sondern muß die Positivdifferenz x -. y
=fdef(x-y, wenn x>=y;0, wenn x. y erfolgt in zwei Schritten:
Als Gegenstück zur Nachfolgerfunktion s(x) = x + 1 definiert man die Vorgängerfunktion Pred(x) durch
Pred(0) = 0, Pred(x+1) = x.
Der Wert Pred(0) = 0 bildet hierbei eine Ausnahme, da die erste natürliche Zahl 0 keinen Vorgänger hat.
Die Positivdifferenz ist dann durch Diff(x,0) = x, Diff(x,y+1) = Pred(Diff(x,y)) festgelegt, auch diese Definition ist gemäß Regel 5. aufgebaut.
Wir haben die grundlegenden Funktionen Add, Mult, Pred, Diff als primitiv rekursiv erkannt.
Diese Funktionsnamen wollen wir von jetzt an nicht mehr benutzen, sondern verwenden die gewohnte Schreibweise:
Add(x,y) = x + y, Mult(x,y) = x * y, Pred(x) = x -. 1, Diff(x,y) = x -. y.
Mit der Schreibweise x - y wird ferner angezeigt, daß dies eine Positivdifferenz x -. y von Zahlen x ≥ y ist, in diesem Fall wird also der Punkt am Minuszeichen unterdrückt, da es sich um die gewöhnliche Differenz handelt.
§ 2. Weitere grundlegende primitiv rekursive Funktionen
Die Addition, Positivdifferenz und Multiplikation sind zweistellige primitiv rekursive Funktionen, aber zum Aufbau der Theorie werden weitere Funktionen benötigt.
Die folgende Funktion ist ganz unscheinbar, aber sehr nützlich, sie hilft uns bei der Durchführung von Fallunterscheidungen.
Es ist die If\-Funktion, sie lautet If(x,y,z)=fdef(z, wenn x=0;y, wenn x>0).
Sie genügt der überaus einfachen Vorschrift If(0,y,z) = z, If(x+1,y,z) = y, diese ist zwar nicht gemäß Regel 5. aufgebaut, weil die Rekursion nach dem ersten Argument x und nicht nach dem letzten Argument z erfolgt. Indessen ist dies unwichtig, auch Funktionen, die durch Rekursion nach einem beliebigen (nicht unbedingt dem letzten) Argument, definiert sind, sind primitiv rekursiv, wie folgende Überlegung zeigt.
Die Funktion ReverseIf(x,y,z) = If(z,y,x) erfüllt die Rekursionsvorschrift
ReverseIf(x,y,0) = x, ReverseIf(x,y,z+1) = y, sie ist nach Regel 5. primitiv rekursiv, und nach den Regeln 3. und 4. ist auch
If(x,y,z) = ReverseIf ° (I33,I23,I13)(x,y,z) = ReverseIf(z,y,x) primitiv rekursiv.
Die Folge 0,1,3,6,10,15,... der sogenannten Dreieckszahlen definiert die Funktion
d(x) = 1+2+...+x, die die Summe der ersten x positiven ganzen Zahlen angibt.
d ist primitiv rekursiv, denn d(0) = 0 und d(x+1) = d(x) + s(x) = d(x) + x + 1 ist eine Vorschrift dafür, die Regel 5. genügt.
Nun kommt etwas sehr Wichtiges:
Die Cantorsche Paarfunktion c(x,y), sie ist durch c(x,y) = d(x+y) + x definiert.
Sie liefert eine bijektive Abbildung von der Menge N x N aller Zahlenpaare (x,y) auf die Menge der natürlichen Zahlen N.
Beweis:
Es sei w eine natürliche Zahl.
In der Folge 0,1,3,6,... der Dreieckszahlen gibt es eine größte Zahl d(n), die ≤ w ist. Dann ist d(n) ≤ w < d(n+1) = d(n) + n + 1, und für die Differenz x = w - d(n) gilt dann 0 ≤ x ≤ n. Wenn man y = n - x setzt, dann ist y die gewöhnliche Differenz von n und x, und es ist n = x + y und schließlich w = d(n) + x = d(x+y) + x = c(x,y).
Damit ist die Darstellbarkeit jeder natürlichen Zahl w als w = c(x,y), also die Surjektivität der Abbildung, gezeigt.
Wenn (u,v) ein Zahlenpaar mit c(u,v) = c(x,y) = w ist, dann gilt
d(x+y) ≤ c(x,y) = w = c(u,v) = d(u+v) + u < d(u+v) + u + v + 1 = d(u+v+1).
Da die Funktion d streng monoton ist, folgt x+y < u+v+1 und damit x+y ≤ u+v.
Durch Vertauschung der Rollen u <--> x und v <--> y erhält man auch
u+v ≤ x+y, also ist die Summe n = u+v = x+y für beide Paare (x,y) und (u,v) dieselbe.
Schließlich ist u = c(u,v) - d(n) = w - d(n) = c(x,y) - d(n) = x und
v = n - u = n - x = y, das Paar (u,v) stimmt mit dem Paar (x,y) überein.
Damit ist die Injektivität der Abbildung gezeigt.
Die Funktion c : N x N --> N hat somit eine Umkehrfunktion, die von N auf N x N abbildet, es handelt sich um ein Paar von einstelligen Funktionen, die aus der Zahl w = c(x,y) den linken Teil x und den rechten Teil y des Paars (x,y) berechnen.
Wir bezeichnen diese Funktionen wie üblich mit l(w) und r(w), ihre definierende Eigenschaft lautet
c(l(w),r(w)) = w. Ferner gilt l(c(x,y)) = x und r(c(x,y)) = y.
Die Funktionen l und r sind primitiv rekursiv, denn es ist
(1) l(0) = 0 und l(x+1) = If(d(l(x)+1) -. x, 0, l(x)+1) und
(2) r(0) = 0 und r(x+1) = If(r(x), r(x)-1, l(x)+1).
Das Interessante an diesen Rekursionsvorschriften ist ihre Einfachheit, üblicherweise definiert man diese Funktionen auf andere, viel kompliziertere Weise, indem man u. a. die Multiplikation, ganzzahlige Quadratwurzel und ganzzahlige Division benutzt.
Der Beweis von (1) und (2) möge dem Leser überlassen bleiben.
Einstellige Funktionen sind nichts anderes als Zahlenfolgen, die Wertefolgen der Funktionen l(w) und r(w) für
w = 0,1,2,3,... lauten
l(w) = 0,0,1,0,1,2,0,1,2,3,0,1,2,3,4,... und
r(w) = 0,1,0,2,1,0,3,2,1,0,4,3,2,1,0,... .
Ferner kann man den Verlauf der Cantorschen Paarungsfunktion c(x,y) aus diesem Schema ablesen:
10 16 23 31 40
6 11 17 24 32
3 7 12 18 25
1 4 8 13 19
0 2 5 9 14 ,
dabei ist x = 0,1,2,... die Spaltennummer von links nach rechts und
y = 0,1,2,... die Zeilennummer von unten nach oben.
Die Funktionen, die man in der Zahlentheorie verwendet, sind alle primitiv rekursiv.
Wenn x und y natürliche Zahlen mit y > 0 sind, dann kann man x durch y dividieren und bekommt einen Divisionsrest, den man mit x mod y bezeichnet.
Die Funktion, die durch Mod(x,y) = x mod y definiert ist, ist primitiv rekursiv, denn
Mod(0,y)=0 und Mod(x+1,y)=fdef(0, wenn Mod(x,y)+1=y;Mod(x,y)+1, sonst)
ist eine nach Regel 5. aufgebaute Vorschrift \(die Fallunterscheidung muß man mit Hilfe der If\-Funktion ausdrücken\), abgesehen davon, daß die Rekursion nach dem ersten Argument erfolgt. Wie schon erwähnt, spielt dies keine wesentliche Rolle und hindert die Funktion Mod nicht daran, primitiv rekursiv zu sein.
Auch die Funktion Pr(n)=p_(n+1)\., die die Folge der Primzahlen
Pr(0)=p_1=2, Pr(1)=p_2=3, Pr(2)=p_3=5, ... angibt, ist primitiv rekursiv.
Die folgende Formel beweist dies (fast):
Pr(n)=sum(csg(sum(csg(sum(csg(m mod d),2<=d0), \ siehe § 4, (e).
Die rechte Summe zählt die Anzahl der Teiler von m mit 2<=d= p_(n+1) ist. Eine solche Funktion ist zum Beispiel b(n)=2^2^n\., und natürlich ist diese Funktion primitiv rekursiv.
Ferner können die auftretenden Summenzeichen auf eine Rekursionsvorschrift zurückgeführt werden, denn es gilt:
Wenn f(x_1\,...\,x_n,y) eine (n+1)\-stellige primitiv rekursive Funktion ist, dann ist die (n+2)\-stellige Funktion F(x_1\,...\,x_n\,y,z), definiert durch
F(x_1\,...\,x_n\,y,z)=sum(f(x_1\,...\,x_n\,k),y<=k§ 3. Definition von Funktionen durch Verlaufsrekursion
Es gibt allgemeinere Arten, Funktionen durch Rekursionsvorschriften zu definieren, als die in § 1 behandelte.
Kein Zweifel besteht daran, daß manche Vorschriften, die über § 1 hinausgehen, ebenfalls berechenbare Funktionen definieren (man kann es programmieren, und es steht fest, daß dabei keine Endlosschleife auftritt).
Für Funktionen, die durch eine sogenannte Verlaufsrekursion festgelegt werden, möchten wir nun beweisen, daß diese ebenfalls primitiv rekursiv sind.
Das Standardbeispiel hierfür ist die Fibonacci-Folge, die durch
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) festgelegt ist.
Die Fibonacci-Funktion F ist primitiv rekursiv, aber mit den Mitteln des § 1 ist es nicht ohne weiteres möglich, das zu beweisen.
Die folgenden Untersuchungen liefern den Beweis der primitiven Rekursivität für solche und ähnliche Funktionen.
Wir haben eine endliche Anzahl von (n+1)\-stelligen Funktionen
\a_j \ (j=1,...,m), die die Ungleichung \a_j(x_1\,...\,x_n\,y)<=y erfüllen, eine n\-stellige Funktion g und eine (m+n+1)\-stellige Funktion h.
Für die n\-gliedrige Folge x_1, ..., x_n benutzen wir x als Abkürzung.
Wir sagen, eine (n+1)\-stellige Funktion f wird durch Verlaufsrekursion aus den angegebenen Daten gebildet, wenn f(x,0)=g(x) und
f(x,y+1)=h(x,y,f(x,\a_1(x,y)),...,f(x,\a_m(x,y))) ist.
Wenn die Funktionen \a_j(x,y)<=y und die Funktionen g und h primitiv rekursiv sind, dann ist auch f primitiv rekursiv.
Beweis:
Wir definieren eine Funktion w(x,y) durch
w(x,0)=c(g(x),0), w(x,y+1)=c(f(x,y+1),w(x,y)).
Diese Funktion ist wohldefiniert \(weil das Argument y mit jedem Rechenschritt um 1 abnimmt und schließlich 0 erreicht\), und w(x,y) ist gleich
c(f(x,y),c(f(x,y-1),c(f(x,y-2),...,c(f(x,0),0)...))),
das ist eine mit Hilfe der Cantorschen Paarfunktion c bewirkte Codierung der Liste
f(x,y),f(x,y-1),...,f(x,0) aller Werte f(x,i) mit 0<=i<=y.
Die Funktion Index(w,i), die aus einer solchen Liste das i\-te Element \(Zählung beginnt mit 0\) auswählt, ist primitiv rekursiv, denn
Index(w,i)=l(Rest(w,i)), dabei ist Rest(w,i)=r^i(w) die Codierung der Liste, die aus der durch w codierten Liste durch Weglassung der ersten i Elemente entsteht, r^i bedeutet die i\-fache Anwendung der Funktion r.
Die Funktion Rest ist primitiv rekursiv, weil sie durch
Rest(w,0)=w, Rest(w,i+1)=r(Rest(w,i)) definiert werden kann.
Für i<=y ist Rest(w(x,y),i)=w(x,y-i), daraus folgt Index(w(x,y),i)=f(x,y-i).
Wegen \a_j(x,y)<=y ist \a_j(x,y)=y-i mit i=y-\a_j(x,y),
und es gilt f(x,\a_j(x,y))=Index(w(x,y),y-\a_j(x,y)) und
w(x,y+1)=c(f(x,y+1),w(x,y))
=c(h(x,y,f(x,\a_1(x,y)),...,f(x,\a_m(x,y))),w(x,y))
=c(h(x,y,Index(w(x,y),y-\a_1(x,y)),...,Index(w(x,y),y-\a_m(x,y))),w(x,y)),
dies ist, zusammen mit w(x,0)=c(g(x),0), eine Rekursionsvorschrift für w(x,y), die Regel 5. entspricht.
Also ist w(x,y) primitiv rekursiv und damit auch f(x,y)=l(w(x,y)), was zu beweisen war.
Für die Fibonacci\-Folge F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) muß man zum Beweis der primitiven Rekursivität nicht die komplette Liste aller vorhergehenden Funktionswerte heranziehen, sondern es genügen die beiden letzten Funktionswerte, dadurch kann der Beweis vereinfacht werden.
Für die Hilfsfunktion w(n)=c(F(n+1),F(n)) gilt die Rekursionsvorschrift
w(0)=c(1,0)=2, w(n+1)=c(l(z)+r(z),l(z)), wobei z=w(n).
Dann ist w und somit auch F(n)=r(w(n)) primitiv rekursiv.
§ 4. Erzeugung einstelliger primitiv rekursiver Funktionen
Mit dem Begriff "primitiv rekursive Funktion" werden nicht nur einstellige, sondern auch mehrstellige Funktionen erfaßt. Mehr noch, es erweist sich bei Verwendung der Regeln 1. - 5. als notwendig, mehrstellige Funktionen (deren primitive Rekursivität man beweist) heranzuziehen, auch wenn man schließlich nur die primitive Rekursivität einer einstelligen Funktion beweisen möchte.
Zum Beispiel ist die Funktion u, die durch u(x) = x2 definiert ist, sicherlich primitiv rekursiv, jedoch bestehen die Beweisschritte darin, daß die zweistelligen Funktionen x+y und x*y primitiv rekursiv sind.
Sollte die Regel 5. zur Konstruktion zweistelliger Funktionen f verwendet werden, dann kommen sogar dreistellige Funktionen h ins Spiel.
Ist es nun möglich, den Begriff "einstellige primitiv rekursive Funktion" aus sich selbst heraus zu definieren, ohne mehrstellige Funktionen zu benutzen?
Natürlich müssen dann die Regeln 1. - 5. durch andere Regeln ersetzt werden.
Die Regeln 1. und 3. entfallen, Regel 4. wird auf den Fall einstelliger Funktionen, also m = n = 1, eingeschränkt.
In Regel 5. nehmen mehrstellige Funktionen einen wesentlichen Platz ein, diese Regel muß man streichen und dafür andere Regeln, die nur von einstelligen Funktionen handeln, erfinden.
Man verdankt Raphael M. Robinson (1947) die grundlegende Erkenntnis, daß das möglich ist.
Wir definieren eine Klasse von Funktionen, die wir "zulässig" nennen wollen.
Nur die einstelligen Funktionen heißen zulässig, die diese Eigenschaft aufgrund von endlich vielen Anwendungen der folgenden Regeln A. - E. besitzen.
A. s(x) = x + 1 ist zulässig.
B. l(x) ist zulässig.
C. Wenn f und g zulässig sind, dann auch die Summe f + g beider Funktionen.
D. Wenn f und g zulässig sind, dann auch f ° g.
E. Wenn f zulässig ist, dann auch die Funktion f#(x) = fx(0).
Bei Regel E. nennt man f# die Iteration der Funktion f, und
fx(0) bedeutet, daß die Funktion f x-mal hintereinander auf 0 angewendet wird:
f#(0) = 0 und f#(x) = fx(0) = f(f(...(f(0))...)), das f tritt x-mal auf.
Die Bezeichnung f#(x) habe ich nirgendwo gelesen, sondern ich verwende sie, weil ich sie zweckmäßig und einprägsam finde.
In Büchern und Artikeln wird dafür das Zeichen Jf oder fJ verwendet.
Ferner erweitern wir den Begriff "zulässig" auf mehrstellige Funktionen, indem wir definieren:
F. Eine n-stellige Funktion f heißt zulässig, wenn für beliebige einstellige zulässige Funktionen g1,...,gn die Verkettung f ° (g1,...,gn) zulässig ist.
Für n = 0 handelt es sich um die Verkettung einer Konstanten f mit einer leeren Argumentliste: f ° (), ebenso wie für n > 0 muß man diese Verkettung als eine einstellige Funktion auffassen, sie hat einen konstanten Wert.
Für n = 1 ist Regel F. keine Definition, weil einstellige zulässige Funktionen bereits definiert sind.
Sie gilt aber als Äquivalenzaussage:
f ist zulässig <==> f ° g ist zulässig für alle zulässigen Funktionen g.
"==>" ist Regel D., und "<==" ist auch richtig, weil man nach den Regeln A. und E. die Funktion s#(x) = x, die identische Funktion, für g einsetzen kann.
Alle einstelligen zulässigen Funktionen sind primitiv rekursiv im Sinne der Regeln 1. - 5. von § 1.
Die Funktion s(x) aus Regel A. ist nach Regel 2. aus § 1 primitiv rekursiv.
Die Funktion l(x) aus Regel B. ist primitiv rekursiv, siehe § 2.
Eine Funktion nach Regel C. ist primitiv rekursiv, weil die in § 2 definierte Funktion
Add(x,y) = x + y primitiv rekursiv ist.
Regel D. liefert eine primitiv rekursive Funktion wegen Regel 4. für m = n = 1.
f#(x) aus Regel E. genügt der Rekursionsvorschrift f#(0) = 0, f#(x+1) = f(f#(x)),
das ist eine gemäß Regel 5. aufgebaute Vorschrift, also ist f# primitiv rekursiv.
Wir möchten die Umkehrung zeigen:
Jede einstellige primitiv rekursive Funktion ist zulässig.
Die Menge der einstelligen primitiv rekursiven Funktionen ist also die Menge der Funktionen, die aus den Regeln A. - E. erhalten werden können.
Mehr noch, wir können beweisen, daß alle (ein- oder mehrstelligen) primitiv rekursiven Funktionen zulässig sind.
Einfach ist dieser Beweis nicht.
Wir gehen Schritt für Schritt vor und gliedern den Beweis in Teilbehauptungen, die wir mit Buchstaben kennzeichnen. Wir müssen die Regeln 1. - 5. aus § 1 der Reihe nach behandeln.
Wenn man die Regel E. auf die Funktionen aus A. und B. anwendet, dann bekommt man
s^\#\.(x)=x, die identische Funktion, und wegen l(0)=0 ferner
l^\#\.(x)=0, die Nullfunktion.
(a) Die Konstante 0 aus Regel 1. ist zulässig.
Das folgt aus Regel F. für n = 0, weil die einstellige Funktion l^\#\.(x), die identisch gleich 0 ist, zulässig ist.
(b) s(x)=x+1 aus Regel 2. ist zulässig.
Das ist richtig, da dies durch Regel A. gefordert wird.
(c) Die Auswahlfunktion I_m^n aus Regel 3. ist zulässig.
Nach Regel F. muß man zeigen, daß für beliebige einstellige zulässige Funktionen g_1\,...\,g_n die Funktion g_m zulässig ist. Das trifft zu, weil 1<=m<=n ist.
(d) Wenn die n\-stellige Funktion f und die m\-stelligen Funktionen
g_1\,...\,g_n aus Regel 4. zulässig sind, dann ist es auch die Verkettung v = f ° (g_1\,...\,g_n).
Nach Regel F. muß man einstellige zulässige Funktionen h_1\,...\,h_m nehmen und die Zulässigkeit von f ° (g_1\,...\,g_n) ° (h_1\,...\,h_m) beweisen,
dies ist gleich f ° (u_1\,...\,u_n), wobei die Funktionen u_i, die durch u_i=g_i \circ(h_1,...,h_m) definiert sind, zulässig sind, weil g_i zulässig ist. Weil f zulässig ist, ist auch f ° (u_1\,...\,u_n) zulässig, daraus folgt die Zulässigkeit von v.
(e) Die Funktionen c(x,y), r(x) und If(x,y,z) sind zulässig.
Die Iteration der Funktion l(x)+1=sl(x) ergibt die Signumfunktion
sg(x)=(sl)^\#\.(x)=fdef(0, wenn x=0;1, wenn x>0).
Ferner führen wir die Funktionen
csg(x)=l(sg(x)+2)=fdef(l(2), wenn x=0;l(3), wenn x>0)=fdef(1, wenn x=0;0, wenn x>0)
und g(x)=x+1+csg(l(x+3)) ein, alle diese Funktionen sind zulässig.
Die Werte von g sind 2__\,2\,3\,5__\,5\,6\,7\,9__\,9\,10\,11\,12\,14__\,14\,15\,...,
sie hat, außer an den unterstrichenen Stellen, den Wert s(x)=x+1.
Die Iteration von g ergibt die Funktion
g^\#\.(x)=x+l(x)+r(x) mit den Werten 0,2,3,5,6,7,9,10,11,12,14,15,...
Schließlich ergibt (g^\#+1)^\#\.(x) die Funktion d(x),
diese Funktion kann also mit Hilfe der Funktionen l und s, der Addition +
und der Iteration \# als d=(s(s+lss(sl)^\# lsss)^\#)^\# dargestellt werden.
Somit ist die Cantorsche Paarfunktion c(x,y)=d(x+y)+x
und auch die Funktion h(x)=d(x+l(x))+g^\#\.(x)+1
=d(x+l(x))+x+l(x)+r(x)+1=d(x+l(x)+1)+r(x) zulässig.
Wegen r(x)<=x gilt h(x)=c(r(x),x+l(x)+1-r(x)),
daraus folgt, daß auch r(x)=l(h(x)) zulässig ist.
Bleibt noch die Zulässigkeit der If\-Funktion zu zeigen.
Wenn t gleich 0 oder 1 ist, dann ist
l(d(y)+y+t)=fdef(l(d(y)+y)=l(c(y,0))=y, wenn t=0;l(d(y)+y+1)=l(d(y+1))=l(c(0,y+1))=0, wenn t=1).
Die dreistellige zulässige Funktion
l(d(y)+y+csg(x))+l(d(z)+z+sg(x)) ergibt
l(d(y)+y+1)+l(d(z)+z)=0+z=z für x=0, und
l(d(y)+y)+l(d(z)+z+1)=y+0=y für x>0, sie stimmt also mit der Funktion If(x,y,z) überein.
Also ist die If\-Funktion zulässig, was zu beweisen war.
(f) Wenn g eine n\-stellige und h eine (n+2)\-stellige Funktion ist, die beide zulässig sind, dann ist auch die gemäß Regel 5. von § 1 gebildete Funktion f zulässig.
Für beliebige einstellige zulässige Funktionen u_1\,...\,u_n sei w die zweistellige Funktion \blue\ w(x,y)=f(u_1(x),...,u_n(x),y)\black\ .
Nach Regel F. ist f zulässig, wenn die Funktion w(x,u(x)) für jede zulässige Funktion u zulässig ist.
Wir haben uns damit von n\-stelligen Funktionen befreit, nur die Eigenschaften der zweistelligen Funktion w müssen untersucht werden.
Aus der Vorschrift für f ergibt sich die Vorschrift für w:
w(x,0)=g(u_1(x),...,u_n(x)),
die rechte Seite ist, weil g zulässig ist, nach Regel F. wieder eine zulässige Funktion G(x), die von den gewählten zulässigen Funktionen u_1\,...\,u_n abhängt, und w(x,y+1)=h(u_1(x),...,u_n(x),y,w(x,y)),
die rechte Seite ist gleich H(x,y,w(x,y)) mit einer dreistelligen zulässigen Funktion H(x,y,z).
Wir führen die Funktion \blue\ v(x,y)=c(y,c(x,w(x,y)))\black ein, die Cantorsche Paarungsfunktion c bewirkt, daß man mit ihrer Umkehrfunktion l(w), r(w) aus dem Funktionswert v(x,y) die Argumente x=lr(v(x,y)) und y=l(v(x,y)) berechnen kann.
v(x,0)=c(0,c(x,G(x)))=d(c(x,G(x))) ist zulässig, und es gilt v(x,y+1)=c(y+1,c(x,w(x,y+1))).
Wenn man z=v(x,y) setzt, dann ist
x=lr(z), y=l(z), w(x,y)=rr(z) und
v(x,y+1)=c(l(z)+1,c(lr(z),H(lr(z),l(z),rr(z)))).
Die rechte Seite ist eine einstellige Funktion V(z), und es gilt
v(x,y)=V^y d(c(x,G(x))), wobei V^y die y\-fache Hintereinanderausführung der Funktion V bedeutet.
Die Funktion v ist zweistellig, wir müssen sie mit Hilfe einer einstelligen Funktion ausdrücken und führen dazu \blue\ p(x)=c(x,V^array(l(x)) r(l(x)+r(x)))\black ein.
Dann ist p(0)=c(0,V^0(0))=c(0,0)=0 und p(x+1)=c(x+1,V^array(l(x+1)) r(l(x+1)+r(x+1))).
Falls l(x+1)=0, dann ist p(x+1)=c(x+1,rr(x+1)),
und für l(x+1)>0 gilt l(x+1)=l(x)+1 und r(x+1)=r(x)-1.
Damit ist p(x+1)=c(x+1,If(l(x+1),V^array(l(x)+1) r(l(x)+r(x)),rr(x+1))).
Setzt man t=p(x), dann ist x=l(t), V^array(l(x)) r(l(x)+r(x))=r(t) und
p(x+1)=c(l(t)+1,If(l(l(t)+1),V(r(t)),rr(l(t)+1)))).
Wenn man die einstellige Funktion auf der rechten Seite W(t) nennt, dann folgt p(x+1)=W(p(x)) und wegen p(0)=0 somit p(x)=W^x(0)=W^\#\.(x).
Nach Regel E. ist p zulässig. Wir setzen t=c(y,d(y+z)),
wobei z=d(c(x,G(x))) der Anfangswert v(x,0) ist.
Dann ist r(p(t))=V^array(l(t)) r(l(t)+r(t))=V^y r(y+d(y+z))
=V^y r(c(y,z))=V^y z=v(x,y).
Die Zulässigkeit der Funktion v(x,y)=c(y,c(x,w(x,y))) ist damit bewiesen, dann ist auch w(x,y) zulässig, speziell ist für jede zulässige Funktion u(x) die Funktion
w(x,u(x))=f(u_1(x),...,u_n(x),u(x)) zulässig.
Weil dies für alle zulässigen Funktionen u_1\,...\,u_n\,u gilt, ist nach Regel F. die Funktion f zulässig, und (f) ist bewiesen.
§ 5. Allgemein rekursive Funktionen
Die Klasse der primitiv rekursiven Funktionen, die in § 1 eingeführt wurde, ist noch nicht umfangreich genug, um den Begriff von Berechenbarkeit vollständig zu erfassen.
Der Wert f(x) einer einstelligen primitiv rekursiven Funktionen f ist für jede natürliche Zahl x definiert, ebenso kann man bei mehrstelligen Funktionen beliebige Argumente einsetzen.
Nun werden wir Funktionen betrachten, die möglicherweise für manche Argumente nicht definiert sind.
Eine Funktion f heißt rekursiv (auch der Begriff "partiell rekursiv" wird verwendet, um hervorzuheben, daß die Funktion nicht überall definiert sein muß), wenn sie nach folgenden Regeln gebildet ist:
1. Alle primitiv rekursiven Funktionen sind rekursiv.
2. Wenn f eine n-stellige rekursive Funktion und g1, ..., gn m-stellige rekursive Funktionen sind, dann ist auch die m-stellige Funktion f ° (g1, ..., gn) rekursiv.
Ihr Wert f(x1, ..., xm) wird nur dann als definiert angesehen, wenn für alle j=1,...,n die Werte gj(x1, ..., xm) und auch das Ergebnis der Einsetzung in die Funktion f definiert sind.
3. Wenn g eine n-stellige und h eine (n+2)-stellige rekursive Funktion sind, dann ist auch f, definiert durch
f(x1, ..., xn, 0) = g(x1, ..., xn), f(x1, ..., xn, y+1) = h(x1, ..., xn, y, f(x1, ..., xn, y)) rekursiv.
Dabei wird f(x1, ..., xn, y) nur dann als definiert angesehen, wenn alle Vorgängerwerte
f(x1, ..., xn, z) mit 0 ≤ z < y definiert sind und wenn die g-Funktion (für y = 0) bzw. die h-Funktion (für y > 0) für ihre entsprechenden Argumente definiert sind.
4. Wenn g eine (n+1)-stellige rekursive Funktion ist, und y ist die kleinste Lösung der Gleichung
g(x1, ..., xn, y) = 0, dann ist die Funktion f(x1, ..., xn) = y, die diese Lösung angibt, rekursiv.
Die Funktion f hat den Wert f(x1, ..., xn) = y, wenn die Werte g(x1, ..., xn, z) für alle z mit
0 ≤ z ≤ y definiert und ≠ 0 für z < y und = 0 für z = y sind.
Gibt es solch ein y nicht, dann ist die Funktion f undefiniert.
Man nennt f eine allgemein rekursive Funktion, wenn sie nach diesen Regeln 1.-4. gebildet ist und wenn alle dabei auftretenden Zwischenfunktionen, einschließlich der Funktion f selbst, überall definiert sind.
Das bedeutet, bei allgemein rekursiven Funktionen darf der Schritt 4. für solche Funktionen g nicht benutzt werden, für die der in grün hervorgehobene Fall eintritt.
§ 6. Universelle Funktionen
In diesem Abschnitt benötigen wir nicht nur die Cantorsche Paarungsfunktion c(x,y), sondern auch Funktionen, die die Codierung von Tripeln (u,v,w) ermöglichen.
In § 3 haben wir bereits eine Codierung von n-Tupeln benutzt, die wir hier auch verwenden könnten. Da Paare und Tripel im Folgenden häufig vorkommen, verwenden wir eine verkürzte Schreibweise für ihre Codierung.
Mit [x,y,z] bezeichnen wir den Wert einer beliebigen, aber festen primitiv rekursiven Abbildung von N x N x N in N mit folgenden Eigenschaften:
(i) Es gibt primitiv rekursive linksseitige Umkehrfunktionen i_0, i_1, i_2 dieser Abbildung: i_0([x,y,z]})=x, i_1([x,y,z])=y, i_2([x,y,z])=z,
somit ist die Abbildung (x,y,z) \mapsto [x,y,z] injektiv.
(ii) i_1(w)0.
Um Paare zu codieren, verwenden wir [x,y] als Abkürzung für [x,0,y].
Sowohl die Codierung [x,y,z]=c(x,c(y,z)) als auch die davon verschiedene Vorschrift [x,y,z]=(x+y+z+2;3)+(x+y+1;2)+x erfüllen die Forderungen (i), (ii) und sind darüber hinaus sogar bijektiv, außerdem ist [0,0]=0 und [0,1]=1, diese beiden Gleichungen werden aber im Folgenden nicht vorausgesetzt, obwohl dadurch an einigen Stellen Vereinfachungen eintreten würden.
Wir führen nun eine Funktion U durch folgende Gleichungen ein, die Untersuchung ihrer Eigenschaften ist das Ziel dieses Abschnitts.
\blue\ U([0,0],x)=s(x),
\blue\ U([0,1],x)=l(x),
\blue\ U([1, g_1, g_2],x)=U(g_1, x)+U(g_2, x),
\blue\ U([2, g_1, g_2],x)=U(g_1\,U(g_2, x)),
\blue\ U([3, g_1],x)=U(g_1, U([3, g_1],x-1)), wenn x>0,
\blue\ U(g,x)=0 für alle übrigen Argumentpaare (g,x).
Die Funktion U ist für alle ihre Argumente wohldefiniert, obwohl wir noch sehen werden, daß sie nicht primitiv rekursiv ist.
Um U(g,x) zu berechnen, muß man ermitteln, ob g=[0,0] oder g=[0,1] ist, oder ob g in der Form [1, g_1, g_2], [2, g_1, g_2] oder [3, g_1] darstellbar ist. Mit Hilfe der Funktion i_0 zeigt man, daß höchstens einer dieser Fälle eintreten kann.
Das ist auch notwendig, weil sonst die Definition der Funktion U mehrdeutig wäre und widersprüchlich sein könnte.
Die Bedingung, daß g=[1, ?, ?] ist, lautet g=[1, i_1(g), i_2(g)],
g=[2, ?, ?] bedeutet g=[2, i_1(g), i_2(g)],
und g=[3,?], das ist als [3, 0, ?] definiert, bedeutet g=[3, i_2(g)].
In diesen Fällen ergeben die ersten beiden Formeln U(g,x) unmittelbar, bei den übrigen Formeln ist i_0(g)>0, und wegen (ii) werden nur Funktionswerte U(g,x\') mit x\'0 gilt.
Die Funktion e, die nun definiert wird, liefert in gewissem Sinne eine Parameterdarstellung der Funktion U.
e([0,g,x])=[a,g,x], wobei a=fdef(s(x), wenn g=[0\,0];l(x), wenn g=[0\,1];0, wenn (g,x)\in\ W),
e([1, q_1, q_2])=[u+v, [1,a,b],x], wenn e(q_1)=[u,a,x] und e(q_2)=[v,b,x],
e([2, q_1, q_2])=[v, [2,a,b],x], wenn e(q_1)=[v,a,u] und e(q_2)=[u,b,x],
e([3, q_1, q_2])=[v, [3,a],z+1], wenn e(q_1)=[v,a,u] und e(q_2)=[u,[3,a],z],
e(q)=[1,0] für alle anderen Argumente q.
Wir möchten nun die drei wichtigen und folgenschweren Aussagen beweisen:
\big\ A. Eine einstellige Funktion f ist genau dann primitiv rekursiv,
\big\ wenn es ein g gibt mit f(x)=U(g,x) für alle x.
\big\ B. Es gilt y=U(g,x) <=> es gibt ein q mit e(q)=[y,g,x].
\big\ C. e ist primitiv rekursiv.
\big\ Beweis von A:
Diese Aussage folgt unmittelbar aus den Ergebnissen von § 4.
Wenn f eine beliebige einstellige primitiv rekursive Funktion ist, dann ist sie eine der Anfangsfunktionen s und l oder kann aus ihnen durch Addition, Verkettung und Iteration gewonnen werden.
Für die Anfangsfunktionen s und l kann man g=[0,0] bzw. g=[0,1] nehmen.
Die übrigen Funktionen kann man nach steigendem Kompliziertheitsgrad (kurz: Grad) anordnen.
Wir legen fest, daß s und l den Grad 0 haben, und wenn n das Maximum der Grade von f_1 und f_2 ist, dann haben f_1+f_2 und f_1\circ\ f_2 den Grad n+1, ferner hat auch f^\# den Grad n+1 für eine Funktion f vom Grad n.
\small\ Man sollte beachten, daß der Begriff "Grad" sich auf die Art und Weise bezieht, wie die Funktion dargestellt ist, nicht auf die Funktion selbst.
\small\ Wenn man ein und dieselbe Funktion auf unterschiedliche Weisen darstellt, dann könnte der Grad dieser Darstellungen unterschiedlich sein, wie z. B. bei
\small\ sg=(s\circ\ l)^\#, dies hat Grad 2, und sg\circ\ sg ist ebenfalls die Signum\-Funktion, aber diese Darstellung besitzt den Grad 3.
Wir betrachten eine Funktion f mit einer Darstellung vom Grad n>0 und dürfen annehmen, daß Behauptung A. für alle Funktionen vom Grad < n bereits bewiesen ist \(starkes Induktionsprinzip\).
Wenn f=f_1+f_2 eine Summe oder f=f_1\circ\ f_2 eine Verkettung ist, dann sind f_1 und f_2 von kleinerem Grad als n, und f_1(x)=U(g_1, x) und f_2(x)=U(g_2, x) ist bereits bewiesen.
Dann erfüllt g=[1, g_1, g_2] im ersten und g=[2, g_1, g_2] im zweiten Fall das Verlangte.
Bei einer Iteration f=h^\# hat h einen kleineren Grad, und h(x)=U(g_1, x) ist schon bewiesen. Mit Induktion über x kann man dann f(x)=U(g,x) für g=[3,g_1] beweisen:
Für dieses g gilt (g,0)\in\ W, daraus folgt U(g,0)=0=f(0), der Induktionsanfang.
f(x+1)=h(f(x))=h(U(g,x))=U(g_1\,U(g,x))=U(g,x+1) ist der Induktionsschritt.
Umgekehrt, für ein beliebiges g ist die Funktion f(x)=U(g,x) primitiv rekursiv.
Für g=[0,0] und g=[0,1] ergibt U(g,x) die primitiv rekursiven Funktionen s(x) und l(x).
Wenn alle Funktionen U(g\',x) mit g\'":
Die Behauptung ist für g=[0,0] und g=[0,1] und für alle (g,x)\in\ W richtig, weil man q=[0,g,x] nehmen kann.
Sonst hat g die Form [1, g_1, g_2], [2, g_1, g_2] oder [3, g_1], wobei im dritten Fall x>0 ist.
Man darf als Induktionsannahme voraussetzen, daß für die Argumente
g_1\,g_2"\-Richtung von Aussage B. auch für dasselbe g, jedoch mit x-1 anstelle von x voraussetzen.
Es ist also eine doppelte Induktion über die Paare (g,x):
die Hauptinduktion ist über die Variable g, und um die Induktionsbehauptung für g zu beweisen, wird neben anderem eine weitere Induktion bezüglich x durchgeführt.
Im ersten Fall g=[1\,g_1\,g_2] gibt es q_1 und q_2 mit
e(q_1)=[U(g_1, x), g_1, x] und e(q_2)=[U(g_2, x), g_2, x].
Dann haben e(q_1) und e(q_2) die Form [u,a,x] und [v,b,x] mit a=g_1, b=g_2, u=U(a\,x), v=U(b,x), und für q=[1, q_1, q_2] ist dann e(q)=[u+v,[1,a,b],x].
Wegen [1,a,b]=g folgt y=U(g,x)=U(a,x)+U(b,x)=u+v und damit e(q)=[y,g,x].
Im zweiten Fall g=[2, g_1, g_2] setzt man u=U(g_2, x),
es gibt q_1 und q_2 mit e(q_1)=[U(g_1,u), g_1, u] und e(q_2)=[u,g_2, x].
Dann haben e(q_1) und e(q_2) die Form [v,a,u] und [u,b,x] mit
a=g_1\., b=g_2\., u=U(b,x), v=U(a,U(b,x))=U(g,x)=y,
und für q=[2, q_1, q_2] ist somit e(q)=[y,g,x].
Im dritten Fall g=[3, g_1], x>0 setzt man u=U(g,x-1),
und es gibt q_1 und q_2 mit e(q_1)=[U(g_1, u), g_1, u] und e(q_2)=[u, g, x-1].
Dies hat die Form [v,a,u] und [u,[3,a],z] mit z=x-1, a=g_1, v=U(a,u),
für q=[3, q_1, q_2] ist dann e(q)=[v,[3,a],z+1]=[v,g,x].
Wegen g=[3, g_1] gilt v=U(g_1, u)=U(g_1, U(g,x-1))=U(g,x)=y,
also e(q)=[y,g,x], was zu beweisen war.
"<==":
Die Voraussetzung ist nun e(q)=[y,g,x].
Man muß nun überlegen, mit welcher Formelzeile e(q) definiert ist.
Für g=[0,0] und g=[0,1] und (g,x)\in\ W kann das nur die erste oder die letzte Formel sein, weil bei den übrigen Formeln das zweite Glied g des Ergebnistripels die Bedingung i_0(g)=1,2 oder 3 erfüllt, und das Paar (g,x)\notin\ W ist.
Für die erste Formel ist das erste Glied y des Tripels e(q) gleich a, dieser Wert stimmt für g=[0,0] und g=[0,1] und (g,x)\in\ W mit U(g,x) überein.
Für die letzte Formel ist e(q)=[1,0], und es wird 1=U(0,0), also 1=s(0) behauptet, was richtig ist.
Für g!=[0,0], g!=[0,1] und (g,x)\notin\ W kommt nur die zweite, dritte oder vierte Definitionsformel der Funktion e in Frage, und zwar genau eine davon.
Es gilt i_0(q)=i_0(g), dieser Wert ist gleich 1,2 oder 3.
Mit Induktion darf man annehmen, daß die Behauptung für Argumente < q bereits bewiesen ist, und dann ist im ersten Fall
e(q_1)=[U(a,x),a,x] und e(q_2)=[U(b,x),b,x], es folgt y=U(a,x)+U(b,x)=U(g,x),
und im zweiten Fall e(q_1)=[U(a,u),a,u] und e(q_2)=[u,b,x] mit u=U(b,x),
es folgt y=U(a,u)=U(a,U(b,x))=U(g,x).
Im dritten Fall ist [3,a]=g, e(q_1)=[U(a,u),a,u] und e(q_2)=[u,g,x-1] mit u=U(g,x-1).
Das erste Glied von e(q)=[y,g,x] ist dann y=U(a,u)=U(a,U(g,x-1)), und mit Hilfe der Gleichung g=[3,a] ist dies nach der Definition von U gleich U(g,x), was zu beweisen war.
\big\ Beweis von C:
Man muß nur die Definition der Funktion e so umschreiben, daß die primitive Rekursivität dieser Funktion erkennbar wird.
Diese Umschreibung ist ungleich komplizierter als die Definition selbst, aber das ist unwichtig, entscheidend ist, daß sie überhaupt möglich ist.
Zunächst ist der Anfangswert e(0) durch e(0)=[1,0] festgelegt.
Für q>0 muß man mit Hilfe primitiv rekursiver Funktionen einen Test durchführen, ob q in der Form [0,g,x] mit (g=[0,0] oder g=[0,1] oder (g,x)\in\ W)
oder als [1, q_1, q_2], [2, q_1, q_2] oder [3, q_1, q_2] dargestellt werden kann.
Dieser Test hat z. B. im Fall [2, q_1, q_2] die Form q=[2,i_1(q), i_2(q)], die übrigen Fälle sind analog.
\small\ Wir wollen die Werte logischer Ausdrücke wie u=v und u!=v mit ihren Wahrheitswerten
\(0 für falsch und 1 für wahr\) identifizieren, die Formeln
\small\ (u=v)=If(u -\void* v,0\,If(v -\void* u,0,1)) und
\small\ (u!=v)=If(u -\void* v,1\,If(v -\void* u,1,0)) zeigen, daß dies durch primitiv rekursive Funktionen ausgedrückt werden kann.
\small\ Somit kann man z. B. wie gewohnt If(x=y,u,v) schreiben, wobei x,y,u,v beliebige einfache oder zusammengesetzte Ausdrücke sind.
\small\ Ferner sind die logischen Verknüpfungen a\and\ b=If(a,b,0) und a\or\ b=If(a,1,b) ebenfalls primitiv rekursiv.
Wenn der Test fehlschlägt, dann ist e(q)=[1,0]=[U(0,0),0].
Sonst ergibt sich e(q) aus einer der Zeilen 1\-4 der Definition von e, aber nur, wenn die angegebenen Bedingungen erfüllt sind, sonst wird e(q)=[1,0] gesetzt.
Falls z. B. die dritte Zeile
e([2\,q_1\,q_2])=[v\,[2\,a\,b]\,x], wenn e(q_1)=[v,a,u] und e(q_2)=[u,b,x]
herangezogen werden muß, weil q die Form [2, q_1, q_2] hat, dann ist in diesem Unterfall die Funktion e(q) gleich
e(q)=If(i_2(e(q_1))=i_0(e(q_2)),[i_0(e(q_1)),[2,i_1(e(q_1)),i_1(e(q_2))],i_2(e(q_1))],[1,0]).
Hier muß man sich noch q_1=i_1(q) und q_2=i_2(q) eingesetzt denken.
Insgesamt erhält man, wenn man die Verzweigung in die vier Unterfälle (der erste Unterfall hat drei weitere Unterfälle) und in den Sonst\-Fall mit Hilfe von If\-Funktionen und logischen Bedingungen ausdrückt, eine Gleichung der Form e(q)=H(q,e(i_1(q)),e(i_2(q))), in der H eine primitiv rekursive Funktion ist, auch wenn sie eine unglaublich komplizierte Gestalt hat.
Wir erhöhen q um 1 und schreiben die Gleichung als
e(q+1)=H(q+1,e(i_1(q+1)),e(i_2(q+1))).
Wegen i_1(q+1)<=q und i_2(q+1)<=q hat diese Vorschrift zusammen mit der Anfangsbedingung e(0)=[1,0] die Form einer Verlaufsrekursion, die in § 3 betrachtet wurde. Nach dem Ergebnis dieses Abschnitts ist e primitiv rekursiv, und C. ist bewiesen.
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*
Die in A. ausgesprochene Eigenschaft der zweistelligen Funktion U drückt man so aus, daß man sagt, U ist eine array(universelle Funktion)__ für die Klasse der einstelligen primitiv rekursiven Funktionen.
Wegen B. gilt U(g,x)=i_0(min {q : i_1(e(q))=g \and i_2(e(q))=x}),
also ist nach der Definition in § 5 U allgemein rekursiv.
Jedoch ist U nicht primitiv rekursiv, dies ist sehr einfach zu beweisen.
Sonst wäre die Funktion h(x)=U(x,x)+1 auch primitiv rekursiv und könnte in der Form h(x)=U(g,x) dargestellt werden, das ergibt für x=g einen Widerspruch.
Die gleiche Überlegung zeigt auch, daß es für die Klasse der allgemein rekursiven Funktionen keine allgemein rekursive universelle Funktion gibt, auch dieses Resultat ist, obwohl trivial, sehr wichtig.
§ 7. Parametrisierung rekursiver Funktionen
\big\ Satz:
Es sei f eine n\-stellige rekursive Funktion, die von der nirgends definierten Funktion verschieden ist. Dann gibt es einstellige primitiv rekursive Funktionen p_0(t)\,p_1(t)\,...\,p_n(t), so daß gilt:
y=f(x_1\,...\,x_n) ist definiert <=> es gibt ein t mit p_0(t)=y, p_j(t)=x_j (j=1,...,n).
Beweis:
Für Funktionen f mit dieser Eigenschaft stimmt also die Menge der (n+1)\-Tupel
(f(x_1\,...\,x_n)\,x_1\,...\,x_n), die man den Graphen der Funktion f nennt, mit der Menge der (n+1)\-Tupel (p_0(t)\,p_1(t)\,...\,p_n(t)) überein.
Wir wollen solche Funktionen und auch die nirgends definierte Funktion darstellbar__ nennen und möchten beweisen, daß jede rekursive Funktion darstellbar ist.
Dazu muß man die Regeln 1.-4. aus § 5 nacheinander abhandeln.
Ist eine der dabei beteiligten Funktionen nirgends definiert, dann ist auch die Ergebnisfunktion nirgends definiert, und es ist nichts weiter zu beweisen, daher wird dieser Fall im Folgenden nicht erwähnt.
\big\ (a)\normal Wenn f gemäß Regel 1. primitiv rekursiv ist, dann ist f darstellbar.
Wie in § 3 führen wir eine Codierung von Listen ein und setzen
t=c(x_1\,c(x_2\,...\,c(x_n\,0)...)), dann kann man aus t die Argumente x_1\,...\,x_n eindeutig rekonstruieren, die Funktionen, die dies tun, nennt man p_1(t)\,...\,p_n(t).
Diese Funktionen und auch p_0(t)=f(p_1(t)\,...\,p_n(t)) sind primitiv rekursiv. Sie haben die im Satz geforderten Eigenschaften, weil die Liste p_1(t)\,...\,p_n(t) jedes beliebige n\-Tupel x_1\,...\,x_n ergeben kann. Also ist f darstellbar.
\big\ (b)\normal Wenn f und g_1\,...\,g_n darstellbar sind, dann ist auch die nach Regel 2. gebildete Verkettung f ° (g_1\,...\,g_n) darstellbar.
Wenn diese Verkettung nirgends definiert ist, ist nichts zu beweisen.
Sonst gibt es Parameterdarstellungen (q_0(t)\,...\,q_n(t)) für f und (r_j0(t)\,...\,r_jm(t)) für g_j\..
Man kann, ähnlich wie in (a), primitiv rekursive Funktionen p_0\,...\,p_m wählen, so daß jedes (m+1)\-Tupel s_0\,...\,s_m in der Form p_0(t)\,...\,p_m(t) dargestellt werden kann.
Wenn t die Gleichungen q_j(p_0(t))=r_j0(p_j(t)) für j=1,...,n und
r_1k(p_1(t))=r_2k(p_2(t))=...\ =r_nk(p_n(t)) für k=1,...,m erfüllt, dann setzt man u_0(t)=q_0(t) und u_k(t) gleich dem gemeinsamen Wert von r_jk(p_j(t)) für j=1,...,n.
Für alle t, die die angeführten Bedingungen nicht erfüllen, setzt man
(u_0(t)\,...\,u_m(t)) gleich ein und demselben (m+1)\-Tupel (v_0\,...\,v_m), wobei v_1\,...\,v_m eine beliebige Argumentliste ist, für die das Ergebnis der Verkettung definiert ist und den Wert v_0 ergibt.
Dann liefert (u_0(t)\,...\,u_m(t)) offensichtlich die verlangte Parameterdarstellung der verketteten Funktion f ° (g_1\,...\,g_n), und sie kann mit primitiv rekursiven Funktionen ausgedrückt werden.
\big\ (c)\normal Wenn f aus g und h durch Rekursion nach Regel 3. aus darstellbaren Funktionen g und h gebildet wird, dann ist auch f darstellbar.
Es gibt Parameterdarstellungen (q_0(t)\,...\,q_n(t)) von g und
(r_0(t)\,...\,r_(n+2)(t)) von h.
Die Gleichung z=f(x,y), wobei x eine Abkürzung für die Liste x_1\,...\,x_n ist, bedeutet, daß es eine Folge u_0\,...\,u_y=z mit
u_0=g(x) und u_(j)=h(x,j-1,u_(j-1)) für j=1,...,y gibt.
Zu diesen y+1 Gleichungen gibt es eine Folge von Parametern aus der Darstellung der Funktionen g und h, diese kann man in eine Liste
t=c(t_0\,c(t_1\,...\,c(t_y\,0)...)) codieren und mit Hilfe der Funktion Index(t,j) aus § 3 daraus das j\-te Element extrahieren, das im Falle j=0 für die Gleichung u_0=g(x) und im Falle j>0 für die Gleichung u_j=h(x,j-1,u_(j-1)) zuständig ist.
Wenn es zu diesem t ein n\-Tupel (x_1\,...\,x_n) gibt, das die Bedingungen
r_k(Index(t,j))=x_k für j=1,...,y und k=1,...,n und
r_0(Index(t,j+1))=r_(n+2)(Index(t,j)) für j=0,...,y-1
erfüllt, dann setzt man w_0(t)=r_0(Index(t,y)) und w_k(t)=x_k fest.
Die Überprüfung der angegebenen Bedingungen kann man mit Hilfe der Signum\-Funktion und des Summenzeichens durchführen, in § 2 wurde bewiesen, daß dies auf primitiv rekursive Funktionen führt.
Wenn die Prüfungen fehlschlagen, dann setzt man wie in (b) das (m+1)\-Tupel (w_0(t)\,...\,w_m(t)) gleich einem Standardwert, der Element des Graphen von f ist, welchen Wert man nimmt, ist völlig gleichgültig.
\big\ (d)\normal Wenn f aus g durch Minimalisierung nach Regel 4. aus einer darstellbaren Funktion g gebildet wird, dann ist auch f darstellbar.
Es sei (q_0(t)\,...\,q_(n+1)(t)) eine Parameterdarstellung von g.
\(21.1.2019: Offenbar wollte ich hier noch weitermachen und sehe gerade, daß das noch offen ist.
Nachdem soviel Zeit vergangen ist, kann ich diese Lücke leider nicht mehr schließen).
§ 8: Ausblick
Aus den Ergebnissen von § 7 folgt, daß jede rekursive Funktion f, die überall definiert ist, allgemein rekursiv ist.
Dies ist durchaus nicht trivial und verdient hervorgehoben zu werden.
Denn es gibt eine Parametrisierung (q_0(t)\,...\,q_n(t)) array(für den Graphen von f.)
Weil f überall definiert ist, kann man zu jeder Argumentliste x_1\,...\,x_n ein minimales t mit q_j(t)=x_j finden, und dann ist f(x_1\,...\,x_n)=q_0(t).
Kurz formuliert: f(x)=q_0(min menge(t | q_j(t)=x_j für j=1,...,n))
ist allgemein rekursiv, denn die Zwischenfunktionen, die vorkommen, sind alle primitiv rekursiv und somit überall definiert.
Mit Hilfe der universellen Funktion U aus § 6 kann man ferner beweisen, daß es auch für die Menge der rekursiven Funktionen f(x) eine rekursive universelle Funktion V(g,x) gibt, dies steht im Gegensatz zu der Tatsache aus § 7, daß dies für allgemein rekursive Funktionen nicht möglich ist.
Dies gilt auch für mehrstellige Funktionen, aber weil man den mehrstelligen Fall mit Hilfe der Codierung von n\-Tupeln auf einstellige Funktionen zurückführen kann, beschränken wir uns auf den Fall einstelliger Funktionen f(x).
Nach § 7 gibt es eine primitiv rekursive Parametrisierung q_0(t), q_1(t) für den Graphen von f, und die primitiv rekursive Funktion c(q_0(t),q_1(t)) kann als U(g,t) dargestellt werden.
V(g,x)=l(U(g,min menge(t | r(U(g,t))=x))) ist dann die gewünschte rekursive universelle Funktion, die für ein geeignetes g jede rekursive Funktion f(x) darstellen kann.
Die Gleichung r(U(g,t))=x ermittelt alle t mit q_1(t)=x.
Solche t gibt es nicht, wenn f(x) nicht definiert ist, sonst ergibt aber q_0(t) mit jedem t dieser Art, also auch mit dem minimalen t, den Funktionswert f(x), und dieses q_0(t) ist gleich l(U(g,t)).
Es gibt also eine Abbildung der Menge \IN der natürlichen Zahlen auf die Menge der rekursiven Funktionen, man nennt das auch eine Aufzählung.
Allgemein wird für ein beliebige Menge M mathematischer Objekte eine surjektive Abbildung \f von \IN auf M als Aufzählung von M bezeichnet.
Es gibt eine besondere Eigenschaft, die Aufzählungen besitzen können.
Sie können total__ sein, das bedeutet:
In der Menge M gibt es ein Element o, so daß es für jede rekursive Funktion p(x) eine allgemein rekursive Funktion q(x) gibt mit
\f(q(x))=fdef(\f(p(x)), wenn p(x) definiert ist;o, wenn p(x) nicht definiert ist).
Die Abbildung g \mapsto V(g,.), die der Zahl g\in\IN die Funktion x\mapsto\ V(g,x) zuordnet, definiert eine Aufzählung der Menge der rekursiven Funktionen.
Mit einer leichten Abänderung dieser Aufzählung (Kleenesche Klammer) bewies Kleene (1909-1994) den Satz, daß diese abgeänderte Aufzählung total ist, wobei das Element o die nirgends definierte Funktion ist.
Ich finde, dies ist ein schöner Satz, aber die Eigenschaften totaler Aufzählungen weiter zu verfolgen überschreitet den Rahmen dieses Artikels, daher möchte ich hiermit einen Punkt machen.
Es wäre sehr interessant, die hier untersuchten Eigenschaften rekursiver Funktionen im Zusammenhang mit Algorithmen und Automaten darzustellen.
Dies könnte in einem Fortsetzungsartikel geschehen, wenn jemand sich entschließen könnte, ihn zu schreiben.
\(\endgroup\)
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Informatik: Rekursive Funktionen
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
