Beweisen oder Widerlegen von primitiv rekursiven Funktionen

Neue Frage »

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
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »