BuK-Übung10 G1

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-06-17T07:51:17+00:00. Aktuelle Version

Inhaltsverzeichnis

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-y=\begin{cases} 0 & ,\text{wenn } x \leq y\\ x-y & sonst \end{cases}
  • Abstandsfunktion |x-y|
  • Signume-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(U_1^2(n,fak(n)), U_2^2(n,fak(n))

Monus-Operation:

mon(0,x)=U_1^1(x)=x mon(S(y),x)=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 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 \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) = f(g(n_1),g(n_2),....,g(n_r)) = f(U_1^r(n_1,n_2,...,n_r),U_2^r(n_1,n_2,...,n_r),.....,U_q^r(n_1,n_2,...,n_r))

Polynom-Funktionen

Aufgabenstellung

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

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

Lösung