| Autor |
Beitrag |
    
michael
| | Veröffentlicht am Samstag, den 04. November, 2000 - 12:08: | 
|
die Ackermann Funktion f:NxN -> N sei durch
f(0,y)=y+1, f(x+1,0)=f(x,1),
f(x+1,y+1) = f(x,f(x+1,y)) definiert.
Beweisen sie durch vollständige Induktion
y < f(x,y)
Ich hab überhaupt keine ahnung wie das hier gehn soll. kann mir bitte jemand den lösungsweg darlegen
danke. |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 04. November, 2000 - 13:36: |
|
Beweis durch VI über x.
x = 0: f(0,y) = y + 1 > y.
x -> x+1.
Beh: f(x+1,y) > y.
Bew. duch VI über y.
y = 0: f(x+1,0) = f(x,1) > 1 > 0 (nach erster IV).
y -> y+1.
f(x+1,y+1) = f(x,f(x+1,y))
> f(x+1,y) (nach erster IV)
> y (nach zweiter IV)
Da f(.,.) immer eine natürliche Zahl ist, folgt sogar f(x+1,y+1) > y+1.
(Wenn a > b > c und a,b,c natürliche Zahlen, dann a > c+1.)
Dass f(.,.) immer eine natürliche Zahl ist, muss, wenn man korrekt sein will, eigentlich auch mit VI bewiesen werden. |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 04. November, 2000 - 23:07: |
|
Hallo Michael. Zusatzfrage: Was ist f(4,4), f(5,5)? Zur Beantwortung dieser Frage darfst du einen Rechner benutzen. Versuch es aber erst mal ohne. |
michael
| | Veröffentlicht am Sonntag, den 05. November, 2000 - 11:51: |
|
moin zaph. erstmal danke für die induktionssache.
nun.. die ackermann funktion viel stärker wachsend alle primitiv-rekursiven Funktionen, dass ich dir wohl nicht sagen kann was f(4,4) geschweige denn f(5,5) ist.
f(4,2) besitzt 19729 stellen
f(4,4) ist größer als 10^10^10^19000
jedenfalls kann ich das wohl nicht mit meim computer so ohne weiteres berechnen. |
Zaph (Zaph)
| | Veröffentlicht am Donnerstag, den 09. November, 2000 - 20:15: |
|
Hallo Michael, ich danke auch dir.
Es geht ja ganz harmlos los:
f(0,y) = y + 1
f(1,y) = y + 2
f(2,y) = 2y + 3
f(3,y) = 2y+3 - 3
Aber dann
f(4,0) = f(3,1) = 13
f(4,1) = f(3,13) = 65533
f(4,2) = f(3,65533) = 265536 - 3
...
f(4,y) = 2^2^...^2 - 3 (ein Turm aus y+3 vielen Zweien!)
f(5,0) = f(4,1) = 65533
f(5,1) = f(4,65533) = 2^2^...^2 - 3 (ein Turm aus 65533 Zweien!!!)
f(5,2) = §$%*&
Entschuldige bitte die respektlose Zusatzfrage. |
|
