 Thema: Beweisen oder Widerlegen von primitiv rekursiven Funktionen |
|
|
Hallo,
Ich soll:
Beweisen oder widerlegen Sie: Falls g ° f primitiv rekursiv ist,
(a) ist auch f primitiv rekursiv.
(b) ist auch g primitiv rekursiv.
Mein bisheriger Ansatz und wo es hapert:
Da hier steht wiederlegen würde ich annehmen, dass man hier die Ackermann Funktion verwenden soll um min eine der Aussagen zu wiederlegen.
Hier der Satz von Ackermann aus unserem Skript:
Annahme, ack sei primitiv rekursiv. Dann ist auch g(x) = ack(x, x) primitiv rekursiv,
d.h. es existiert ein c element von N mit g(x) < ack(c, x) für alle x. Für x = c ergibt sich
ein Widerspruch.
Demnach wäre doch dann die a wohl nicht richtig denn wenn g die ack funktion ist und g°f primitiv rekursiv ist, kann ich einfach ein f mit f(x) < ack(c,x) zeigen wo x = c ergibt, um dies zu wiederlegen. Hier ist aber auch mein Problem, wie mache ich das? Wie komme ich auf eine solche Funktion?
Gruß Flurry1337
|
|
| Thema: mue Rekursive Funktion even |
|
|
Hallo,
Ich soll zeigen, dass die Funktion mue rekursiv ist:
even(n) = ( n -> falls n gerade; nicht definiert sonst)
Ich darf annehmen, dass Addition, totale Subtraktion, Multiplikation, Vorgangerfunktion, mehrstelligen Nullkonstanten und Signumfunktion primitiv rekursiv sind.
Mein bisheriger Ansatz:
Also wenn ich die Aufgabe richtig verstehe, ist also eine prim. Rekursive Funktion h, deren Minimalisierung f ergibt gesucht.
h(n,n) = 0 wenn n gerade ist
h(n,n) > 0 wenn n ungerade ist
h(n,m) > 0 für alle m < n
und h ist primitiv rekursiv.
Ich hatte hierfür am anfang ein neues Thema erstellt da ich dachte die beiden Aufgabe haben recht wenig miteinander zu tun aber denke das ist jetzt doch nicht mehr so. Also hier mein While-Programm zu zur funktion even:
in x1, var x2, x3
x3:= x1;
while x1 != 0 DO
x1:= x1-1;
x2:= x1-1;
x1:=x2;
out x3
Stimmt das soweit? Wenn ja dann müsste ja h (n,n) ja ausgedrückt werden können über h(n,n)= add((even(n,n),odd(n,n)).
mit
even (0) = n
even (n+1) = odd (n)
odd (0) = 0
odd (n+1) = even (n)
Kann man irgendwas davon machen?
Freu mich über jeden kleinen Tipp,
Gruß Flurry1337
|
|
|
