{"id":635,"date":"2012-10-25T09:02:30","date_gmt":"2012-10-25T07:02:30","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=635"},"modified":"2013-06-24T20:15:08","modified_gmt":"2013-06-24T18:15:08","slug":"mue-rekursion-und-whileloop-berechenbarkeit","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=635","title":{"rendered":"TI: Mue-Rekursion und WHILE\/LOOP-Berechenbarkeit (Update 2)"},"content":{"rendered":"<p><strong>Update<\/strong>: Korrektur des Schleifenfehlers beim Loop-Programm (Danke Dennis).<\/p>\n<p>Mit der primitiven Rekursion haben wir eine echte Teilmenge der berechenbaren Funktionen bereits beschrieben. Und zwar, um genau zu sein, alle totalen Funktionen. D.h. sie sind \u00fcberall definiert (aber nicht alle totalen Funktionen sind primitiv rekursiv: siehe Ackermann-Funktion) und haben daher f\u00fcr jedes $$x$$ in $$f(x)$$ einen Funktionswert und somit endlich viele Rekursionsaufrufe, d.h. eine feste Schachtelungstiefe, was die Ackermann-Funktion z.B. nicht hat. Daher Achtung:<\/p>\n<blockquote><p>Jede primitiv rekursive Funktion ist total, aber nicht jede totale Funktion ist primitiv rekursiv!<\/p><\/blockquote>\n<p>Wir m\u00f6chten nun aber alle berechenbaren Funktionen haben. Auch die, die nicht \u00fcberall definiert sind wie z.B. die Wurzelfunktion (diese ist nur auf Quadratzahlen definiert), die partielle Subtraktion oder der Logarithmus zur Basis zwei (nur f\u00fcr 2-er-Potenzen definiert). Was also tun?<\/p>\n<p>Dazu reichen die 3 im vorherigen Beitrag vorgestellten Grundoperationen (konstante Funktion, Projektion und Nachfolgefunktion) im Zusammenspiel mit den Konstruktionsprinzipien der Komposition und primitiver Rekursion aber nicht aus. Wir schaffen es nicht mit den Werkzeugen der primitiven Rekursion (und damit ein LOOP-Programm) zu beschreiben, welches eine noch unbekannte Anzahl an Schleifendurchl\u00e4ufen vorzuweisen hat.\u00a0Beispiel folgt gleich.<\/p>\n<p>Um die Klasse der berechenbaren Funktionen nun zu erweitern m\u00fcssen wir unseren Werkzeugkasten entweder mit neuen Grundoperationen aufstocken oder ein neues Konstruktionsprinzip einf\u00fchren, welches die M\u00f6glichkeit mit einschlie\u00dft, dass eine Berechnung nicht terminiert, d.h. irgendwo nicht definiert ist (im Gegensatz zur primitiven Rekursion), da wir die Anzahl der Schleifendurchg\u00e4nge nicht kennen. Wir entscheiden uns f\u00fcr letzteres, da es ausreicht und f\u00fchren den $$\\mu$$-Operator ein. Es gibt den beschr\u00e4nkten und den unbeschr\u00e4nkten\u00a0$$\\mu$$-Operator. Beide tun das selbe, ersterer jedoch auf einem abgeschlossenen Intervall. D.h. wir haben eine vorher definierte Anzahl an Schleifendurchl\u00e4ufen, damit ein LOOP-Programm und somit letztendlich eine primitive Rekursion. Haben wir keine vorher festgelegte Anzahl an Durchl\u00e4ufen und kann deswegen das komplette Programm auch garnicht anhalten, so sprechen wir vom unbeschr\u00e4nkten\u00a0$$\\mu$$-Operator.<\/p>\n<p>Wenn man aus der programmiertechnischen Brille schaut, h\u00e4tte man folgende F\u00e4lle:<\/p>\n<ul>\n<li>1. beschr\u00e4nkter $$\\mu$$-Operator (unser h im Code):<\/li>\n<\/ul>\n<pre style=\"padding-left: 30px;\">m:=0;<\/pre>\n<pre style=\"padding-left: 30px;\">WHILE f(x1,..,xk,m) NOT 0 AND m &lt;= y DO<\/pre>\n<pre style=\"padding-left: 30px;\">\u00a0 m:=m+1;<\/pre>\n<pre style=\"padding-left: 30px;\">\u00a0 h:=m;<\/pre>\n<pre style=\"padding-left: 30px;\">END;<\/pre>\n<p>Beschr\u00e4nkung ist rot markiert.<\/p>\n<ul>\n<li>2. unbeschr\u00e4nkter $$\\mu$$-Operator (unser h im Code):<\/li>\n<\/ul>\n<pre style=\"padding-left: 30px;\">m:=0;<\/pre>\n<pre style=\"padding-left: 30px;\">WHILE f(x1,..,xk,m) NOT 0 DO<\/pre>\n<pre style=\"padding-left: 30px;\">\u00a0 m:=m+1;<\/pre>\n<pre style=\"padding-left: 30px;\">\u00a0 h:=m;<\/pre>\n<pre style=\"padding-left: 30px;\">END;<\/pre>\n<p>Hier fehlt die Beschr\u00e4nkung g\u00e4nzlich. Die Suche ist im schlimmsten Fall endlos. Das \u00c4ndert jedoch nichts an der Berechenbarkeit der Funktion und ist uns somit egal.<\/p>\n<p>Wir definieren hier den unbeschr\u00e4nkten $$\\mu$$-Operator\u00a0zun\u00e4chst formal und erkl\u00e4ren es dann:<\/p>\n<p>$$\\mu f(x_1,&#8230;,x_n):=min\\begin{cases} {} &amp; f(m,x_1,&#8230;,x_n) = 0\\\\m\\vert &amp; \\mbox{und } \\forall k &lt; m \\mbox{ ist} \\\\{} &amp; f(k,x_1,&#8230;,x_n) \\neq \\bot \\end{cases}$$<\/p>\n<p>Was macht das kleine Zeichen denn nun letztendlich? Es hilft uns dabei die vorab fehlende Anzahl an notwendigen Schleifendurchl\u00e4ufen im Programm zu kompensieren. Wir haben dann kein &#8222;tue etwas, und zwar x Mal&#8220; (LOOP), sondern ein &#8222;tue etwas bestimmtes solange etwas der Fall ist&#8220; (WHILE).\u00a0$$m$$ wird hier bei jedem Schleifendurchlauf hochgez\u00e4hlt und gepr\u00fcft ob $$f(m,x_1,&#8230;,x_n) = 0$$ ist. Es sucht also die erste &#8222;Nullstelle&#8220; der Funktion. Wenn das der Fall ist, haben wir das erste $$m$$, d.h. die Anzahl der Schleifendurchl\u00e4ufe bis zur ersten Nullstelle. Falls die Bedingung nicht erreicht wird,\u00a0$$f(k,x_1,&#8230;,x_n)$$ wird nie 0, terminiert die Schleife nicht. Das ist der Unterschied zu primitiv rekursiven (LOOP-berechenbaren) Funktionen. Dort steht bereits vor der Ausf\u00fchrung fest wieviele Schleifendurchl\u00e4ufe es gibt, sie haben also eine\u00a0<em>begrenzte Schachtelungstiefe<\/em>.<\/p>\n<p>Wichtig ist hierbei, dass die Funktion bis zum auftreten unseres gesuchten $$m$$ f\u00fcr alle Werte kleiner als $$m$$ einen Funktionswert liefert, d.h. tats\u00e4chlich \u00fcberall (bis dahin zumindest) definiert ist. Jetzt k\u00f6nntet Ihr euch fragen: &#8222;Warum zur H\u00f6lle interessiert uns die Nullstelle der Funktion?!&#8220;. Tut sie selbst eig. zun\u00e4chst nicht. Wir formen unsere Funktion nur so um, dass sie bei einer erfolgreichen Berechnung am Ende der Durchl\u00e4ufe = 0 ist. Wenn sie erreicht ist, haben wir die Berechnung beendet und unser Ergebnis ist die Anzahl der Schleifendurchl\u00e4ufe. Ansonsten terminiert die Maschine nicht und rechnet endlos weiter.<\/p>\n<p>Aber vielleicht wird das aus den Beispielen etwas deutlicher.<\/p>\n<p><strong>Beispiel<\/strong>: $$add(m,n)$$ (primitiv rekursiv, LOOP)<\/p>\n<p style=\"padding-left: 30px;\"><strong>Update<\/strong>: danke f\u00fcr die Korrektur des Schleifenfehlers, Dennis.<\/p>\n<p style=\"padding-left: 30px;\">Wir wissen aus der primitiven Rekursion, dass diese Funktion primitiv rekursiv ist. Auch wissen wir schon vorab Bescheid wieviele Schleifendurchl\u00e4ufe wir brauchen werden. N\u00e4mlich genau $$m$$ (oder $$n$$, je nachdem \u00fcber welche Variable wir hochz\u00e4hlen). Geben wir doch mal so ein Loop-Programm f\u00fcr die Addition an (x ist die Ergebnisvariable) welches nur die Grundoperationen nutzt:<\/p>\n<pre style=\"padding-left: 60px;\">x := n;\r\nLOOP m DO\r\n x := x + 1;\r\nEND<\/pre>\n<p style=\"padding-left: 30px;\">Oder der ganze Spa\u00df mit der Grundoperation Nachfolger: $$succ()$$:<\/p>\n<pre style=\"padding-left: 60px;\">x := n;\r\nLOOP m DO\r\n x := succ(x);\r\nEND<\/pre>\n<p style=\"padding-left: 30px;\">Wir wissen in beiden F\u00e4llen schon vorab wieviele Schleifendurchl\u00e4ufe wir haben werden: genau $$m$$ St\u00fcck.<\/p>\n<p><strong>Beispiel<\/strong>: partielle Subtraktion ($$\\mu$$-rekursiv, WHILE)<\/p>\n<p style=\"padding-left: 30px;\">W\u00e4hrend die totale Subtraktion (also die arithmetische Differenz) primitiv rekursiv sind, ist es die partielle Subtraktion nicht. Tun wir mal so als wissen wir das nicht und versuchen unser Gl\u00fcck. Die partielle Subtraktion ist definiert als:<\/p>\n<p style=\"padding-left: 30px;\">$$psub(a,b):=\\begin{cases} {a-b,} &amp; \\mbox{ falls } a \\geq b\\\\{undef.,} &amp; \\mbox{ sonst }\\end{cases}$$<\/p>\n<p style=\"padding-left: 30px;\">Sollte also a gr\u00f6\u00dfer oder gleich b sein, so erfolgt die Subtraktion. Andernfalls ist der Funktionswert undefiniert, d.h. unsere Funktion terminiert nicht. Wie formulieren wir diese Funktion denn nun primitiv rekursiv? Wir m\u00fcssen also ein LOOP-Programm angeben, welches den Funktionswert berechnet und aus den Grundoperationen besteht. Der beste Versuch scheitert bei dem Versuch eine 1 zu substrahieren:<\/p>\n<pre style=\"padding-left: 60px;\">x := a + 0;\r\nLOOP b DO\r\n x := x ??? 1\r\nEND<\/pre>\n<p style=\"padding-left: 30px;\">Und fehlt hier die Subtraktion selbst. Setzen wir mal die arithmetische Differenz ein, von der wir wissen, dass sie primitiv rekursiv ist. Sie ist wie folgt definiert:<\/p>\n<p style=\"padding-left: 30px;\">$$sub(a,b):=\\begin{cases} {a-b,} &amp; \\mbox{ falls } a \\geq b\\\\{0,} &amp; \\mbox{ sonst }\\end{cases}$$<\/p>\n<pre style=\"padding-left: 60px;\">x := a + 0;\r\nLOOP b DO\r\n x := sub(x,1)\r\nEND<\/pre>\n<p style=\"padding-left: 30px;\">Setzen wir die Werte a = 5 und b = 3, so haben wir 3 Schleifendurchl\u00e4ufe mit folgenden Aufrufen:<\/p>\n<pre style=\"padding-left: 60px;\">sub(5,1) = 4<\/pre>\n<pre style=\"padding-left: 60px;\">sub(4,1) = 3<\/pre>\n<pre style=\"padding-left: 60px;\">sub(3,1) = 2<\/pre>\n<p style=\"padding-left: 30px;\">Sieht gut aus, oder? Und nun wollen wir mal der Definition unserer partiellen Subtraktion $$psub$$ nach bei Werten $$b &gt; a$$ einen undefinierten Wert rausbekommen. Wir starten also mit a = 3 und b = 5 bei 5 Schleifendurchl\u00e4ufen (wir loopen ja \u00fcber b = 5).<\/p>\n<pre style=\"padding-left: 60px;\">sub (3,1) = 2<\/pre>\n<pre style=\"padding-left: 60px;\">sub (2,1) = 1<\/pre>\n<pre style=\"padding-left: 60px;\">sub (1,1) = 0<\/pre>\n<pre style=\"padding-left: 60px;\">sub (0,1) = 0<\/pre>\n<pre style=\"padding-left: 60px;\">sub (0,1) = 0<\/pre>\n<p style=\"padding-left: 30px;\">Was ist denn hier passiert?! Wir haben eine 0, was offensichtlich falsch ist. Jetzt k\u00f6nnte man meinen: &#8222;Ist doch kein Problem! Ist das eben unser undefinierter Wert falls $$b &gt; a$$!&#8220;. Und wie unterscheiden wir diesen vom Ergebnis wenn $$a = b$$ ist? Tja&#8230; da m\u00fcssen wir also mal eine L\u00f6sung f\u00fcr finden. Holen wir mal den $$\\mu$$-Operator zur Hilfe und basteln uns mit ihm eine WHILE-Schleife.<\/p>\n<p>Die Frage ist zun\u00e4chst: wie bekommen wir die feste Anzahl an Schleifendurchg\u00e4ngen weg? Wir m\u00fcssen ein Kriterium angeben, welches uns eine Abbruchbedingung und somit eine dynamische Anzahl an Schleifendurchg\u00e4ngen erlaubt. Und uns am besten auch noch den Wert f\u00fcr die Anzahl der dazu ben\u00f6tigten Schleifendurchg\u00e4nge liefert. Wir einigen uns zun\u00e4chst darauf, dass die Berechnung abgebrochen werden soll wenn der Wert 0 erreicht wird und bem\u00fchen unsere $$\\mu$$-Definition von oben:<\/p>\n<p>$$\\mu f(x_1,&#8230;,x_n):=min\\begin{cases} {} &amp; f(m,x_1,&#8230;,x_n) = 0\\\\m\\vert &amp; \\mbox{und } \\forall k &lt; m \\mbox{ ist} \\\\{} &amp; f(k,x_1,&#8230;,x_n) \\neq \\bot \\end{cases}$$<\/p>\n<p>Wir m\u00fcssen unsere Funktion also so schreiben damit es der $$\\mu$$-Rekursion entspricht:<\/p>\n<p>$$\\mu f(a,b):=min\\begin{cases} {} &amp; f(m,a,b) = 0\\\\m\\vert &amp; \\mbox{und } \\forall k &lt; m \\mbox{ ist} \\\\{} &amp; f(k,a,b) \\neq \\bot \\end{cases}$$<\/p>\n<p>Wir setzen die neue Funktion mit einem Parameter mehr (n\u00e4mlich m) = 0 f\u00fcr unsere Abbruchbedingung alleine nur mit den Grundoperationen\u00a0Wir setzen unsere Funktion = 0: $$f(m,a,b) = sub(b+m,a) + sub(a,b+m)$$ und\u00a0betrachten folgende F\u00e4lle in dem entstandenen WHILE-Programm:<\/p>\n<pre style=\"padding-left: 30px;\">m:=0;<\/pre>\n<pre style=\"padding-left: 30px;\">WHILE f(m,a,b) NOT 0 DO\r\n  h:=m;<\/pre>\n<pre style=\"padding-left: 30px;\">\u00a0 m:=m+1;<\/pre>\n<pre style=\"padding-left: 30px;\">END;<\/pre>\n<ul>\n<li>1. Fall $$a &gt; b$$: Ergebnis kann berechnet werden<\/li>\n<\/ul>\n<p>Am Ende der Schleifendurchg\u00e4nge muss der Funktionswert = 0 berechnet und die Anzahl der Schleifendurchg\u00e4nge in der Variable $$m$$ abgespeichert werden. Testweise probieren wir das mit $$a = 5, b = 2$$ aus:<\/p>\n<p>$$\\begin{array}{lcl}f(0,5,2)&amp;=&amp; sub(2+0,5) + sub(5,2+0) &amp; = 0 + 3 &amp; m = 0\\\\ {} &amp;=&amp; sub(2+1,5) + sub(5,2+1) &amp; = 0 + 2 &amp; m=1&amp; \\\\ {} &amp;=&amp; sub(2+2,5) + sub(5,2+2) &amp; = 0 + 1 &amp; m=2&amp;\\\\ {} &amp;=&amp; sub(2+3,5) + sub(5,2+3) &amp; = 0 + 0 &amp; m=3&amp;\\end{array}$$<\/p>\n<p>Ab $$m=3$$ ist unsere Funktion = 0 geworden, die Berechnung wird abgebrochen und wir haben in $$m$$ die Anzahl der Schleifendurchl\u00e4ufe als Ergebnis stehen. Passt also.\u00a0$$\\mu f(5,2) = 3$$.<\/p>\n<ul>\n<li>2. Fall $$a = b$$: Ergebnis kann berechnet werden<\/li>\n<\/ul>\n<p>Am Ende der Schleifendurchg\u00e4nge muss der Funktionswert = 0 berechnet und die Anzahl der Schleifendurchg\u00e4nge in der Variable $$m$$ abgespeichert werden.<\/p>\n<p>$$\\begin{array}{lcl}f(0,5,5)&amp;=&amp; sub(5+0,5) + sub(5,5+0) &amp; = 0 + 0 &amp; m = 0\\end{array}$$<\/p>\n<p>Und hier sind wir auch schon fertig. Passt auch.\u00a0$$\\mu f(5,5) = 0$$.<\/p>\n<ul>\n<li>3. Fall $$a &lt; b$$: Ergebnis ist undefiniert, Berechnung h\u00e4lt nie<\/li>\n<\/ul>\n<p>Ergebnis ist undefiniert, die Schleife ist endlos.<\/p>\n<p>$$\\begin{array}{lcl}f(0,2,5)&amp;=&amp; sub(5+0,2) + sub(2,5+0) &amp; = 3 + 0 &amp; m = 0\\\\ {} &amp;=&amp; sub(5+1,2) + sub(2,5+1) &amp; = 4 + 0 &amp; m=1&amp; \\\\ {} &amp;=&amp; sub(5+2,2) + sub(2,5+2) &amp; = 5 + 0 &amp; m=2&amp;\\\\ {} &amp;=&amp; &#8230; &amp; &#8230; &amp; &#8230; &amp;\\end{array}$$<\/p>\n<p>Hier bricht die Schleife nicht ab, da der Erste Teil der Substraktion mit jeder Schleife immer weiter hochgez\u00e4hlt wird. Das Ergebnis ist f\u00fcr $$a &lt; b$$ also undefiniert. $$\\mu f(2,5)=\\bot$$.\u00a0Genau das, was wir wollten.<\/p>\n<p>Und nun versuchen wir es mal etwas abstrakter und werden probieren die Goldbach-Vermutung als LOOP-Programm (und somit primitiv rekursiv) abzubilden:<\/p>\n<p><strong>Beispiel<\/strong>: Goldbach-Vermutung<\/p>\n<p>Die Goldbach-Vermutung besagt, dass jede gerade Zahl &gt; 2 als die Summe zweier Primzahlen geschrieben werden kann. Und wir wissen ja, wie wir das testen k\u00f6nnen: durchprobieren! Nehmen wir z.B. die 4: diese k\u00f6nnen wir als 4 = 2+2 schreiben. Nun nehmen wir die 6: 6 = 3 + 3. Geht auch. Das k\u00f6nnen wir so fortf\u00fchren. Und nun? Wir definieren die Goldbach-Vermutungs-Funktion, die wir auf LOOP (primitiv Rekursiv) oder WHILE ($$\\mu$$)-Berechenbarkeit pr\u00fcfen wollen durch ein Pr\u00e4dikat $$Goldbach$$. Das liefert uns eine 1 wenn die Bedingung erf\u00fcllt ist und ansonsten eine 0.<\/p>\n<p>$$Goldbach(n):=\\begin{cases} {1,} &amp; \\mbox{ wenn aus zwei Primzahlen darstellbar}\\\\{0,} &amp; \\mbox{ sonst }\\end{cases}$$<\/p>\n<p>Wie w\u00fcrde unser LOOP-Programm denn f\u00fcr die Goldbach-Vermutung aussehen? Etwa so?<\/p>\n<pre style=\"padding-left: 30px;\">x := 0;\r\nLOOP m DO\r\n x := Goldbach(m)\r\nEND<\/pre>\n<p>Hierbei gibt $$Goldbach(m)$$, wie erw\u00e4hnt, eine 1 aus wenn die Zahl $$m$$ mit zwei Primzahlen geschrieben werden kann und 0 sonst. Wir wollen alle $$m$$ testen, die Schleifendurchg\u00e4nge sind also dynamisch. Wir kommen hier mit dem LOOP also nicht sonderlich weit und das Programm ist wertlos. Es h\u00f6rt eben genau nach $$m$$ Schleifendurchg\u00e4ngen mit der Berechnung auf.\u00a0Wir versuchen es nun mit einem WHILE-Programm:<\/p>\n<p style=\"padding-left: 30px;\">x := 0;<\/p>\n<p style=\"padding-left: 30px;\">m:=0;<\/p>\n<pre style=\"padding-left: 30px;\">WHILE x NOT 0 DO\r\n  x := Goldbach(m);\r\n  <del>succ(m);<\/del>\r\n  h:=m;\r\n  succ(m);<\/pre>\n<pre style=\"padding-left: 30px;\">END<\/pre>\n<p>Ui, schau an. Sieht doch gut aus! Am Ende der Berechnung (wenn es denn eine gibt) bekommen wir im $$x$$ eine 0 wenn das Programm auf das erste (und somit auch das kleinste $$m$$ f\u00fcr das es der Fall ist) $$m$$ st\u00f6\u00dft, welches nicht mit zwei Primzahlen geschrieben werden kann, denn unsere Goldbach-Funktion gibt uns ja nach unserer oberen Definition eine 0 aus wenn die Zahl nicht als Summe zweier Primzahlen darstellbar ist (wie wir das genau berechnen ist uns derzeit &#8211; f\u00fcr das Verst\u00e4ndnis des $$\\mu$$-Operators selbst &#8211;\u00a0ziemlich egal). <del>Streng genommen wird das $$m$$ am Ende ja nochmal um eins erh\u00f6ht und wir bekommen das gesuchte $$m$$ um eins erh\u00f6ht und m\u00fcssten es um 1 dekrementieren, aber wir wollen mal nicht so kleinlich sein \ud83d\ude42<\/del> Mike hat in den Kommentaren mal kurz die WHILE-Schleife umgestellt, das geht nat\u00fcrlich auch und ist eine gute Idee. Damit ist die \u00c4nderung auch drin \ud83d\ude42<\/p>\n<p>Wie man sieht haben wir also eine freche Abk\u00fcrzung genommen: wir haben einfach $$Goldbach(m)$$ ohne Berechnungs-Definition verwendet und es auch nicht = 0 gesetzt. F\u00fcr das Verst\u00e4ndnis sollte das reichen. Ansonsten m\u00fcsste man genauso vorgehen wie bei der partiellen Subtraktion.<\/p>\n<p>Im Endeffekt minimalisieren wir hier also eine Funktion und suchen ihre kleinste Nullstelle. Lassen wir z.B. den\u00a0$$\\mu$$-Operator auf die konstante Funktion $$f(x) = 1$$ los, so werden wir nie eine Nullstelle finden (es gibt ja keine, der Funktionswert ist immer = 1) und enden in einer Endlosschleife. Damit ist die Funktion $$f$$ \u00fcberall undefiniert. Auch wenn ich eine Funktion $$f$$ habe, die eine Nullstelle hat, aber irgendwo davor undefiniert ist, so ist unsere\u00a0$$\\mu f$$ auch undefiniert. Das kann man sich beim Aufstellen einer Wertetabelle sehr gut vor Augen f\u00fchren.<\/p>\n<h2>Update<\/h2>\n<p>Den Merksatz habe ich bereits einen Betrag zuvor bei der primitiven Rekursion verwendet und halte ihn f\u00fcr so wichtig, ihn noch einmal hier zu verwenden. Bitte vollzieht in euren Gedanken den Merksatz nach damit die Beiden wichtigen Konstrukte auch wirklich h\u00e4ngen bleiben \ud83d\ude09<\/p>\n<p>Merksatz: jedes LOOP-Programm l\u00e4sst sich durch primitive Rekursion ausdr\u00fccken un jede primitiv rekursive Funktion durch ein LOOP-Programm. Ebenso l\u00e4sst sich ein LOOP-Programm durch ein WHILE-Programm ersetzen. Damit ist auch jede primitiv rekursive Funktion WHILE-Berechenbar. Jedoch gilt das nicht umgekehrt: WHILE-Schleifen lassen sich nicht durch LOOP-Schleifen ersetzen (es ist z.B. im Voraus nicht bekannt wie h\u00e4ufig die Schleife durchlaufen wird), siehe Ackermann-Funktion. Erst durch die $$\\mu-Rekursion$$ k\u00f6nnen wir das WHILE-Konstrukt mathemathisch greifbar machen.<\/p>\n<p>Wie immer gilt: wer grobe Schnitzer findet, ab in die Kommentare \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: Korrektur des Schleifenfehlers beim Loop-Programm (Danke Dennis). Mit der primitiven Rekursion haben wir eine echte Teilmenge der berechenbaren Funktionen bereits beschrieben. Und zwar, um genau zu sein, alle totalen Funktionen. D.h. sie sind \u00fcberall definiert (aber nicht alle totalen Funktionen sind primitiv rekursiv: siehe Ackermann-Funktion) und haben daher f\u00fcr jedes $$x$$ in $$f(x)$$ einen &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=635\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTI: Mue-Rekursion und WHILE\/LOOP-Berechenbarkeit (Update 2)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-635","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/635","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=635"}],"version-history":[{"count":62,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/635\/revisions"}],"predecessor-version":[{"id":704,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/635\/revisions\/704"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=635"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=635"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=635"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}