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

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