Ackermann-Berechenbar < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:39 Mi 13.05.2015 | | Autor: | mariem |
Hallo,
zeigt man folgenderweise dass die Ackermann-Funktion berechenbar ist?
Die Ackermann-Funktion ist durch die folgenden Regeln definiert:
Regel 1: A(0, y)=y+1
Regel 2: A(x+1, 0)=A(x, 1)
Regel 3: A(x+1, y+1)=A(x, A(x+1, y))
Es folgen folgende 3 Punkte:
1. Nach jedem Schritt in der Auswertung von A(x, y) folgt entweder eine natürliche Zahl oder ein verschachtelter Ausdruck in der Form [mm] A(w_1, A(w_2, A(w_3, \dots A(w_{k-1}, w_k) \dots [/mm] )))
2. Genau eine Regel ist an jedem Schritt anwendbar.
3. Egal welche Regel man anwendet, sie muss an das rechteste A des verschachtelten Ausdruck angewendet werden.
Die Auswertung muss nach einer endlichen Anzahl von Schritten beenden:
Satz:
Für jede Auswahl der natürlichen Zahlen x und y kann der Ausdruck A(x, y) nach eine endliche Anzahl von Anwendunden der Regeln 1,2,3 zu eine natürliche Zahl reduziert werden.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:02 Fr 15.05.2015 | | Autor: | tobit09 |
Hallo mariem!
> zeigt man folgenderweise dass die Ackermann-Funktion
> berechenbar ist?
>
> Die Ackermann-Funktion ist durch die folgenden Regeln
> definiert:
>
> Regel 1: A(0, y)=y+1
>
> Regel 2: A(x+1, 0)=A(x, 1)
>
> Regel 3: A(x+1, y+1)=A(x, A(x+1, y))
>
>
> Es folgen folgende 3 Punkte:
>
> 1. Nach jedem Schritt in der Auswertung von A(x, y) folgt
> entweder eine natürliche Zahl oder ein verschachtelter
> Ausdruck in der Form [mm]A(w_1, A(w_2, A(w_3, \dots A(w_{k-1}, w_k) \dots[/mm]
> )))
>
> 2. Genau eine Regel ist an jedem Schritt anwendbar.
>
> 3. Egal welche Regel man anwendet, sie muss an das
> rechteste A des verschachtelten Ausdruck angewendet werden.
>
>
> Die Auswertung muss nach einer endlichen Anzahl von
> Schritten beenden:
>
> Satz:
> Für jede Auswahl der natürlichen Zahlen x und y kann der
> Ausdruck A(x, y) nach eine endliche Anzahl von Anwendunden
> der Regeln 1,2,3 zu eine natürliche Zahl reduziert werden.
Zeigen willst du die intuitive Berechenbarkeit der Ackermann-Funktion, also dass ein Algorithmus existiert, der zu gegebenen natürlichen Zahlen x und y den Wert A(x,y) liefert.
Die Existenz von einem Algorithmus zeigt man am besten, indem man einen angibt.
Diese Angabe eines Algorithmus' fehlt mir bei deinen Ansätzen.
Meinen von Schöning (leicht angepasst) übernommenen Ansatz zum Nachweis der intuitiven Berechenbarkeit der Ackermann-Funktion habe ich dir bereits in dieser Antwort geschrieben (ganz unten).
Dass der dort angegebene rekursive Algorithmus im Falle des Terminierens das korrekte Ergebnis liefert, ist klar.
Nur dass er tatsächlich terminiert, muss man sich durch eine Doppelinduktion klar machen.
Viele Grüße
Tobias
|
|
|
|
