| Autor |
Beitrag |
    
Stefan
| | Veröffentlicht am Samstag, den 04. November, 2000 - 20:05: | 
|
Hallo,
Es geht um die Ackermann Funktion, die durch
f(o,y) = y+1
f(x+1,) = f(x,1)
f(x,y) = f(x-1, f(x, y-1))
definiert ist.
Für diese soll per vollst. Induktion bewiesen werden, dass gilt:
y < f(x,y)
Das ist mir auch irgendwie klar, da ja die Funktion nur zu einem Abschluss kommt wenn x=0 --> dann ist ja f(0,y)=y+1, d.h. der Funktionswert ist um 1 grösser als y. Nur wird ja y durch die rekursiven Aufrufe ständig verändert, und pendelt dabei scheinbar stets zwischen 0 und dem Funktionsergebnis-1.
Wie kann man diese Ungleichung also per vollst. Induktion beweisen?
Danke,
Stefan |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 04. November, 2000 - 21:51: |
|
Siehe hier. |
Stefan
| | Veröffentlicht am Samstag, den 04. November, 2000 - 21:55: |
|
danke,
ich hatte heute schonmal nach der Ackermann Funktion gesucht, lustigerweise hatte jemand in der Zwischenzeit dieselbe Frage gestellt.
Stefan |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 04. November, 2000 - 23:05: |
|
Hallo Stefan. Was ist f(4,4), f(5,5)? Zur Beantwortung dieser Frage darfst du einen Rechner benutzen. |
Stefan
| | Veröffentlicht am Samstag, den 04. November, 2000 - 23:38: |
|
Ab f(4,1) wirds echt haarig gross, f(4,4) und f(5,5) wurde garantiert noch nie berechnet (ich glaube f(4,2) ist 265536 oder so).
Ausserdem hab ich die Vermutung, das du das auch weisst.. |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 04. November, 2000 - 23:54: |
|
Ich hatte mir gerade ein kleines Progrämmchen geschrieben, dass f(x,y) rekursiv berechnen soll (hab mir aber auch keine sonderliche Mühe gegeben). Bei f(4,2) kommt es ziemlich schnell zum "Stack-Überlauf".
Nicht zu unrecht hat diese unscheinbar aussehende Funktion wohl einen eigenen Namen... |
Zaph (Zaph)
| | Veröffentlicht am Donnerstag, den 09. November, 2000 - 20:19: |
|
Siehe auch hier. |
|
