Primitive Rekursion II - Programmierung durch Fallunterscheidung

Soderle, weiter geht's.



Angenommen man möchte der Einfachheit halber eine Funktion der Form

(a) h(x) = | f(x) falls t(x) = 0
...........| g(x) sonst

darstellen. Also eine Funktion, die abhängig von einer Prüffunktion t entweder die Funktion f oder g auf die Eingabe anwendet.
Auch solche Funktionen sind primitiv-rekursiv, wenn jeder ihrer Bestandteile ebenfalls primitiv-rekursiv ist.

Mithilfe der Signum-Funktion sign, die 1 ausgibt, wenn ein bestimmter Ausdruck einen positiven Wert annimmt und 0 andernfalls, lässt sich die Funktion h leicht umsetzen.

h(x) = (1−sign(t(x))) ∗ f (x) + sign(t(x)) ∗ g(x)


Die Intuition dahinter ist die Folgende:
Ich multipliziere das Signum-Ergebnis der Prüffunktion subtrahiert von 1 mit der Funktion f(x) und addiere das ganze mit dem Signum-Ergebnis der Prüffunktion multipliziert mit g(x).

Ergibt die Prüffunktion nun 0, multipliziere ich das Ergebnis der Funktion f(x) mit 1 und das Ergebnis von g(x) mit 0. f(x) wird also ausgeführt.
Andersherum ergibt die Subtraktion 0, und das Ergebnis von g(x) wird da Ergebnis von h(x).

Obwohl eine Addition stattfindet, wird immer nur das Ergebnis einer der beiden Teilfunktionen genutzt, da das andere unweigerlich einer Multiplikation mit 0 entgegensteht.

In ordentlicher primitiv-rekursiver Schreibweise sieht das ganze dann so aus:

h = add o (mul o (sub o (c(k,1), sign o t), f ), mul o (sign o t, g))


Soviel dazu. Weiter mit Suche.