Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Primitive Rekursion
Howdy (Leidens)genossen!
Hat jemand von euch eine Ahnung was genau dazu gehoert,wenn man beweisen will dass eine Funze primrek ist? Ich hatte bei der letzten Klausur trotz Angabe eines primitiven rekursionsschemas 0/6 Punkten. Kann mir das also jemand hier bitte schreiben, wie das auszusehen hat? Ein Checker/Nerd waere hier durchaus willkommen!
Fühl mich zwar nicht angesprochen, aber ich versuch’s trotzdem mal.
Du hast die Funktion, nennen wir sie f. Dann suchst du dir einen Parameter aus, über den du deine Rekursion machst. Bei f(x, y) z.B. y. Dann schaust du, was bei f(x, 0) rauskommt, bzw halt für den ersten definierten Wert für y. Das Ergebnis ist dann die Funktion g(x).
Dann schaust du, was für f(x, y+1) rauskommt. Dabei versuchst du, die Funktion irgendwie auf den Rekursionsvorgänger f(x, y) zurückzuführen. Das geschafft ist das Ergebnis dann die Funktion h(x, y, f(x, y)). Da das aber blöd aussieht, wird der Rekursionsvorgänger noch mit einem schönen Buchstaben substituiert, z.B. z := f(x, y). Auf beiden Seiten.
Am Ende hast du dann z.B. sowas dastehen wie
g(x) = 0
h(x, y, z) = succ(z)
Da man die Parameter von primitiv rekursiven Funktionen scheinbar nur in ihrer Gesamtheit verwenden darf, braucht man noch ein paar Projektionen. Dann haben wir:
g(x) = 0
h(x, y, z) = succ(pi_3^3(x, y, z))
Jetzt könnte man noch ganz durchdrehen und die Funktionen g und h als f definierende Funktionen deklarieren:
f = pr(g, h)
(Alle Angaben sind wie immer ohne Gewähr. Der Rechtsweg ist ausgeschlossen. Irrtum vorbehalten. Anwenden auf eigene Gefahr.)
Dazu hab ich auch eine Frage: Ist es ein gültiger Beweis, wenn man zu der Funktion ein LOOP-Programm schreibt?
Es heißt ja: Jedes LOOP-berechenbare Programm ist primitiv-rekursiv und umgekehrt.
wie würdet ihr die folgende Aufgabe lösen?:
Sei f eine einstellige prim.rek.Funktion.
F(x,y)=f^y(x).
Wir sollen zwei prim.rek.funktionen angeben so das die gegebene Funktion daraus hervorgeht…wie mach ichn das?
Ja, soweit ich weiß, sind LOOP-Programme auch ok.
@Bibi: Zuerst mal F(x,y) is pr. wenn f pr. Also musst du zeigen, dass f pr. Dann geht´s los:
f^0(x) = x , folgt g(x) = x.
f^(y+1)(x) = f(f^y(x)) folgt h(x,y,z) = π3^3(x,y,f(z)).
Aus dem ganzen folgt F(x,y) is pr.
Stimmt´s?
jupp 