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. |
|