Ackermannfunktion
-
Hallo,
ich habe eine Funktion: F: N → N, mit F(x) := fx(x), x Element N
Ich soll zeigen, dass diese Funktion schneller wächst als die Ackermannfunktion??? Ich bin aber der Meinung, das die Ackermannfunktion schneller wächst? Oder hab ich die Aufgabe nicht verstanden?
-
ack schrieb:
ich habe eine Funktion: F: N → N, mit F(x) := fx(x), x Element N
Was ist fx(x)?
Außerdem nimmt die Ackermann-Funktion zwei Parameter. Vermutlich meinst du ackermann(n, n)?
-
Also hier mal die gesamte Aufgabe:
Sei f0, f1, ... eine Folge von Funktionen fi: N → N, die definiert ist durch f0(x) = x + 1 sowie für i >= 1 durch fi(x) = f(x-1)i-1(x),
wobei f(l)(x) = f(f(...f(x))) die l-fache Anwendung von f bezeichnet mit x Element N.Zeigen Sie, dass die Funktion F: N → N mit F(x) := fx(x) für x Element N schließlich schneller wächst als jede Funktion fi.
-
ack schrieb:
Also hier mal die gesamte Aufgabe:
Sei f0, f1, ... eine Folge von Funktionen fi: N → N, die definiert ist durch f0(x) = x + 1 sowie für i >= 1 durch fi(x) = f(x-1)i-1(x),
wobei f(l)(x) = f(f(...f(x))) die l-fache Anwendung von f bezeichnet mit x Element N.Zeigen Sie, dass die Funktion F: N → N mit F(x) := fx(x) für x Element N schließlich schneller wächst als jede Funktion fi.
OK, die Definition verstehe ich. Wo liegt dein Problem, das zu zeigen? Versuch doch mal einen Beweis durch Widerspruch.
Mit der Ackermann-Funktion hat das erstmal relativ wenig zu tun. Man kann es mit den Eigenschaften der Ackermann-Funktion zeigen, wenn man mag, aber das geht garantiert weit über das Ziel der Aufgabe hinaus.
-
Also keine Ahnung, ob ich das jetzt richtig deute, aber kann es sein, dass es nur um den kleinen Unterschied geht, dass bei der ersten Funktion (x-1) eine Anwendung auf sich selbst weniger ist... und das immer... als bei der zweiten Funktion? Geht es darum?
-
ack schrieb:
Also keine Ahnung, ob ich das jetzt richtig deute, aber kann es sein, dass es nur um den kleinen Unterschied geht, dass bei der ersten Funktion (x-1) eine Anwendung auf sich selbst weniger ist... und das immer... als bei der zweiten Funktion? Geht es darum?
Die Aufgabenstellung war doch:
Aufgabenstellung schrieb:
Zeigen Sie, dass die Funktion F: N → N mit F(x) := fx(x) für x Element N schließlich schneller wächst als jede Funktion fi.
Da steht nichts davon, dass F schneller wachsen soll als die Ackermann-Funktion.
-
Was heißt denn dann
F(x) := fx(x)
???
Heißt das:
F(0) = f0(0) = 0 + 1 = 1
F(1) = f1(1) = 1 * 2 = 2
F(2) = f2(2) = 2 ^ 2 = 4???
-
ack schrieb:
Was heißt denn dann
F(x) := fx(x)
???
Heißt das:
F(0) = f0(0) = 0 + 1 = 1
F(1) = f1(1) = 1 * 2 = 2
F(2) = f2(2) = 2 ^ 2 = 4Fast.
F(1) = f1(1) stimmt, aber f1(1) ist nicht 1 * 2.
F(2) = f2(2) = geht auch anders weiter, das ist nicht 2^2.
-
F(0) = f0(0) = 0 + 1 = 1
F(1) = f1(1) = f0(0) + f0(0) = 1 + 1 = 2
F(2) = f1(2) = f1(1) + f1(1) = f0(0) + f0(0) + f0(0) + f0(0) = 1 + 1 + 1 + 1 = 4So vielleicht?
-
ack schrieb:
F(0) = f0(0) = 0 + 1 = 1
F(1) = f1(1) = f0(0) + f0(0) = 1 + 1 = 2
F(2) = f1(2) = f1(1) + f1(1) = f0(0) + f0(0) + f0(0) + f0(0) = 1 + 1 + 1 + 1 = 4So vielleicht?
Schau dir bitte nochmal genau die Definition an. Vor allem was f_0^0(x) ist, wäre hier vielleicht wichtig.