Ackermannfunktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:12 Di 08.01.2013 | | Autor: | bandchef |
| Aufgabe | | Zeigen Sie mittels vollständiger Induktion, dass $ack(n,m) [mm] \forall [/mm] n,m [mm] \in \mathbb N_0$ [/mm] definiert ist. |
Hi Leute,
ich hab große Probleme mit dieser Aufgabe. Ich hab jetzt aber schon mal die Definition der Ackermannfunktion gefunden:
[mm] $ack(n,m)=\begin{cases} m+1, & \mbox{für } n=0 \\ ack(n-1,1), & \mbox{für } m=0 \mbox{ und } n \geq 1 \\ ack(n-1,ack(n,m-1)), & \mbox{sonst} \end{cases}$
[/mm]
So nun weiß ich, dass ich man ja bei solche Induktionsaufgaben auch immer einen Induktionsanfang benötigt und genau da gehts jetzt schon los. Ich weiß nicht wie ich den richtigen Induktionsanfang setze... Was mach hier stört ist auch einfach, weil die Funktion von zwei Variablen abhängt...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:18 Di 08.01.2013 | | Autor: | fred97 |
> Zeigen Sie mittels vollständiger Induktion, dass [mm]ack(n,m) \forall n,m \in \mathbb N_0[/mm]
> definiert ist.
> Hi Leute,
>
> ich hab große Probleme mit dieser Aufgabe. Ich hab jetzt
> aber schon mal die Definition der Ackermannfunktion
> gefunden:
>
> [mm]ack(n,m)=\begin{cases} m+1, & \mbox{für } n=0 \\ ack(n-1,1), & \mbox{für } m=0 \mbox{ und } n \geq 1 \\ ack(n-1,ack(n,m-1)), & \mbox{sonst} \end{cases}[/mm]
>
>
> So nun weiß ich, dass ich man ja bei solche
> Induktionsaufgaben auch immer einen Induktionsanfang
> benötigt und genau da gehts jetzt schon los. Ich weiß
> nicht wie ich den richtigen Induktionsanfang setze... Was
> mach hier stört ist auch einfach, weil die Funktion von
> zwei Variablen abhängt...
Das macht man mit "doppelter Induktion". Schau mal hier:
http://www.ruhr-uni-bochum.de/lmi/lehre/materialien/ti/vorlesung/ackermann.pdf
FRED
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:49 Di 08.01.2013 | | Autor: | bandchef |
So erstmal Danke für deine Hilfe!
Ich hab nun die ersten drei Seiten durchgelesen und auch verstanden aber auf der vierten Seite, kapiere ich schon das erste nicht.
Die Definition von gerade etwas genauer hingeschrieben:
$ack(0,m) = m+1 [mm] \forall [/mm] m [mm] \geq [/mm] 0$
$ack(n,0) = ack(n-1,1) [mm] \forall [/mm] n [mm] \geq [/mm] 1$
$ack(n,m) = ack(n-1, ack(n,m-1)) [mm] \forall [/mm] n,m [mm] \geq [/mm] 1$
So, gut. Soweit hab ich da noch alles. Aber jetzt kommt in den Folien das hier:
Wir zerlegen ack(n,m) in Scheiben [mm] $Ack_n: \mathbb [/mm] N [mm] \to \mathbb [/mm] N$:
[mm] $Ack_n(m) [/mm] = ack(n,m)$
und schnuppern an [mm] $Ack_0, Ack_1, Ack_2,... [/mm] $
Offensichtlich gilt: [mm] $Ack_0(m) [/mm] = m+1$
Mit Induktion ergibt sich relativ leicht
[mm] $Ack_1(m) [/mm] = m+2$
[mm] $Ack_2(m) [/mm] = 2m+3$
[mm] $Ack_3(m) [/mm] = [mm] 2^{m+3}-3$
[/mm]
Und das kapier ich dann eben schon nicht mehr. Wie komme ich auf diese Formeln? Wie funktioniert das? Ich hab sowas noch nicht gemacht...
|
|
|
| |
|
> Die Definition von gerade etwas genauer hingeschrieben:
>
> [mm]ack(0,m) = m+1 \forall m \geq 0[/mm]
> [mm]ack(n,0) = ack(n-1,1) \forall n \geq 1[/mm]
>
> [mm]ack(n,m) = ack(n-1, ack(n,m-1)) \forall n,m \geq 1[/mm]
>
> So, gut. Soweit hab ich da noch alles. Aber jetzt kommt in
> den Folien das hier:
>
> Wir zerlegen ack(n,m) in Scheiben [mm]Ack_n: \mathbb N \to \mathbb N[/mm]:
>
> [mm]Ack_n(m) = ack(n,m)[/mm]
>
> und schnuppern an [mm]Ack_0, Ack_1, Ack_2,...[/mm]
>
> Offensichtlich gilt: [mm]Ack_0(m) = m+1[/mm]
>
> Mit Induktion ergibt sich relativ leicht
>
> [mm]Ack_1(m) = m+2[/mm]
> [mm]Ack_2(m) = 2m+3[/mm]
> [mm]Ack_3(m) = 2^{m+3}-3[/mm]
>
> Und das kapier ich dann eben schon nicht mehr.
Doch! Hast du irgendetwas versucht? Das liegt eher an fehlenden Durchhaltevermögen.
> Wie komme
> ich auf diese Formeln? Wie funktioniert das?
siehe:
> Mit Induktion ergibt sich relativ leicht...
> Ich hab sowas
> noch nicht gemacht...
Ich habe mich auch noch nie zuvor damit beschäftigt und habe soetwas ähnliches wie eine ausgeprägte Analysis-Phobie.
Aber anstatt aufzugeben würde ich an deiner Stelle mich dahinterklemmen und mal stur nach gutdünken einsetzen:
[mm]Ack_1(m)=ack(1,m)=ack(1-1,ack(1,m-1))=ack(0,ack(1,m-1))=ack(1,m-1)+1=Ack_1(m-1)+1[/mm]
[mm]Ack_1(m-1)=ack(1,m-1)=ack(1-1,ack(1,m-2))=ack(0,ack(1,m-2))=ack(1,m-2)+1=Ack_1(m-2)+1[/mm]
...
ergibt
[mm]Ack_1(m)=Ack_1(m-1)+1=Ack_1(m-2)+1+1=\ldots = ack(0,1)+m=2+m=m+2[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:07 Di 08.01.2013 | | Autor: | bandchef |
Für eine Analysis-Phobie sieht das aber ziemlich professionell aus:
$ [mm] Ack_1(m)=ack(1,m)=ack(1-1,ack(1,m-1))=ack(0,ack(1,m-1))\red{=}ack(1,m-1)+1=Ack_1(m-1)+1 [/mm] $
Was ich allerdings bei deiner Umformung nicht kapiere ist der Schritt vor und nach dem rotmarkierten "=". Die äußere Funktion vor dem roten "=" ergibt ja sowas wie ack(0, m) was ja laut Definition m+1 ist. Wie aber kommt man dann zu ack(1,m-1)+1?
Edit: Ah, jetz glaub ich hab ich's geschnallt: Die äußere Funktion ergibt das +1 und die innere Funktion repräsentiert das m. Ich denke so ist es gemeint. Aber: Wie kommt von alleine drauf, dass das "," dass die zwei Argumente der äußeren Funktion ein "+" bedeuten?
|
|
|
| |
|
> [mm]Ack_1(m)=ack(1,m)=ack(1-1,ack(1,m-1))=ack(0,ack(1,m-1))\red{=}ack(1,m-1)+1=Ack_1(m-1)+1[/mm]
>
> Was ich allerdings bei deiner Umformung nicht kapiere ist
> der Schritt vor und nach dem rotmarkierten "=". Die
> äußere Funktion vor dem roten "=" ergibt ja sowas wie
> ack(0, m) was ja laut Definition m+1 ist. Wie aber kommt
> man dann zu ack(1,m-1)+1?
>
> Edit: Ah, jetz glaub ich hab ich's geschnallt:
Ist die Frage noch von Interesse?
> Die äußere
> Funktion ergibt das +1 und die innere Funktion
> repräsentiert das m.
aus deinem eigenem Post geht hervor:
[mm] ack(0,m) = m+1 \forall m \geq 0 [/mm]
> Ich denke so ist es gemeint. Aber:
> Wie kommt von alleine drauf, dass das "," dass die zwei
> Argumente der äußeren Funktion ein "+" bedeuten?
Man setzt doch wirklich nur stur
[mm] ack(0,m) = m+1 \forall m \geq 0 [/mm]
[mm] ack(n,0) = ack(n-1,1) \forall n \geq 1 [/mm]
[mm] ack(n,m) = ack(n-1, ack(n,m-1)) \forall n,m \geq 1 [/mm]
und hofft, dass es ein baldiges Ende findet.
|
|
|
| |
|
... ein baldiges Ende.  Ohja, wie war, wie war.
Ich hab jetzt mal noch beispielhaft das hier geschrieben:
[mm] $Ack_1(m-2) [/mm] = ack(1,m-2) = ack(1-1, ack(1,m-2-1))=ack(0,ack(1,m-3)) = [mm] ack(1,m-3)+1=Ack_1(m-3)+1$
[/mm]
Ich denke, das sollte soweit stimmen.
Jetzt noch kurz zum eigentlichen Ergebnis:
[mm] $Ack_1(m) [/mm] = [mm] Ack_1(m-1)\red{+1} [/mm] = [mm] Ack_1(m-2)+1\red{+1} [/mm] = [mm] Ack_1(m-3)+1+1\red{+1} [/mm] = ...$
Diese rot markierten "+1" kommen aus der Erfahrung der Induktion hinzu, oder? Wenn ich bei der ersten Berechnung von [mm] $Ack_1(m)$ [/mm] am Schluss ein "+1" bekommen hab, dann muss ich bei der Berechnung von [mm] $Ack_1(m-1)$ [/mm] ein weiteres "+1" bekommen? Wenn man aber das berechnete Ergebnis von [mm] $Ack_1(m-1)$ [/mm] anschaut, dann sieht man, dass man wieder nur ein "+1" bekommt.
Die Frage präziser: Woher kommt dann das "+1+1" bzw. "+1+1+1" bei der eigentlichen Induktion?
Was ich auch noch nicht ganz verstehe ist der Schluss dieser Gleichung:
$... = ack(0,1)+m=2+m=m+2 $
Wie kommst du drauf? Für ack(0,1) gibts kein Ergebnis in der Definition und woher kommt das "+m"? Nunja, ack(0,m) = m+1. Muss ich also nun jetzt noch [mm] $Ack_0(1)$ [/mm] berechnen? Oh, jetzt ist es mir auch wieder aufgefallen: $ack(0,1) = 1+1 = 2$ Gut jetzt weiß ich woher das Ergebnis am Schluss kommt, aber immer noch nicht wie ich von $ [mm] Ack_1(m) [/mm] = [mm] Ack_1(m-1)\red{+1} [/mm] = [mm] Ack_1(m-2)+1\red{+1} [/mm] = [mm] Ack_1(m-3)+1+1\red{+1} [/mm] = ... $ auf $ack(0,1)+m$ komme...
Als nächstes hab ich noch das hier probiert:
[mm] $Ack_2(m) [/mm] = ack(2,m) = ack(2-1, ack(2,m-1)) = ack(1, ack(2,m-1)) = ack(1-1, ack(1,ack(1,m-1)) =$
$= ack(1, ack(1,m-1))+1 = ack(1-1,ack(1,m-1)) +1 = ack(1,m-1)+1+1 =$
$= ack(1-1,ack(1,m-1))+1+1 = ack(0,ack(1,m-1))+1+1 = ack(1,m-1) +1+1+1 = [mm] Ack_2(m-1)+3$
[/mm]
Nun folgt:
[mm] $Ack_2(m) [/mm] = [mm] Ack_2(m-1)+1 [/mm] = [mm] Ack_2(m-2)+1+1 [/mm] = ... = ack(2,1) = ...?$
So und jetzt beißt's aus...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Do 10.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
