Eigenschaften - Ackermann < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 03:11 Mi 06.05.2015 | | Autor: | mariem |
Hallo,
ich will die folgenden Eigenschaften der Ackermann-Funktion beweisen:
1. A(x,y)>y.
2. A(x,y+1)>A(x,y).
3. Wenn [mm] y_2>y_1, [/mm] dann [mm] A(x,y_2)>A(x,y_1). [/mm]
4. A(x+1, y) [mm] \geq [/mm] A(x,y+1).
5. A(x,y)>x.
6. Wenn [mm] x_2>x_1, [/mm] dann [mm] A(x_2, y)>A(x_1, [/mm] y).
7. A(x+2, y)>A(x,2y).
Könnt ihr mir ein Tipp geben wie man die Eigenschaften 3, 6 beweisen kann?
Benutzt man dazu die Eigenschaften 2 bzw. 4?
Aber wie?
Ist der Beweis der Eigenschaft vielleicht folgenderweise?
Vollständige Induktion für .
Induktionsanfang: Für x=0 haben wir [mm] A(0,y_2)=y_2+1>y_1+1=A(0,y_1) [/mm]
Induktionsbehauptung: Wir behaupten dass es für x=n gilt, also [mm] A(n,y_2)>A(n,y_1) [/mm] (I.B)
Induktionsschritt: Wir wollen zeigen dass [mm] A(n+1,y_2)>A(n+1,y_1). [/mm]
Wir kann man weiter machen?
Für die Eigenschaft 5, haben wir folgendes:
Von derEigenschaft 4 haben wir A(x+1, y) [mm] \geq [/mm] A(x,y+1). Also, haben wir A(x,y) [mm] \geq [/mm] A(x-1, y+1) [mm] \geq [/mm] A(x-2, y+2) [mm] \geq \dots \geq [/mm] A(0,x+y)=x+y+1>x.
Aber wie kann man das formell beweisen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:20 Mi 13.05.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
