BuK/IIm10/BuK-Übung10 G1

Wiki-Quelltext dieser Seite.

= 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 <math>P(n)= \begin{cases}
0 & ,\text{wenn } n=0\\
n-1 & sonst
\end{cases}</math>
*Potenzfunktion <math>pot(x,a)=a^x</math>
*Fakultät <math>fak(n)=n!</math>
*Monus-Operation <math>x-y=\begin{cases}
0 & ,\text{wenn } x \leq y\\
x-y & sonst
\end{cases}</math>
*Abstandsfunktion <math>|x-y|</math>
*Signume-Funktion <math>signum(n)</math>
== Lösung ==
Vorgängerfunktion:

<math>P(0)=C_0^1=0</math>

<math>P(n+1)=P(S(n))=U_1^2(n,P(n))=n</math>

Potenzfunktion:

<math>pot(0,a) = C_1^1=1</math>

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

Fakultät:

<math>fak(0) = C_1^1=1</math>

<math>fak(S(n))= g(n, fak(n)) = mult(U_1^2(n,fak(n)), U_2^2(n,fak(n))</math>

Monus-Operation:

<math>mon(0,x)=U_1^1(x)=x</math>

<math>mon(S(y),x)=U_2^3(y,mon(y,x),x)</math>

Abstandsfunktion:

<math>ab(x,y) = add(U_2^2(mon(y,x),mon(x,y)), U_1^2(mon(y,x),mon(x,y)))</math>

Signum-Funktion:

<math>signum(0) = C_0^0=0</math>

<math>signum(S(n)) = U_2^2(n, signum(n))</math>