primitiv rekursiv

[BlackWidow83]

Hi Leute,

ich hab hier eine kleine Aufgabe zu bewältigen und weiß nicht, wie ich da rangehen kann.

"Zeigen Sie, dass die Funktionen exp und pred primitiv rekursive Funktionen sind."

Dadrunter stehen dann noch 4 kleine Hilfestellungen, die bis auf die 2. auch alle klar sind:

exp(x, 0) = 1
exp(x, succ() = mult(x, exp(x, y))
pred(0) = 0
pred(succ) = y


Kann jemand helfen, wie ich diese Aufgabe zu lösen hab?

Gruß
Basti

 

[Hellie]

"Zeigen Sie, dass die Funktionen exp und pred primitiv rekursive Funktionen sind."

exp(x, 0) = 1
exp(x, succ() = mult(x, exp(x, y))
pred(0) = 0
pred(succ) = y

Also... dass exp eine rekursive Funktion ist, erkennt man imho an dem Selbstaufruf (2. Hinweis) und an der Abbruchbedingung, s. 1 Hinweis. Dass es sich um primitiv-rekursive Fkt. handelt (Laut Wikipedia: Funktionen, die auf bestimmte Art aus einfachen Grundoperationen zusammengesetzt werden können), ist für mich nicht ersichtlich. Auch warum pred eine rekursive Prozedur ist, kann ich nicht aus den Hinweisen herauslesen. Höchstens eine Abbruchbedingung im 3. Hinweis. Hast du vielleicht irgendwelche Funktionen gegeben, also Quelltext dazu? Oder zumindest einen hinweis, was die einzelnen Funktionen machen?

lg Hellie

 

[BlackWidow83]

Hallo Hellie,

erstmal vielen Dank für Deine Antwort.
Also weitere Hilfestellungen/Funktionen sind in der Aufgabe nicht gegeben. Allerdings kann ich Dir sagen, was die einzelnen Funktionen machen:

exp = Exponent (z. B. exp(x, 0)) = x^0
succ = Nachfolger eines Ausdrucks (z. B. succ(3) = 4)
pred = analog zu succ der Vorgänger eines Ausdrucks

 

[Merlin732]

Hi BlackWidow83,

also ich fass es nochmal zusammen.

Die Funktionen sind rekursiv, da sie sich selbst aufrufen.

Primitiv Rekursive Funktionen beruhen auf der Idee, dass sich komplexe Funktionen aus einfachen Basisfunktionen definieren lassen (durch Funktionsschachtelung und Rekursion).

Basisfunktionen der primitiven Rekursion sind:

- die Nullfunktion n(x)=0
- die Nachfolgerfunktion s(x) = x+1
- die Projektion

Also sehen Funktionen immer so aus:

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

Wenn du also eine Formel bekommst, also z.b. f(2,2) dann schaust du wo sie passt, in dem Fall die 2. Funktion, da der Parameter 2 ja größer 0 ist und dann wendest du die rechte Seite an. wenn auf der rechten seite f(y,y) vorkommt, dann setzt du wieder die richtige formel ein etc.

Hoffe das hat etwas geholfen.

MfG Lars

 

[Hellie]

Dann sollte man das ganze vielleicht umschreiben, aus den Hinweisen:

Der zweite Hinweis sagt ja eigentlich, dass x^y= x* x^(y-1) ist. Demnach kann man statt

exp(x, succ() = mult(x, exp(x, y)) auch exp(x, x)= mult(y, exp(x, pred)) schreiben. Damit wird der Exponent mit jedem rekursiven Aufruf um 1 verringert, bis er schließlich 0 erriecht, was als Abbruchbedingung gilt.

Und wenn pred(succ)=y ist, kann man auch sagen, dass pred=y-1 ist. Prinzipiell könnte man argumentieren, dass der Funktionswert von y abhängig ist (das erkennt man auch an Hinweis 4 selbst), allerdings sehe ich darin keinen Selbstaufruf an sich, weil die Funktion ja nicht noch mal aufgerufen wird. Laut Wikipedia ist das aber auch nicht wichtig (sorry, ich steh selbst nicht sonderlich tief in der Materie). Dort findest du auch eine Erklärung, warum Multiplikation und Addition primitiv-rekursiv sind. Mit meinem Schülerwissen komme ich da leider nicht so ganz mit.

lg Hellie

 

[Merlin732]

wie gesagt, primitiv rekursiv bedeutet nur, dass man komplexe funktionen auf einfache basisfunktionen zurückführen kann.

in den komplexen funktionen sind dann natürlich die basisfunktionen enthalten und diese können sich auf wieder selbst aufrufen.
ich würde raten einfach mal ein bespiel zu rechnen, also mal

exp(5,2) rechnen, die funktion dafür ist ja bekannt.

exp(x, 0) = 1
exp(x, succ() = mult(x, exp(x, y))

wenn du das verstanden hast, dann versuch doch einfach mal eine solche primitive rekursion für fibbonaci zahlen zu finden.

 

[vop]

Hast Du inzwischen mal reingeschaut:

Etwa hier:
http://de.wikipedia.org/wiki/Primitiv-rekursive_Funktion

Damit solltest Du alles haben, was benötigt wird.

P.S.
Die Frage an sich ist ja nicht gerade Pascal/Delphi....

vop