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.

<math>h_i=\mu f_i(x)=
\begin{cases}
\text{das kleinste }n \in \mathbb{N}_0 \text{, mit }f_i(n,x) = 0 & \text{, wenn}\\
& \text{(1) so ein n existiert und}\\
& \text{(2) }f_i(m,x) \text{ f\"ur alle }m \leq n \text{ definiert ist;}\\
\text{n.\,d.} & \text{, sonst}
\end{cases}</math><br/>

# <math>h_1: f_1(n,x) = x\ mod\ 2 - n</math>
# <math>h_2: f_2(n,x) = x^2 - n</math>
# <math>h_3: f_3(n,x) = n^2 - x</math>

==Lösung==
# <math>h_1 = \begin{cases}
1, &\text{wenn }x\text{ ungerade};\\
0, &\text{sonst}
\end{cases}</math>
# <math>h_2 = x^2</math>
# <math>h_3 = 0</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==
<math>h_i=\mu f_i(x,y)=
\begin{cases}
\text{das kleinste }k \in \mathbb{N}_0 \text{, mit }f_i(k,x,y) = 0 & \text{, wenn}\\
& \text{(1) so ein k existiert und}\\
& \text{(2) }f_i(l,x,y) \text{ f\"ur alle }l \leq k \text{ definiert ist;}\\
\text{n.\,d.} & \text{, sonst}
\end{cases}</math><br/>

1. <math>f_1(k,x,y) = 2 * signum(y - x) * prime(y) - signum(S(y) - x) - k</math><br/>
mit <math>prime(p)=\begin{cases}
1, &\text{wenn p eine Primzahl ist};\\
\text{n.\,d.}, &\text{sonst}
\end{cases}
</math><br/>


2. <math>f_2(k,m,n) = (n - k * m + 1) * (2 * signum(m) - 1) - 1</math><br/>