Primitive Rekursion III - Suche

In der Rekursion gibt es zwei Arten von Suche: Beschränkte und unbeschränkte Suche.

Erste lässt sich problemlos in der primitiven Rekursion nutzen, die andere ändert jedoch die Klasse der Funktion zu Mü-rekursiv (entsprechenden griechischen Buchstaben vorstellen.)

Kommen wir zuerst zur beschränkten Suche. Zu unterscheiden sind Minimierung und Maximierung.
Erste sucht von 0 bis zu einer bestimmten Schranke. Letztere von einer bestimmten Schranke bis hin zu 0.

Das Schema schaut wie folgt aus. (Ich beschreibe hier nur die beschränkte Minimierung, die Maximierung verhält sich analog)

(a) Min_g[f].

Auf gut deutsch: Suche das kleinste g', aber nur bis du g erreicht, für das f 0 ergibt. Gib dieses g' aus, sonst gib die Grenze addiert mit 1 aus

g ist eine primitiv-rekursive Funktion, es handelt sich hierbei zumeist um die Konstantenfunktion.



Nun zu den Mü-Rekursiven Funktionen.

Wie bereits erwähnt, ist deren Suche unbeschränkt. Die Berechnung eines Funktionswertes kann sich also bis zur Unendlichkeit hinziehen.
Erstmals werden hier auch nicht totale Funktionen betrachtet.
Das Schema für unbeschränkte Suche schaut wie folgt aus:

(b) mü f := min{y|f(x,y) = 0} falls dieses existiert und f(x,i) definiert für alle i............. _|_ sonst

Zu gut Deutsch: Suche solange, bis du etwas hast, dass in der Funktion 0 ergibt, so es denn existiert, und die Funktion für jeden Wert, den du vorher überprüft hast definiert ist. Sonst gibt "undefiniert" zurück

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.