Wichtig: lasst euch von der mathematischen Definition nicht einsch\u00fcchtern. Ich versuche in jedem Satz immer die Definition noch zu erkl\u00e4ren. Ansonsten: wer grobe Schnitzer findet: bitte melden!<\/p>\n
Zwei wichtige Themen aus der 2. Kurseinheit behandeln die primitive und die \\(\\mu\\)-Rekursion. Aus der Definition im Kurstext erschlie\u00dft sich mir ihre (und von vielem anderen auch) Bedeutung jedoch nicht sofort. Aber vielleicht stehe ich auch einfach auf dem Schlauch bei diesen Themen. Beide Rekursionen dienen dazu das Repertoire der berechenbaren Funktionen zu vergr\u00f6\u00dfern.<\/p>\n
In Kurseinheit 1 gab es ja bereits eine Liste an berechenbaren Funktionen. All‘ diese konnten mit einer einfachen Registermaschine, welche nur die Grundoperationen (Arithmetische Differenz zu 1, Addition von 1 und Test auf 0) abgebildet werden. Das ist zwar alles sch\u00f6n und gut, aber reicht uns nat\u00fcrlich nicht. Also erweitern wir das Feld der berechenbaren Funktionen mit der Rekursion, denn der Definition nach sind alle primitiv- und \\(\\mu\\)-rekursiven Funktionen berechenbar.<\/p>\n
Was ist also die primitive Rekursion? Die primitiv rekursiven Funktionen entstehen aus den Grundoperationen (die stelle ich gleich vor) und werden mittels Komposition (Hintereinanderausf\u00fchrung) und\/oder der primitiven Rekursion gebildet. Als Grundoperationen haben wir:<\/p>\n
Die konstante Funktion<\/strong>: \\(C^k : \\mathbb{N}^k \\rightarrow \\mathbb{N}\\) mit \\((n_1, …, n_k) \\mapsto c\\) und \\(c \\in \\mathbb{N}\\).<\/p>\n Oder manchmal auch die Nullfunktion<\/strong>\u00a0\\(0^k : \\mathbb{N}^k \\rightarrow \\mathbb{N}\\) mit \\((n_1, …, n_k) \\mapsto 0\\)<\/p>\n Erkl\u00e4rung:\u00a0\\(\\mathbb{N}^k \\rightarrow \\mathbb{N}\\) bedeutet nichts weiter als dass der Definitionsbereich (und damit die Argumente der Funktion) der Bereich der nat\u00fcrlichen Zahlen (eben \\(\\mathbb{N}^k\\)) ist. \\(k\\) bedeutet Stelligkeit (also die Anzahl der Argumente der Funktion, die Argumente selbst sind mit \\((n_1, …, n_k)\\) angegeben). Das Ergebnis der Funktion ist jedoch nur einstellig. Z.B. w\u00e4re \\(f^3 : \\mathbb{N}^3 \\rightarrow \\mathbb{N}\\) mit \\(f(x,y,z) = x + y – z\\) so eine Funktion (nicht f\u00fcr eine konstante Funktion), die\u00a0 drei Argumente entgegen nimmt, aber nur einen Funktionswert (sogenannter Wertebereich) ausgibt.<\/p>\n Die konstante Funktion<\/strong> \\(C^k\\) macht noch viel weniger. Egal wieviel Argumente Du ihr gibst, sie gibt immer nur einen Wert zur\u00fcck. Die Konstante c, welche auch aus dem Bereich \\(\\mathbb{N}\\) kommt. Also z.B. \\(f^4 : \\mathbb{N}^4 \\rightarrow \\mathbb{N}\\) mit \\(f(a,b,c,d) = 5\\). Egal, was die Funktion an Argumenten bekommt, es kommt immer 5 heraus.<\/p>\n Die konstante<\/strong>\u00a0Nullfunktion<\/strong>, welche h\u00e4ufig in den Definitionen f\u00fcr die primitive Rekursion verwendet wird ist auch nur eine konstante Funktion. Nur ist hier \\(c\\) immer einfach nur 0. Mehr nicht. Also nicht verwirren lassen.<\/p>\n Die Projektion<\/strong> auf ein Argument: \\(\\pi^k_i : \\mathbb{N}^k \\rightarrow \\mathbb{N}\\) mit \\((n_1,…,n_k) = n_i\\)<\/p>\n Hier ist die Erkl\u00e4rung offensichtlich. Also \u00fcberspringen wir sie mal. Nein, Scherz. Das muss ich oft genug im Skript lesen und denke mir nur: „Bitte?!“. Manche Dinge sind derart einfach, dass man nicht glaubt sie verstanden zu haben weil man von den ganzen griechischen Buchstaben erschlagen wurde.<\/p>\n Diese Funktion tut nur eines: sie gibt das \\(i-te\\) Argument aus ihrer \\(k\\)-stelligen Argumentliste zur\u00fcck. Das wars. Wirklich. Aber eine Kleinigkeit ist noch hilfreich: Es gibt die einstellige Projektion mit \\(\\pi^1_1(n_1) = n_1\\). Diese nennt man die Identit\u00e4tsfunktion<\/strong> \\(id(x) = x\\). Konkretes Beispiel f\u00fcr beide? Bitte sehr. Projektion: \\(\\pi^4_2(a,b,c,d) = b\\). Identit\u00e4tsfunktion:\u00a0\\(\\pi^1_1(a) = id(a) = a\\).<\/p>\n Die Nachfolgefunktion<\/strong>: \\(Suc : \\mathbb{N} \\rightarrow \\mathbb{N}\\) mit \\(n \\mapsto suc(n) := n+1\\)<\/p>\n Geht kaum einfacher. Was macht die Funktion? Sie gibt zu dem ihr gegebenen Argument einfach nur den Nachfolger zur\u00fcck. Beispiel: \\(f(2) = 3\\). Das war’s.<\/p>\n Was haben die Basis-Funktionen nun mit primitiver Rekursion zu tun? Alle<\/strong> Funktionen, die aus diesen Basisoperationen mittels Komposition (oder Substitution) und Rekursion gebildet werden k\u00f6nnen, werden rekursive Funktionen genannt und sind berechenbar. Diese liegen in \\(\\mathcal{P}\\), dem Bereich der total-rekursiven<\/strong> Funktionen, denn sie decken den vollst\u00e4ndigen Definitionsbereich ab (jedem Wert aus dem Definitionsbereich wird ein Funktionswert zugeordnet, kein Argument bleibt ohne Funktionswert). Zu den partiell-rekursiven Funktionen kommen wir noch.<\/p>\n Beispiel<\/strong>: Wollen wir mal einen Versuch wagen und eine Komposition der Grundoperationen aufstellen und ausrechnen?<\/p>\n Konstante<\/strong> Funktion: \\(c : \\mathbb{N}^2 \\rightarrow \\mathbb{N}\\) mit \\(c(x,y) \\mapsto 4\\).<\/p>\n Projektion<\/strong> \\(\\pi^2_1 : \\mathbb{N}^2 \\rightarrow \\mathbb{N}\\) mit \\(\\pi^2_1 (x,y) \\mapsto x\\)<\/p>\n Nachfolgefunktion<\/strong>: \\(suc : \\mathbb{N} \\rightarrow \\mathbb{N}\\) mit \\(suc(x) \\mapsto x+1\\)<\/p>\n Wir bilden nun aus diesen drei Funktionen eine Komposition<\/a>: \\(\\pi^2_1(x,y)\\circ (c(x,y) \\circ suc(x))\\). D.h. eine Hintereinanderausf\u00fchrung der Funktionen. Es gilt (bitte beim Wikipedia-Link nachschauen) bei der Komposition: \\(g \\circ (f \\circ h) = g(f(h(x)))\\). F\u00fcr unsere Funktionen bedeutet es also: \\(\\pi^2_1(c(suc(x),y),z)\\). Wir setzen unsere Variablen willk\u00fcrlich: \\(x=5\\), \\(y=6\\) und \\(z=7\\). Damit haben wir dann auch gleich etwas, womit wir rechnen k\u00f6nnen: \\(\\pi^2_1(c(suc(5),6),7)\\). Wir beginnen also von Innen nach Au\u00dfen:<\/p>\n \\(suc(5) = 6\\) (unsere Nachfolgefunktion)<\/p>\n \\(c(6,6) = 4\\) (unsere konstante Funktion)<\/p>\n \\(\\pi^2_1(4,7) = 4\\) (unsere Projektion)<\/p>\n Damit ist \\(\\pi^2_1(c(suc(5),6),7) = 4\\).<\/p>\n Nun ist jede Funktion, die wir mit den drei Basisoperationen von oben mittels Komposition (Substitution) und Rekursion abbilden k\u00f6nnen ebenfalls primitiv-rekursiv und damit berechenbar.<\/p>\n Bitte nicht dr\u00fcber hinwegweg lesen. Diese Ausf\u00fchrung wird bei jeder\u00a0Definition der primitiven Rekursion verwendet (manchmal in umgekehrter Reihenfolge, aber der Sinn und Zweck sind gleich). Erst wenn man die Funktion in das Rekursionsschema hat \u00fcberf\u00fchren k\u00f6nnen, ist sie wirklich primitiv rekursiv. Wir werden also mit folgenden Dingen gequ\u00e4lt:<\/p>\n 1. Komposition\/Einsetzung\/Substitution <\/strong>formal: haben wir hier z.B. eine Funktion \\(h\\) (k-stellig mit \\(\\mathbb{N^k}\\)) und mehrere Funktionen \\(g_1,…,g_k\\) (alle n-stellig mit \\(\\mathbb{N^n}\\))\u00a0und sind diese primitiv-rekursiv, so ist auch \\(h(g_1(x_1,…,x_n), …, g_k(x_1,…,x_n))\\) primitiv-rekursiv.<\/p>\n Das bedeutet: nichts weiter als eine Einsetzung. Zun\u00e4chst haben wir in der Funktion \\(h\\) genau \\(k\\) Parameter (Stelligkeit, siehe oben) aus dem Bereich der nat\u00fcrlichen Zahlen \\(\\mathbb{N}\\). Und dann noch \u00a0\\(k\\) Funktionen \\(g\\) (es k\u00f6nnen auch mehr sein, aber wir brauchen nur \\(k\\)), die selbst \\(n\\) Parameter verwenden, welche oben mit \\((x_1,…,x_n)\\) beschrieben sind. Nun m\u00f6chten wir die (nicht beschriebenen) Parameter der Funktion \\(h\\) einfach durch ausgerechnete Funktionswerte der Funktionen \\(g\\) ersetzen. Das ist alles, was die Substitution macht.<\/p>\n Beispiel<\/strong>:<\/p>\n Funktion: \\(h : \\mathbb{N}^2 \\rightarrow \\mathbb{N}\\) mit \\(h(x,y) \\mapsto x*y\\)<\/p>\n Funktion: \\(g : \\mathbb{N}^3 \\rightarrow \\mathbb{N}\\) mit \\(g(a,b,x) \\mapsto a+b+c\\)<\/p>\n Wir f\u00fchren nun die Substitution der Parameter von \\(h\\) mit den Funktionswerten von \\(g\\) durch: \\(h(x,y) = h(g(a,b,c),g(a,b,c))\\). Wir setzen willk\u00fcrlich \\(a = b = c = 2\\) und haben somit: \\(h(g(2,2,2),g(2,2,2))\\). Ausrechnen von Innen nach Au\u00dfen:\u00a0\\(h(6,6) = 36\\). That’s it!<\/p>\n 2. Rekursionsschema<\/strong> formal: dieser Teil wird dazu verwendet um zu garantieren, dass auch die neue Funktion, welche durch primitive Rekursion gebildet wurde bzgl. primitiver Rekursion abgeschlossen und ist nicht aus dem Rahmen f\u00e4llt. Es besagt, dass eine Funktion \\(f\\) nach dem Schema der primitiven Rekursion aufgebaut ist, wen sie folgende Form besitzt:<\/p>\n \\(f(m,n)=\\begin{cases} g(n), & \\mbox{falls }m = 0 \\\\ h(f(m-1,n),m-1,n), & \\mbox{falls }m > 0 \\\\\\end{cases}\\)<\/p>\n Was bedeutet das nun f\u00fcr uns? Wir haben hier zwei Fallunterscheidungen: einmal wenn ein Parameter = 0 (m=0) ist, so bedarf es keiner Rekursion und wird durch eine Funktion \\(g(n)\\) abgehandelt. Ist jedoch \\(m > 0\\), m\u00fcssen wir einen zweiten Fall betrachten. Hier erfolgt die Rekursion, welche die Funktion \\(f\\) einfach nur mit dem n\u00e4chst-kleineren Parameter \\(m-1\\) aufruft. Am Ende wird \u00a0\\(m=0\\) und wir k\u00f6nnen unser \\(g(n)\\) f\u00fcr diesen Fall verwenden und schlie\u00dfen die Rekursion damit ab.<\/p>\n H\u00e4ufig wird auch folgende Definition verwendet:<\/p>\n (R1) \\(f(0,x_1,…,x_n) = g(x_1,…,x_n)\\)<\/p>\n Bedeutet nichts anderes, als unser \\(g\\) von oben. Nur dass das etwas allgemeiner formuliert und die Parameterbeschr\u00e4nkung abgehoben wurde.<\/p>\n (R2) \\(f(m+1,x_1,…,x_n) = h(f(m,x_1,…,x_n),m,x_1,…x_n)\\)<\/p>\n Auch das ist nicht weit weg von unserer Fallunterscheidung. Unsere Funktion beginnt mit dem Parameter \\(m+1\\), das ist das was eig. unsere Schleifenvariable ist. Diese wird dann im n\u00e4chsten Durchlauf dekrementiert und die Funktion ruft sich mit diesem dekrementierten Wert so lange selbst auf, bis \\(m=0\\) ist und wir unser oben definiertes \\(g\\) verwenden k\u00f6nnen. In manchen Definitionen wird einfach nur \\(m\\) in \\(f\\) verwendet und in \\(h\\) steht dann \\(m-1\\).<\/p>\n Hier w\u00e4re ein Beispiel nicht schlecht, oder? Versuchen wir es doch mal mit der Addition<\/strong> und schauen ob sie aus der Klasse der primitiv-rekursiven Funktionen ist. Also los geht’s:<\/p>\n Um zu beweisen, dass eine Funktion primitiv rekursiv ist muss man diese mit den obigen Grundoperationen definieren und in das Rekursionsschema pressen k\u00f6nnen. Und zwar f\u00fcr alle F\u00e4lle aus den nat\u00fcrlichen Zahlen. Hier sei die 0 vor allem zu beachten, denn die wird gerne mal vergessen.\u00a0Im Endeffekt ist die Addition ja nur \\(add(m,n) = m+n\\). Um zu zeigen, dass sie primitiv rekursiv ist m\u00fcssen wir sie nun mit den oben definierten Grundoperationen abbilden und sie ins Rekursionsschema pressen. Probieren wir es einfach.<\/p>\n 1. Fall: Addition von 0 + n. Bedeutet: \\(add(0,n)=0+n = n\\). Das bilden wir ab mit der Projektion: \\(\\pi^2_2 : \\mathbb{N}^2 \\rightarrow \\mathbb{N}\\) mit \\(\\pi^2_2 (0,n) \\mapsto n\\). \u00a0Aufgeschrieben bedeutet dies: \\(add(0,n)=\\pi^2_2 (0,n)=n\\). Damit wir unser \\(g(n)\\) aus dem Rekursionsschema von oben schon erschlagen:<\/p>\n\\(add(m,n)=\\begin{cases} g(n) = \\pi^2_2 (0,n), & \\mbox{falls }m = 0 \\\\ …, & \\mbox{falls }m > 0 \\\\\\end{cases}\\)\n Allgemein ausgedr\u00fcckt (wir wollen uns ja an die Definitionen aus dem Skript halten) pressen wir das nun in unsere Definition von \\(g\\) aus (R1):<\/p>\n\\(f(0,x_1,…,x_n) = add(0,n)\\)\n\\(g(x_1,…,x_n)=g(n)=\\pi^2_2 (0,n)=n\\)\n Und somit<\/p>\n (R1) \\(add(0,n)=g(n)=\\pi^2_2 (0,n)=n\\)<\/p>\n Passt also in den ersten Teil des Schemas.<\/p>\n 2. Fall: Addition von m + n: Bedeutet: \\(add(m,n) )= m+n\\). Das ist etwas schwieriger. Hier bedienen wir uns der primitiven Rekursion und der Nachfolgefunktion \\(suc\\): \\(add(m+1,n) = suc(add(m,n))\\) (Achtung: die Funktion ist noch nicht in der geforderten Form f\u00fcr den 2. Fall um die \u00dcbersicht zu wahren). Noch nicht so ganz einleuchtend, oder? Vor allem nicht, wie wir drauf gekommen sind. Nehmen wir einen ganz einfachen Fall mit echten Zahlen.<\/p>\n Wollen wir z.B. 1 + 5 addieren, so f\u00e4llt uns schnell ein, dass wir uns doch einfach einmal der Nachfolgefunktion bedienen k\u00f6nnen: \\(add(1,5) = suc(add(0,5))\\) (nun haben wir Innen den 1. Fall von oben, wo die 0 addiert wird und wir verwenden die dort f\u00fcr diesen Fall definierte Projektion, unser \\(g(n)\\) auf das zweite Argument) \\(=suc(\\pi^2_2(0,5)) = suc(5) = 6\\). Schnell sollte einleuchten, dass wir uns einfach beliebig oft der Nachfolgefunktion bedienen d\u00fcrfen, abh\u00e4ngig davon was wir addieren. Wir k\u00f6nnen hier aber zun\u00e4chst nur die 1 addieren. Um auch mehr als die 1 addieren zu k\u00f6nnen, m\u00fcssen wir die Funktion so definieren, dass sie am Ende auf unser \\(g(n)\\) Innen zur\u00fcckgef\u00fchrt, welches dann mit \\(suc(x)\\) ausgerechnet werden kann.\u00a0Wie w\u00fcrde unser\u00a0\\(add(2,5)\\) denn aussehen? So: \\(suc(suc(\\pi^2_2(0,5))) = suc(suc(5))\\). L\u00f6sen wir das auf: \\(suc(suc(5)) = suc(6) = 7\\). Und \\(add(3,5)\\)? Genau!\u00a0\\(suc(suc(suc(\\pi^2_2(0,5)))) = suc(suc(suc(5))) = 8\\).<\/p>\n Das ist aber noch nicht die Rekursion, denn eine Rekursion ist der Aufruf einer Funktion durch sich selbst. Und vor allem ist das ja auch noch nicht in der streng geforderten Form! Wir k\u00f6nnen ja nicht f\u00fcr jeden \\(n\\) aus \\(\\mathbb{N}\\) tausende von \\(suc\\) angeben. Also muss unser \\(add\\) rekursiv durch sich selbst definiert werden (was ja am Ende sowieso auf ein einzelnes \\(suc\\) zur\u00fcckf\u00fchrt). Probieren wir also das Beispiel mit den Zahlen \\((3,5)\\) von oben und arbeiten mit Rekursion statt nur mit tausenden von \\(suc\\):<\/p>\n\\(\\begin{array} {lcl} add(3,5)&=& suc(add(2,5))\\\\&=& suc(suc(add(1,5)))\\\\&=&suc(suc(suc(add(0,5))))\\\\&=&suc(suc(suc(\\pi^2_2(0,5))))\\\\&=&suc(suc(suc(5)))\\\\&=&suc(suc(6))\\\\&=&suc(7)\\\\&=&8\\end{array}\\)\n Damit entspricht das genau dem, was wir mit\u00a0\\(add(m+1,n) = suc(add(m,n))\\) bereits rekursiv definiert haben. F\u00fcr die einfache Fallunterscheidung nehmen wir dann \\(add(m,n) = suc(add(m-1,n))\\), was ja das Selbe ist. F\u00fcr die allgemeinere Definition aus (R2) ist unsere Definition jedoch goldrichtig.<\/p>\n Ab damit in die Fallunterscheidung und wir haben unser \\(h\\) gefunden:<\/p>\n\\(add(m,n)=\\begin{cases} g(n)=\\pi^2_2 (0,n), & \\mbox{falls }m=0 \\\\ suc(\\pi^3_1 (add(m-1,n),m-1,n)) & \\mbox{falls }m > 0 \\\\\\end{cases}\\)\n Wie versprochen werden wir auch hier allgemeiner und pressen das in unsere Definition der Rekursion f\u00fcr (R2):<\/p>\n (R2) \\(f(m+1,x_1,…,x_n)=add(m+1,n)\\)<\/p>\n\\(h(f(m,x_1,…,x_n),m,x_1,…x_n) = suc(\\pi^3_1(add(m,n),m,n))\\)\n Und somit<\/p>\n (R2) \\(add(m+1,n) = suc(\\pi^3_1(add(m,n),m,n))\\)<\/p>\n Und das passt auch in den zweiten Teil des Schemas.<\/p>\n Nehmen wir Papier und Stift und rechnen damit ein konkretes Beispiel durch:<\/p>\n Beispiel<\/strong>: \\(add(3,4)\\)<\/p>\n Mit unserer Definition der Addition von oben \u00a0\\(add(m+1,n)=suc(\\pi^3_1 (add(m,n),m,n))\\)\u00a0k\u00f6nnen wir das nun rekursiv aufl\u00f6sen:<\/p>\n <\/p>\n\\(\\begin{array} {lcl} add(3,4)&=& suc(\\pi^3_1 (add(2,4),2,4))\\\\&{}&\\text{(aufloesen von add(2,4))}\\\\&=& suc(\\pi^3_1 (suc(\\pi^3_1(add(1,4),1,4),2,4)))\\\\&{}&\\text{(aufloesen von add(1,4))}\\\\&=&suc(\\pi^3_1 (suc(\\pi^3_1(suc(\\pi^3_1(add(0,4),0,4),1,4),2,4))))\\\\&{}&\\text{(aufloesen von add(0,4))}\\\\&=&suc(\\pi^3_1 (suc(\\pi^3_1(suc(\\pi^3_1(\\pi^2_2(0,4),0,4),1,4),2,4))))\\\\&{}&\\text{(aufloesen von }\\pi^2_2(0,4))\\\\&=&suc(\\pi^3_1 (suc(\\pi^3_1(suc(\\pi^3_1(4,0,4),1,4),2,4)))\\\\&{}&\\text{(aufloesen von }\\pi^3_1(4,0,4))\\\\&=&suc(\\pi^3_1 (suc(\\pi^3_1(suc(4),1,4),2,4)))\\\\&{}&\\text{(ausrechnen von } suc(4))\\\\&=&suc(\\pi^3_1 (suc(\\pi^3_1(5,1,4),2,4)))\\\\&{}&\\text{(aufloesen von }\\pi^3_1(5,1,4))\\\\&=&suc(\\pi^3_1 (suc(5),2,4)))\\\\&{}&\\text{(ausrechnen von } suc(5))\\\\&=&suc(\\pi^3_1 (6,2,4))\\\\&{}&\\text{(aufloesen von }\\pi^3_1 (6,2,4))\\\\&=&suc(6)\\\\&{}&\\text{(ausrechnen von } suc (6))\\\\&=&7\\end{array}\\)\n <\/p>\n Damit haben wir die Addition primitiv rekursiv definiert, die Addition ist also ein Teil der primitiv-rekursiven Funktionen und damit berechenbar. Sicher wollt ihr den ganzen Spa\u00df auch mit der Multiplikation machen. Probiert es mal. Ihr werden sehen, dass es schnell un\u00fcbersichtlich wird wenn ihr nur die 3 Grundoperationen von oben benutzt. Irgendwas stimmt hier aber noch nicht ganz, oder? Euch schwirrt bestimmt noch etwas aus der 1. Kurseinheit im Kopf rum, was wir gemacht haben. Genau!\u00a0Erinnert ihr euch zuf\u00e4llig noch an die normalen und verallgemeinerten Registermaschinen aus der 1. Kurseinheit?<\/p>\n Alle Operationen, die wir mit normalen Registermaschinen abbilden und damit ihre Berechenbarkeit beweisen konnten, konnten wir fortan in unseren verallgemeinerten Registermaschinen ohne Beweis benutzen! Das Gleiche k\u00f6nnen wir hier auch tun. Wir k\u00f6nnen jetzt die Multiplikation primitiv-rekursiv definieren und hierf\u00fcr die Addition verwenden, deren Berechenbarkeit wir soeben nachgewiesen haben. Weil wir dann damit nach dem Rekursionsschema die Multiplikation mittels der Addition definieren konnten, die Addition durch die 3 Grundoperationen definiert wurde folgt daraus, dass die Multiplikation auch berechenbar ist.<\/p>\n Gerne kann ich den L\u00f6sungsweg f\u00fcr die Multiplikation dann auch posten wenn gew\u00fcnscht. Versucht es aber erstmal selbst.<\/p>\n Aber auch die primitive Rekursion hat ihre Grenzen. Genau f\u00fcr diese wurde die Ackermann-Funktion erfunden. Man vermutete vor einiger Zeit, dass man mit der Klasse der primitiv Rekursiven Funktionen alle berechenbaren Funktionen erschlagen h\u00e4tte. Das wurde jedoch von der Ackermann-Funktion, die eigens daf\u00fcr entwickelt wurde, widerlegt. Das Repertoire an Grundoperationen war schlicht und ergreifend nicht m\u00e4chtig genug um diese berechenbare, aber nicht primitiv rekursive Funktion abzubilden.<\/p>\n Erst mit der Einf\u00fchrung des\u00a0\\(\\mu\\)-Operators und der sogenannten\u00a0\\(\\mu\\)-Rekursion hat man diese Klasse so erweitern k\u00f6nnen, dass die Ackermann-Funktion da hinein f\u00e4llt. Man geht in der Church’schen These davon aus, dass sich mit der\u00a0\\(\\mu\\)-Rekursion nun alle berechenbaren Funktionen abbilden lassen, die (Turing-)berechenbar sind. Aber da k\u00fcmmern wir uns dann im n\u00e4chsten Beitrag im Rahmen der\u00a0\\(\\mu\\)-Rekursion drum.<\/p>\n Eine wichtige Eigenschaft der rekursiven Funktionen ist derer Zusammenhang mit der LOOP-Berechenbarkeit. Jedes LOOP-Programm l\u00e4sst sich primitiv rekursiv darstellen und umgekehrt. Im Gegensatz zu GOTO (Registermaschinen) und WHILE (unsere\u00a0\\(\\mu\\)-Rekursion) terminieren LOOP-Programme immer. Und ja, Ihr habt es euch vielleicht gedacht: die Ackermann-Funktion ist nicht primitiv rekursiv und damit auch nicht LOOP-berechenbar.<\/p>\n <\/p>\nRekursionsschema<\/h2>\n
Ist die Addidtion primitiv rekursiv?<\/h2>\n
Ackermann-Funktion<\/h2>\n
Loop Berechenbarkeit<\/h2>\n
Aber hier steht schon zu viel Text. Vielleicht sind WHILE und LOOP-Berechenbarkeit ja einen eigenen Beitrag wert \ud83d\ude42<\/del><\/p>\nUpdate<\/h2>\n