Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Beweisen oder Widerlegen von primitiv rekursiven Funktionen (http://www.informatikerboard.de/board/thread.php?threadid=2826)
Geschrieben von Flurry1337 am 01.02.2016 um 10:32:
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
Forensoftware: Burning Board, entwickelt von WoltLab GmbH