Zur Notation: Für Konstanten schreibe ich c(1,0), für Projektionen pr(3,3).
Möchte man zeigen, dass eine Funktion primitiv rekursiv ist, muss man zeigen, dass diese sich nur mit Hilfe von bereits als primitiv-rekursiv bewiesenen Funktionen darstellen lässt und das entstandene Konstrukt auch wirklich das berechnet, was es soll.
An sich ist es nichts anderes als Programmieren: Ihr überlegt euch, wie ihr die Funktion mit Hilfe der zur Verfügung stehenden Notationen entwickeln können.
Exerzieren wir das noch einmal am Beispiel des kleinsten gemeinsamen Vielfachen.
Wir gehen davon aus, dass das Berechnen des größten gemeinsamen Teilers noch nicht als primitiv rekursiv bewiesen wurde.
Schritt 1: Gedanken machen
Schritt 2: Den Ausdruck aufbauen
Schritt 3: Korrektheit zeigen
Schritt 4: Schnittigen Antwortsatz finden
Exerzieren wir das mal für zwei Beispiele durch, die unterschiedliche Herangehensweisen erlauben, Addition und Teilbarkeit.
Addition – Schritt 1: Gedanken machen
Wenn ich zwei Zahlen auf rekursive Weise addieren will, muss ich mir Gedanken machen über den Rekurssionsabbruch und den Rekrusionsschritt machen.
Der triviale Fall, der Rekursionsabbruch tritt ein, wenn einer der beiden Parameter 0 ist. In der primitiven Rekursioin wird immer der letzte Parameter bis zu einem bestimmten Punkt verringert, so dass die zweite Zahl 0 sein muss, im trivialen Fall.
add(x,0) = x
Dies ist der Rekursionsfall:
add(x,y+1) = succ(add(x,y))
Addition – Schritt 2: Den Ausdruck aufbauen
Hier wollen wir nun das abstrakte Programm entwickeln.
Es ist definiert durch Pr[Rekursionsabbruch,Rekurssionsschritt]
Rekursionsabbruch = add(x,0) = add(x) = x := pr(1,1)
Der Rekursionsabbruch hat, da der Zählparameter bei 0 angekommen ist, eine Stelle weniger als die zu beschreibende Funktion.
Der Rekursionsschritt hingegen hat eine Stelle mehr. Die letzten beiden Stellen sind für uns von besonderem Interesse, sie enthalten den bereits verringerten Zählparameter und den eigentlichen Rekusionsauffruf mit dem verringerten Zählparameter.
Kurz: f(x_1,.....x_n,y+1) = g(x_1,...,x_n,y,f(x,y))
Rekurssionsschritt = add(x,y+1) = succ(add(x,y)) = s o pr(3,3)
Warum ist hier der ein Ausdruck der Art s o add o (pr(3,1),pr(3,2))? Selbstreferenz dieser Art ist im Schema verboten. Der Funktionsname darf so nicht im Ausdruck auftauchen. Dafür ist die letzte Projektion da.
Der gesamte Ausdruck, der die Addition berechnen soll sieht zusammengesetzt folgendermaßen aus:
add = Pr[pr(1,1),succ o pr(3,3)]
Die benutzten Funktion successor, sowie die Projektion, das Ausgeben von Konstanten und die Komposition sind primitiv rekursiv. Der Ausdruck, den wir gebaut haben, ist also auch primitiv rekursiv.
Addition - Schritt 3: Korrektheit zeigen
Um zu zeigen, dass der Ausdruck auch wirklich die Addition berechnet, analysieren wir das rekursive Verhalten des Ausdrucks:
add(x,0) = pr(1,1)(x) = x
add(x,y+1) = so pr(3,3)(x,y,add(x,y)) = succ(add(x,y)) = add(x,y)+1
Hey, das sieht ja haargenau aus, wie die Überlegung, die wir uns ursprünglich gemacht haben! Dieser Ausdruck berechnet tatsächlich die Addition.
Addition - Schritt 4: Schnittigen Antwortsatz finden
Da ein Asudruck gefunden wurde, der primitiv rekursiv ist (→ Schritt 2) und nachweislich die Addition berechnet (→ Schritt 3), ist gezeigt, dass die Addition eine primitiv-rekursive Funktion ist
Der Rest folgt noch! Schaut immer mal wieder rein. :)
TBD:
Programmierung durch Fallunterscheidung
Programmierung durch beschränkte Suche
Unbeschränkte Minimierung
Keine Kommentare:
Kommentar veröffentlichen