Beweisen oder Widerlegen von primitiv rekursiven Funktionen |
01.02.2016, 10:32 | Auf diesen Beitrag antworten » |
Flurry1337 | 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 |
|
|