BuK-Übung10 G1

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

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