Aus ProgrammingWiki

Primitiv rekursive zahlentheoretische Funktionen

Aufgabenstellung

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 & sonst \end{cases}$
Potenzfunktion $pot(x,a)=a^x$
Fakultät $fak(n)=n!$
Monus-Operation $x\dot{-}y=\begin{cases} 0 & ,\text{wenn } x \leq y\\ x-y & sonst \end{cases}$
Abstandsfunktion $|x-y|$
Signum-Funktion $signum(n)$

Lösung

Vorgängerfunktion:

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

$P(n+1)=P(S(n))=U_1^2(n,P(n))=n$

Potenzfunktion:

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

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

Fakultät:

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

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

Monus-Operation:

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

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

Abstandsfunktion:

$ab(x,y) = add(U_2^2(mon(y,x),mon(x,y)), U_1^2(mon(y,x),mon(x,y)))$

Signum-Funktion:

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

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

Konstante Funktionen

Aufgabenstellung

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 \mapsto \mathbb{N}_0^r$ , mit $C_q^r(n_1,n_2,....,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 Funktion S wird a-mal aufgerufen.)

$S_a^2(0,m)=m$

$S_a^2(S(a),m)=S_a^2(a,S(m))$

Beispiel: $S_a^2(3,10)=S_a^2(2,11)=S_a^2(1,12)=S_a^2(0,13)$

Polynom-Funktionen

Aufgabenstellung

Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.

Beispiel: $p(n)=an^2+bn+c$

Lösung

Es kann gezeigt werden, dass die Addition, die Multiplikation und die Potenzfunktion primitiv-rekursiv sind. Die Polynom-Funktion kann durch Verwendung dieser drei Funktionen durch Substitution und Rekursion gebildet werden. Da dies möglich ist und die Funktionen wie bereits erwähnt primitiv-rekursiv sind, ist auch die Polynom-Funktion primitiv-rekursiv.

Rechenoperationen

Aufgabenstellung

Folgen Sie dem Schema der rekursiven Deﬁnitionen der elementaren binären Rechenoperationen (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 add (lambda (a b) (cond ((= 0 a) b) (else (add1 (add (sub1 a) b))))))

(add 10 2)

(define mult (lambda (a b) (cond ((= 0 a) 0) (else (add (mult (sub1 a) b) b)))))

(mult 2 3)

(define pot (lambda (x a) (cond ((= 0 x) 1) (else (mult (pot (sub1 x) a) a)))))

(pot 3 2)

(define op (lambda (nr a b) (cond ((= nr 1) (add a b)) ((= nr 2) (mult a b)) ((= nr 3) (pot a b)) (else "Die Operationsnummer ist zu groß!"))))

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

Lösung

Aufgabe

Geben Sie eine effizientere 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

(define ack (lambda (n m) (if (= n 0) (+ m 1) (if (= m 0) (ack (- n 1) 1) (ack (- n 1) (ack n (- m 1)))))))

(ack 3 4)

Hier die Ackermann-Peter-Funktion mit Memoizing.

(define nimm-oder-berechne (lambda (fkt n m tabelle) (let ([resultat (getprop tabelle (+(* n 100000) m))]) (if resultat resultat (let ([res (fkt n m)]) (putprop tabelle (+(* n 100000) m) res) res))))) (define ack-mem (lambda (n m) (if (= n 0) (+ m 1) (if (= m 0) (nimm-oder-berechne ack-mem(- n 1) 1 'acks) (nimm-oder-berechne ack-mem(- n 1) (nimm-oder-berechne ack-mem n (- m 1) 'acks) 'acks)))))

(ack-mem 5 0)

Sudan-Funktion

Aufgabenstellung

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.

$\begin{array}{ccc} F_0(x,y) & = & x+y\\ F_{n+1}(x, 0) & = & x, n \geq 0\\ F_{m+1}(x, y+1) & = & F_n(F_{n+1}(x, y), F_{n+1}(x, y) + y + 1), n \geq 0 \end{array}$

Berechnen Sie $F_1$ und $F_2$ für selbstgewählte Argumente.

Lösung

(define sudan (lambda (n x y) (cond ((= 0 n) (+ x y)) ((= 0 y) x) (else (sudan (sub1 n) (sudan n x (sub1 y)) (+ y (sudan n x (sub1 y))))))))

(sudan 1 0 6)

(sudan 2 1 2)

BuK-Übung10 G1

Aus ProgrammingWiki

Inhaltsverzeichnis

Primitiv rekursive zahlentheoretische Funktionen

Aufgabenstellung

Lösung

Konstante Funktionen

Aufgabenstellung

Lösung

Polynom-Funktionen

Aufgabenstellung

Lösung

Rechenoperationen

Aufgabenstellung

Lösung

Ackermann-Peter-Funktion

Aufgabe

Lösung

Aufgabe

Lösung

Sudan-Funktion

Aufgabenstellung

Lösung

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge