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 Nullfunktionen als Basisfunktionen. Manche Quellen nehmen alternativ die konstanten Funktionen als Basisfunktionen auf.
Zeigen Sie mit unserer Definitionsform, dass die konstanten Funktionen <math>C_q^r : \mathbb{N}_0^r \rightarrow \mathbb{N}_0</math> ,
mit <math>C_q^r(n_1 , n_2 , \dots , n_r ) = q</math>, primitiv rekursiv sind.

==Lösung==
Die konstanten Funktionen lassen sich mit Hilfe der Projektionsfunktion darstellen.<br/>
<math>C_q^r(n_1 , n_2 , \dots , n_r ) = q = U_0^{r+1}(q, n_1 , n_2 , \dots , n_r )</math><br/>
Sie sind daher primitiv rekursiv.

=Polynom-Funktionen=
==Aufgabe==
Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.
Beispiel: <math>p(n) = a*n^2 + b*n + c</math>.

==Lösung==
Die Polynome enthalten die Operationen Addition, Multiplikation und Potenz. Da die Operationen primitiv rekursiv sind, sind auch Polynome primitiv rekursiv.

<language>Scheme</language>
=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==
<code id="4dfdf93231861">
(define add1
  (lambda (n) (+ n 1)))

(define sub1
  (lambda (n)
    (if (= n 0)
        0
        (- n 1))))

(define op
  (lambda (nr m n)
    (cond ((= nr 0) (add1 m))
          ((and (= nr 1) (= m 0)) n)
          ((and (= nr 2) (= m 0)) 0)
          ((= m 0) 1)
          (else (op (sub1 nr) (op nr (sub1 m) n) n)))))
</code>
<run id="4dfdf932318ca">(op 3 10 2)</run>

=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==