Aus ProgrammingWiki

Inhaltsverzeichnis

1 Primitiv rekursive zahlentheoretische Funktionen
- 1.1 Aufgabe
- 1.2 Lösung
2 Konstante Funktionen
- 2.1 Aufgabe
- 2.2 Lösung
3 Polynom-Funktionen
- 3.1 Aufgabe
- 3.2 Lösung
4 Rechenoperationen
- 4.1 Aufgabe
- 4.2 Lösung
5 Ackermann-Peter-Funktion
- 5.1 Aufgabe
- 5.2 Lösung
6 Sudan-Funktion
- 6.1 Aufgabe
- 6.2 Lösung

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\ \dot{-}\ 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

$P(0)=C_0^0 = 0$

$P(S(n))=g(n,P(n)) = U_1^2(n,P(n)) = n$

Potenzfunktion:

$pot(0,a) = C_1^1(a) = 1$

$pot(S(x),a) = g(x,pot(x,a),a) = mul(U_2^3(x,pot(x,a),a), U_3^3(x,pot(x,a),a)) = mul(pot(x,a),a)$

Fakultät:

$fak(0) = C_1^0 = 1$

$fak(S(n))= g(n, fak(n)) = mul(S(n), U_2^2(n,fak(n)) = mul(S(n),fak(n))$

Monus-Operation:

$monus(0,x)=U_1^1(x)=x$

$monus(S(y),x)=P(U_2^3(y,monus(y,x),x))$

Abstandsfunktion:

$dist(x,y) = add(monus(U_1^2(x,y),U_2^2(x,y)),monus(U_2^2(x,y),U_1^2(x,y))) = add(monus(x,y),monus(y,x))$

Signum-Funktion:

$signum(0) = C_0^0=0$

$signum(S(n)) = U_2^2(n, signum(n))$

Konstante Funktionen

Aufgabe

Unsere Deﬁnition 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 Deﬁnitionsform, 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

$C_q^r(n_1,n_2,...,n_r)=S_a^2(a,C_0^r(n_1,n_2,...,n_r))$
Die Nachfolgerfunktion S wird a mal auf $C_0^r$ ausgeführt
$S_a^2(0,m)=m$
$S_a^2(S(a),m)=S_a^2(a,S(m))$

Polynom-Funktionen

Aufgabe

Begründen Sie, weshalb Polynome mit natürlichen Koeﬃzienten 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 Deﬁnitionen 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

(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)))))

(op 3 10 2)

Ackermann-Peter-Funktion

Aufgabe

Die AP -Funktion ist eine total berechenbare Funktion, die jedoch nicht primitiv rekursiv ist. Sie ist wie folgt deﬁniert.
$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 eﬃzientere Implementation für AP an, indem Sie herausﬁnden, 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 [1] gefunden werden.

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

(define AP (lambda (nr m) (cond ((= nr 0) (+ m 1)) ((= m 0) (AP (sub1 nr) 1)) (else (AP (sub1 nr) (AP nr (sub1 m)))))))

(AP 3 3)

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$

(define AP# (lambda (nr m) (cond ((= nr 0) (+ m 1)) ((= nr 1) (+ m 2)) ((= nr 2) (- (* m 2) 3)) ((= m 0) (AP (sub1 nr) 1)) (else (AP (sub1 nr) (AP nr (sub1 m)))))))

(AP# 3 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 deﬁniert.
$F_0 (x, y) = x + y$
$F_{n+1} (x, 0) = x, n \geq{} 0$
$F_{n+1} (x, y + 1) = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), n \geq{} 0$
Berechnen Sie $F_1$ und $F_2$ für selbstgewählte Argumente.