BuK/IIm10/BuK-Übung11 G2

Wiki-Quelltext dieser Seite.

=µ-rekursive zahlentheoretische Funktionen=
==Aufgabe==
Ermitteln Sie für die im Folgenden gegebenen Funktionen <math>h_i = \mu  f : \mathbb{N}_0 \rightarrow \mathbb{N}_0</math> gleichwertige explizite Vorschriften.


==Lösung==
1. <math>h_1 = \begin{cases}
1, &\text{wenn }x\text{ ungerade};\\
\text{n.\,d.}, &\text{sonst}
\end{cases}</math><br/>

2. <math>h_2 = x^2</math><br/>

3. <math>h_3 = \begin{cases}
1, &\text{wenn }x=1;\\
\text{n.\,d.}, &\text{sonst}
\end{cases}</math><br/>

==Aufgabe==
Ermitteln Sie für die im Folgenden gegebenen Funktionen gleichwertige Vorschriften
nach dem Definitionsschema für µ-rekursive Funktionen.<br/>
1. <math> p(x, y) =\begin{cases}
1, &\text{wenn y eine Primzahl gr\"{o}\ss{}er als x ist};\\
\text{n.\,d.}, &\text{sonst}
\end{cases}
</math><br/>
2. <math> g(m, n) =\begin{cases}
\frac{n}{m}, &\text{wenn } m \neq 0 \text{ und } m\text{ teilt }n;\\
\text{n.\,d.}, &\text{sonst}
\end{cases}
</math><br/>

==Lösung==
1. <math>f(i,x,y) = signum(y-x)*prime(y)-i</math><br/>
mit <math>prime(p)=\begin{cases}
1, &\text{wenn p eine Primzahl ist};\\
\text{n.\,d.}, &\text{sonst}
\end{cases}
</math><br/>