Flurry1337
Grünschnabel
Dabei seit: 31.01.2016
Beiträge: 2
|
|
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
|
|