BuK/IIm10/BuK-Übung10 G2

Wiki-Quelltext dieser Seite.

=Primitiv rekursive zahlentheoretische Funktionen=
==Aufgabe==
Weisen Sie nach, dass die folgenden zahlentheoretischen Funktionen primitiv rekursiv
sind. Dabei dürfen Sie bereits auf das Ergebnis der folgenden Aufgabe zurückgreifen.<br/>

• Vorgängerfunktion:
<math>P(n) =\begin{cases}
0, &\text{wenn }n = 0;\\
n-1, &\text{sonst}
\end{cases}</math><br/>

• Potenzfunktion: 
<math>pot(x,a) =a^x</math><br/>

• Fakultät: 
<math>fak(n) = n!</math><br/>

• Monus-Operation: 
<math>monus(x,y) = x - y = \begin{cases}
0, &\text{wenn }x\leq{}y;\\
x-y, &\text{sonst}
\end{cases} </math><br/>

• Abstandsfunktion: 
<math>dist(x,y) = |x - y|</math><br/>

• Signum-Funktion: 
<math>signum(n) =\begin{cases}
0, &\text{wenn }n = 0;\\
1, &\text{sonst}
\end{cases}</math><br/>

==Lösung==

• Vorgängerfunktion:<br/>
<math>P(0) = 0</math><br/>
<math>P(S(n)) = n</math>

• Potenzfunktion:<br/>
<math>pot(0,a) = 1</math><br/>
<math>pot(S(x),a) = mul(pot(x,a),a)</math><br/>

• Fakultät:<br/>
<math>fak(0) = 1</math><br/>
<math>fak(S(n)) = mul(fak(n),S(n))</math><br/>

• Monus-Operation: <br/>
<math>monus(x,0) = x</math><br/>
<math>monus(0,y) = 0</math><br/>
<math>monus(S(x),y) = monus(x,P(y))</math><br/>

• Abstandsfunktion:<br/>
<math>dist(x,0) = x</math><br/>
<math>dist(0,y) = y</math><br/>
<math>dist(S(x),y) = dist(x,P(y))</math><br/>

• Signum-Funktion:<br/>
<math>signum(0) = 0</math><br/>
<math>signum(S(n)) = 1</math><br/>

=Konstante Funktionen=
==Aufgabe==
Unsere Definition der Menge der primitiv rekursiven Funktionen verwendet die Nullfunk-
tionen als Basisfunktionen. Manche Quellen nehmen alternativ die konstanten Funktio-
nen als Basisfunktionen auf.
Zeigen Sie mit unserer Definitionsform, dass die konstanten Funktionen Cq : N0 r → N0 ,
mit Cq (n1 , n2 , . . . , nr ) = q, primitiv rekursiv sind.

==Lösung==

=Polynom-Funktionen=
==Aufgabe==
Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.
Beispiel: p(n) = an2 + bn + c.

==Lösung==

=Rechenoperationen=
==Aufgabe==
Folgen Sie dem Schema der rekursiven Definitionen der elementaren binären Rechenoperrationen (Addition (1), Multiplikation (2), Potenzieren (3), ...) und entwickeln Sie eine
entsprechende Scheme-Prozedur op. Verwenden Sie add1 für die Nachfolger- und sub1
für die Vorgängerfunktion. Aufrufbeispiel: (op 3 10 2) liefert 1024.

==Lösung==

=Ackermann-Peter-Funktion=
==Aufgabe==
Die AP -Funktion ist eine total berechenbare Funktion, die jedoch nicht primitiv rekursiv
ist. Sie ist wie folgt definiert.
AP (0, m) = m + 1
AP (nr, 0) = AP (nr − 1, 1)
AP (nr, m) = AP (nr − 1, AP (nr, m − 1))
Füllen Sie die folgende Tabelle aus, soweit es eben geht.

<br/>
Geben Sie eine effizientere Implementation für AP an, indem Sie herausfinden, wie sich
die Tabelleneinträge in Zeile i aus denen in Zeile i−1 gewinnen (ablesen) lassen. Benutzen
Sie außerdem memoizing.

==Lösung==

=Sudan-Funktion=
==Aufgabe==
Der rumänische Mathematiker Gabriel Sudan (14.04.1899 - 22.06.1977) – wie Ackermann
ebenfalls ein Schüler von David Hilbert – hat 1927 eine total berechenbare jedoch nicht
primitiv rekursive Funktion publiziert. Sie ist folgendermaßen definiert.
F0 (x, y) = x + y
Fn+1 (x, 0) = x, n ≥ 0
Fn+1 (x, y + 1) = Fn (Fn+1 (x, y), Fn+1 (x, y) + y + 1), n ≥ 0
Berechnen Sie F1 und F2 für selbstgewählte Argumente.

==Lösung==