Montag, 19. Juli 2010

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

Keine Kommentare:

Kommentar veröffentlichen