TI: Mue-Rekursion und WHILE/LOOP-Berechenbarkeit (Update 2)

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 überall definiert (aber nicht alle totalen Funktionen sind primitiv rekursiv: siehe Ackermann-Funktion) und haben daher für 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:

Jede primitiv rekursive Funktion ist total, aber nicht jede totale Funktion ist primitiv rekursiv!

Wir möchten nun aber alle berechenbaren Funktionen haben. Auch die, die nicht überall definiert sind wie z.B. die Wurzelfunktion (diese ist nur auf Quadratzahlen definiert), die partielle Subtraktion oder der Logarithmus zur Basis zwei (nur für 2-er-Potenzen definiert). Was also tun?

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äufen vorzuweisen hat. Beispiel folgt gleich.

Um die Klasse der berechenbaren Funktionen nun zu erweitern müssen wir unseren Werkzeugkasten entweder mit neuen Grundoperationen aufstocken oder ein neues Konstruktionsprinzip einführen, welches die Möglichkeit mit einschließt, dass eine Berechnung nicht terminiert, d.h. irgendwo nicht definiert ist (im Gegensatz zur primitiven Rekursion), da wir die Anzahl der Schleifendurchgänge nicht kennen. Wir entscheiden uns für letzteres, da es ausreicht und führen den $\mu$-Operator ein. Es gibt den beschränkten und den unbeschränkten $\mu$-Operator. Beide tun das selbe, ersterer jedoch auf einem abgeschlossenen Intervall. D.h. wir haben eine vorher definierte Anzahl an Schleifendurchläufen, damit ein LOOP-Programm und somit letztendlich eine primitive Rekursion. Haben wir keine vorher festgelegte Anzahl an Durchläufen und kann deswegen das komplette Programm auch garnicht anhalten, so sprechen wir vom unbeschränkten $\mu$-Operator.

Wenn man aus der programmiertechnischen Brille schaut, hätte man folgende Fälle:

• 1. beschränkter $\mu$-Operator (unser h im Code):

m:=0;

WHILE f(x1,..,xk,m) NOT 0 AND m <= y DO

  m:=m+1;

  h:=m;

END;

Beschränkung ist rot markiert.

• 2. unbeschränkter $\mu$-Operator (unser h im Code):

m:=0;

WHILE f(x1,..,xk,m) NOT 0 DO

  m:=m+1;

  h:=m;

END;

Hier fehlt die Beschränkung gänzlich. Die Suche ist im schlimmsten Fall endlos. Das Ändert jedoch nichts an der Berechenbarkeit der Funktion und ist uns somit egal.

Wir definieren hier den unbeschränkten $\mu$-Operator zunächst formal und erklären es dann:

$\mu f(x_1,...,x_n):=min\begin{cases} {} & f(m,x_1,...,x_n) = 0\\m\vert & \mbox{und } \forall k < m \mbox{ ist} \\{} & f(k,x_1,...,x_n) \neq \bot \end{cases}$

Was macht das kleine Zeichen denn nun letztendlich? Es hilft uns dabei die vorab fehlende Anzahl an notwendigen Schleifendurchläufen im Programm zu kompensieren. Wir haben dann kein "tue etwas, und zwar x Mal" (LOOP), sondern ein "tue etwas bestimmtes solange etwas der Fall ist" (WHILE). $m$ wird hier bei jedem Schleifendurchlauf hochgezählt und geprüft ob $f(m,x_1,...,x_n) = 0$ ist. Es sucht also die erste "Nullstelle" der Funktion. Wenn das der Fall ist, haben wir das erste $m$, d.h. die Anzahl der Schleifendurchläufe bis zur ersten Nullstelle. Falls die Bedingung nicht erreicht wird, $f(k,x_1,...,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ührung fest wieviele Schleifendurchläufe es gibt, sie haben also eine begrenzte Schachtelungstiefe.

Wichtig ist hierbei, dass die Funktion bis zum auftreten unseres gesuchten $m$ für alle Werte kleiner als $m$ einen Funktionswert liefert, d.h. tatsächlich überall (bis dahin zumindest) definiert ist. Jetzt könntet Ihr euch fragen: "Warum zur Hölle interessiert uns die Nullstelle der Funktion?!". Tut sie selbst eig. zunächst nicht. Wir formen unsere Funktion nur so um, dass sie bei einer erfolgreichen Berechnung am Ende der Durchläufe = 0 ist. Wenn sie erreicht ist, haben wir die Berechnung beendet und unser Ergebnis ist die Anzahl der Schleifendurchläufe. Ansonsten terminiert die Maschine nicht und rechnet endlos weiter.

Aber vielleicht wird das aus den Beispielen etwas deutlicher.

Beispiel: $add(m,n)$ (primitiv rekursiv, LOOP)

Update: danke für die Korrektur des Schleifenfehlers, Dennis.

Wir wissen aus der primitiven Rekursion, dass diese Funktion primitiv rekursiv ist. Auch wissen wir schon vorab Bescheid wieviele Schleifendurchläufe wir brauchen werden. Nämlich genau $m$ (oder $n$, je nachdem über welche Variable wir hochzählen). Geben wir doch mal so ein Loop-Programm für die Addition an (x ist die Ergebnisvariable) welches nur die Grundoperationen nutzt:

x := n;
LOOP m DO
 x := x + 1;
END

Oder der ganze Spaß mit der Grundoperation Nachfolger: $succ()$:

x := n;
LOOP m DO
 x := succ(x);
END

Wir wissen in beiden Fällen schon vorab wieviele Schleifendurchläufe wir haben werden: genau $m$ Stück.

Beispiel: partielle Subtraktion ($\mu$-rekursiv, WHILE)

Während 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ück. Die partielle Subtraktion ist definiert als:

$psub(a,b):=\begin{cases} {a-b,} & \mbox{ falls } a \geq b\\{undef.,} & \mbox{ sonst }\end{cases}$

Sollte also a größer 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üssen 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:

x := a + 0;
LOOP b DO
 x := x ??? 1
END

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:

$sub(a,b):=\begin{cases} {a-b,} & \mbox{ falls } a \geq b\\{0,} & \mbox{ sonst }\end{cases}$

x := a + 0;
LOOP b DO
 x := sub(x,1)
END

Setzen wir die Werte a = 5 und b = 3, so haben wir 3 Schleifendurchläufe mit folgenden Aufrufen:

sub(5,1) = 4

sub(4,1) = 3

sub(3,1) = 2

Sieht gut aus, oder? Und nun wollen wir mal der Definition unserer partiellen Subtraktion $psub$ nach bei Werten $b > a$ einen undefinierten Wert rausbekommen. Wir starten also mit a = 3 und b = 5 bei 5 Schleifendurchläufen (wir loopen ja über b = 5).

sub (3,1) = 2

sub (2,1) = 1

sub (1,1) = 0

sub (0,1) = 0

sub (0,1) = 0

Was ist denn hier passiert?! Wir haben eine 0, was offensichtlich falsch ist. Jetzt könnte man meinen: "Ist doch kein Problem! Ist das eben unser undefinierter Wert falls $b > a$!". Und wie unterscheiden wir diesen vom Ergebnis wenn $a = b$ ist? Tja... da müssen wir also mal eine Lösung für finden. Holen wir mal den $\mu$-Operator zur Hilfe und basteln uns mit ihm eine WHILE-Schleife.

Die Frage ist zunächst: wie bekommen wir die feste Anzahl an Schleifendurchgängen weg? Wir müssen ein Kriterium angeben, welches uns eine Abbruchbedingung und somit eine dynamische Anzahl an Schleifendurchgängen erlaubt. Und uns am besten auch noch den Wert für die Anzahl der dazu benötigten Schleifendurchgänge liefert. Wir einigen uns zunächst darauf, dass die Berechnung abgebrochen werden soll wenn der Wert 0 erreicht wird und bemühen unsere $\mu$-Definition von oben:

$\mu f(x_1,...,x_n):=min\begin{cases} {} & f(m,x_1,...,x_n) = 0\\m\vert & \mbox{und } \forall k < m \mbox{ ist} \\{} & f(k,x_1,...,x_n) \neq \bot \end{cases}$

Wir müssen unsere Funktion also so schreiben damit es der $\mu$-Rekursion entspricht:

$\mu f(a,b):=min\begin{cases} {} & f(m,a,b) = 0\\m\vert & \mbox{und } \forall k < m \mbox{ ist} \\{} & f(k,a,b) \neq \bot \end{cases}$

Wir setzen die neue Funktion mit einem Parameter mehr (nämlich m) = 0 für unsere Abbruchbedingung alleine nur mit den Grundoperationen Wir setzen unsere Funktion = 0: $f(m,a,b) = sub(b+m,a) + sub(a,b+m)$ und betrachten folgende Fälle in dem entstandenen WHILE-Programm:

m:=0;

WHILE f(m,a,b) NOT 0 DO
  h:=m;

  m:=m+1;

END;

• 1. Fall $a > b$: Ergebnis kann berechnet werden

Am Ende der Schleifendurchgänge muss der Funktionswert = 0 berechnet und die Anzahl der Schleifendurchgänge in der Variable $m$ abgespeichert werden. Testweise probieren wir das mit $a = 5, b = 2$ aus:

$\begin{array}{lcl}f(0,5,2)&=& sub(2+0,5) + sub(5,2+0) & = 0 + 3 & m = 0\\ {} &=& sub(2+1,5) + sub(5,2+1) & = 0 + 2 & m=1& \\ {} &=& sub(2+2,5) + sub(5,2+2) & = 0 + 1 & m=2&\\ {} &=& sub(2+3,5) + sub(5,2+3) & = 0 + 0 & m=3&\end{array}$

Ab $m=3$ ist unsere Funktion = 0 geworden, die Berechnung wird abgebrochen und wir haben in $m$ die Anzahl der Schleifendurchläufe als Ergebnis stehen. Passt also. $\mu f(5,2) = 3$.

• 2. Fall $a = b$: Ergebnis kann berechnet werden

Am Ende der Schleifendurchgänge muss der Funktionswert = 0 berechnet und die Anzahl der Schleifendurchgänge in der Variable $m$ abgespeichert werden.

$\begin{array}{lcl}f(0,5,5)&=& sub(5+0,5) + sub(5,5+0) & = 0 + 0 & m = 0\end{array}$

Und hier sind wir auch schon fertig. Passt auch. $\mu f(5,5) = 0$.

• 3. Fall $a < b$: Ergebnis ist undefiniert, Berechnung hält nie

Ergebnis ist undefiniert, die Schleife ist endlos.

$\begin{array}{lcl}f(0,2,5)&=& sub(5+0,2) + sub(2,5+0) & = 3 + 0 & m = 0\\ {} &=& sub(5+1,2) + sub(2,5+1) & = 4 + 0 & m=1& \\ {} &=& sub(5+2,2) + sub(2,5+2) & = 5 + 0 & m=2&\\ {} &=& ... & ... & ... &\end{array}$

Hier bricht die Schleife nicht ab, da der Erste Teil der Substraktion mit jeder Schleife immer weiter hochgezählt wird. Das Ergebnis ist für $a < b$ also undefiniert. $\mu f(2,5)=\bot$. Genau das, was wir wollten.

Und nun versuchen wir es mal etwas abstrakter und werden probieren die Goldbach-Vermutung als LOOP-Programm (und somit primitiv rekursiv) abzubilden:

Beispiel: Goldbach-Vermutung

Die Goldbach-Vermutung besagt, dass jede gerade Zahl > 2 als die Summe zweier Primzahlen geschrieben werden kann. Und wir wissen ja, wie wir das testen können: durchprobieren! Nehmen wir z.B. die 4: diese können wir als 4 = 2+2 schreiben. Nun nehmen wir die 6: 6 = 3 + 3. Geht auch. Das können wir so fortführen. Und nun? Wir definieren die Goldbach-Vermutungs-Funktion, die wir auf LOOP (primitiv Rekursiv) oder WHILE ($\mu$)-Berechenbarkeit prüfen wollen durch ein Prädikat $Goldbach$. Das liefert uns eine 1 wenn die Bedingung erfüllt ist und ansonsten eine 0.

$Goldbach(n):=\begin{cases} {1,} & \mbox{ wenn aus zwei Primzahlen darstellbar}\\{0,} & \mbox{ sonst }\end{cases}$

Wie würde unser LOOP-Programm denn für die Goldbach-Vermutung aussehen? Etwa so?

x := 0;
LOOP m DO
 x := Goldbach(m)
END

Hierbei gibt $Goldbach(m)$, wie erwähnt, eine 1 aus wenn die Zahl $m$ mit zwei Primzahlen geschrieben werden kann und 0 sonst. Wir wollen alle $m$ testen, die Schleifendurchgänge sind also dynamisch. Wir kommen hier mit dem LOOP also nicht sonderlich weit und das Programm ist wertlos. Es hört eben genau nach $m$ Schleifendurchgängen mit der Berechnung auf. Wir versuchen es nun mit einem WHILE-Programm:

x := 0;

m:=0;

WHILE x NOT 0 DO
  x := Goldbach(m);
  succ(m);
  h:=m;
  succ(m);

END

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ür das es der Fall ist) $m$ stößt, 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 - für das Verständnis des $\mu$-Operators selbst - ziemlich egal). Streng genommen wird das $m$ am Ende ja nochmal um eins erhöht und wir bekommen das gesuchte $m$ um eins erhöht und müssten es um 1 dekrementieren, aber wir wollen mal nicht so kleinlich sein 🙂 Mike hat in den Kommentaren mal kurz die WHILE-Schleife umgestellt, das geht natürlich auch und ist eine gute Idee. Damit ist die Änderung auch drin 🙂

Wie man sieht haben wir also eine freche Abkürzung genommen: wir haben einfach $Goldbach(m)$ ohne Berechnungs-Definition verwendet und es auch nicht = 0 gesetzt. Für das Verständnis sollte das reichen. Ansonsten müsste man genauso vorgehen wie bei der partiellen Subtraktion.

Im Endeffekt minimalisieren wir hier also eine Funktion und suchen ihre kleinste Nullstelle. Lassen wir z.B. den $\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$ überall undefiniert. Auch wenn ich eine Funktion $f$ habe, die eine Nullstelle hat, aber irgendwo davor undefiniert ist, so ist unsere $\mu f$ auch undefiniert. Das kann man sich beim Aufstellen einer Wertetabelle sehr gut vor Augen führen.

Update

Den Merksatz habe ich bereits einen Betrag zuvor bei der primitiven Rekursion verwendet und halte ihn für so wichtig, ihn noch einmal hier zu verwenden. Bitte vollzieht in euren Gedanken den Merksatz nach damit die Beiden wichtigen Konstrukte auch wirklich hängen bleiben 😉

Merksatz: jedes LOOP-Programm lässt sich durch primitive Rekursion ausdrücken un jede primitiv rekursive Funktion durch ein LOOP-Programm. Ebenso lässt 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äufig die Schleife durchlaufen wird), siehe Ackermann-Funktion. Erst durch die $\mu-Rekursion$ können wir das WHILE-Konstrukt mathemathisch greifbar machen.

Wie immer gilt: wer grobe Schnitzer findet, ab in die Kommentare 🙂

Datum: 25. Oktober 2012
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url