Hyperoperatoren, Ackermann < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:55 Mi 03.04.2013 | | Autor: | quasimo |
| Aufgabe | (Auch für Personen, die mit dem Thema nicht viel am Hut haben geeignet, da ich alle Definitionen dir wir haben nenne)
Definition:Hyperoperatoren (Knuthsche Pfeilnotation)
x [mm] \uparrow^0 [/mm] y = x *y
x [mm] \uparrow^{n+1} [/mm] 0 =1
x [mm] \uparrow [/mm] (y+1) = x [mm] \uparrow^n [/mm] (x [mm] \uparrow^{n+1} [/mm] y)
Definition Ackermann-Peter Funktion
A: [mm] \IN^2 [/mm] -> [mm] \IN
[/mm]
[mm] A_0 [/mm] (x)= x+1
[mm] A_{n+1} [/mm] (0)= [mm] A_n [/mm] (1)
[mm] A_{n+1} [/mm] (x+1) = [mm] A_n (A_{n+1} [/mm] (x))
Proposition:
Es gilt
[mm] A_n (x)=\begin{cases} x+1, & \mbox{falls } n=0\\ x+2, & \mbox{falls } n=1\\(2\uparrow^{n-2} (x+3))-3, & \mbox{sonst} \end{cases} [/mm] |
Bew. der Proposition.
Seien [mm] A_n' [/mm] die Funktionen aus der Proposition. Man überprüft die Rekursionsgleichung problemlos für die angegebenen Lösungen für [mm] A_0', A_1' [/mm] und [mm] A_2' [/mm] . Für n [mm] \ge [/mm] 2 folge die Rekursionsgleichungen aus denen von [mm] \uparrow:
[/mm]
[mm] A_{n+1}' [/mm] (0)= [mm] (2\uparrow^{n-1} [/mm] 3)-3= [mm] (2\uparrow^{n-2} [/mm] 4)-3 = [mm] A_n'(1)
[/mm]
(Beim zweiten "=" haben wir ein Lemma verwendet: 2 [mm] \uparrow^{n+1} [/mm] 3 = 2 [mm] \uparrow^n [/mm] 4 )
[mm] A_{n-1}' [/mm] (x+1) [mm] =(2\uparrow^{n-1} [/mm] (x+4))-3 = [mm] (2\uparrow^{n-2}([2 \uparrow^{n-1} [/mm] (x+3)] -3+3)-3 = [mm] A_n' (A_{n+1}' [/mm] (x))
MEINE FRAGE: [mm] A_{n-1}' [/mm] (x+1) [mm] =(2\uparrow^{n-1} [/mm] (x+4))-3
Wenn ich die Definition verwende, komme ich auf: [mm] A_{n-1}' [/mm] (x+1) [mm] =(2\uparrow^{n-3} [/mm] (x+4))-3
Was wird hier denn noch gemacht, um zu dem ergebnis zu kommen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Fr 05.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
