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.

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

• Potenzfunktion: pot(x,a) =a^x

• Fakultät: fak(n) = n!

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

• Abstandsfunktion: dist(x,y) = |x - y|

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

Lösung

• Vorgängerfunktion:
P(0) = 0

• Potenzfunktion:
pot(0,a) = 1
pot(S(x),a) = mul(pot(x,a),a)

• Fakultät:
fak(0) = 1
fak(S(n)) = mul(fak(n),S(n))

• Monus-Operation:
monus(x,0) = x
monus(0,y) = 0
monus(S(x),y) = monus(x,P(y))

• Abstandsfunktion:
dist(x,0) = x
dist(0,y) = y
dist(S(x),y) = dist(x,P(y))

• Signum-Funktion:
signum(0) = 0
signum(S(n)) = 1

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 C_q^r : \mathbb{N}_0^r \rightarrow \mathbb{N}_0 , mit C_q^r(n_1 , n_2 , \dots , n_r ) = q, primitiv rekursiv sind.

Lösung

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

Polynom-Funktionen

Aufgabe

Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind. Beispiel: p(n) = a*n^2 + b*n + c.

Lösung

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

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)

Füllen Sie die folgende Tabelle aus, soweit es eben geht.
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

Eine halbwegs ausgefüllte Tabelle kann unter http://de.wikipedia.org/wiki/Ackermannfunktion#Wertetabelle gefunden werden.

Die Funktionswerte für nr = 1 werden immer vom Feld rechts oberhalb AP(0,m+1) verwendet. Es ergibt sich:
AP(1, m) = m + 2
Für nr = 2 werden die Funktionswerte AP(1,2*m+1) verwendet. Eingesetzt ergibt sich:
AP(2, m) = 2*m + 3

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