Primitiv Rekursive Funktionen

[Lim_Dul]

Wir müssen als Übungsaufgabe beweisen, das folgende Funktion primitiv rekursiv ist:
f(x,0) = g(x) (G ist primitiv rekursiv)
f(x,y+1) = f(f(x,y),y)

Problem ist, wir haben zur Verfüngung als Operationen um aus einer primitiv rekursiven Funktion eine andere zu machen folgende:
Substitution:
f(x)=g(h(x))
Und primitive Rekursion:
f(x,0)=g(x)
f(x,y+1)=h(x,y,f(x,y))

Und mir gelingt die Herleitung nicht, das die ganz oben angebene Formel sich daraus herleiten lässt.

Ich weiß, das die Formel oben sich schreiben lässt:
f(x,y)=g(g(g(.....g(x))..)) (2y fach)

Aber der Beweis warum das so ist, gelingt mir nicht.
Als Tip haben wir bekommen, die Logarithmus Funktion (Basis 2):
ld(0)=0
ld(x)=Abgerundet ld2(x)
Diese Funktion ist primitiv Rekursiv

Achja, alle Werte x,y sind natürliche Zahlen inklusive der Null.

[doppelelch]

Lässt sich in kurzen Worten darlegen, was "primitiv" rekursiv bedeutet?

Ist nur ne Frage.

Gruß

de

[Lim_Dul]

Das Thema hat sich mittlerweile zwar erledigt, aber die Definiton will ich dennoch geben.
Es stehen folgende Grundfunktionen zur Verfügung:


N(X)=x+1
Cn(x)=n (Liefert eine Konstante)
Pnm(x1,...,xm) = xn (Liefert das n-te Argument aus m argumenten).

Nach folgenden Vorschriften kann man daraus neue Funktionen bauen:
Substitution: f(x)=g(h1(x),...,hn(x))
und primitive Rekursion nach folgendem Schema:

f(x,0)=g(x)
f(x,y+1)=h(x,y,f(x,y))

[doppelelch]

Klingt ziemlich interessant. "Hat sich erledigt" ist allerdings nicht gerade motivierend. Deshalb werde ich mich da nun nicht reindenken.

Trotzdem Danke

Gruß

de

[Water]

Ich verstehe immer noch nicht, warum f(x,y+1)=h(x,y,f(x,y))
kann jemand helfen?