BuK-Übung10 G1

Aus ProgrammingWiki
< BuK < IIm10
Archivierte Version vom 2011-06-17T07:02:24+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))