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>

= 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 <math>C_q^r : \mathbb{N}_0^r \mapsto \mathbb{N}_0^r</math>, mit <math>C_q^r(n_1,n_2,....,n_r)=q</math>, primitiv rekursiv sind.
== Lösung ==