BuK/IIm10/BuK-Übung11 G1

Wiki-Quelltext dieser Seite.

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

# <math>h_1=\mu f(x)=
\begin{cases}
\text{das kleinste }y \in \mathbb{N}_0 \text{, mit }x mod 2 - y = 0 & \text{, wenn}\\
& \text{(1) so ein y existiert und}\\
& \text{(2) }x mod 2 - i = 0 \text{ f\"ur alle }i \leq y \text{ definiert ist;}\\
undefiniert & \text{, sonst}
\end{cases}</math>
# <math>h_2=\mu f(x)=
\begin{cases}
\text{das kleinste }y \in \mathbb{N}_0 \text{, mit }x^2 \dot{-} y = 0 & \text{, wenn}\\
& \text{(1) so ein y existiert und}\\
& \text{(2) }x^2 \dot{-} i = 0 \text{ f\"ur alle }i \leq y \text{ definiert ist;}\\
undefiniert & \text{, sonst}
\end{cases}</math>
# <math>h_3=\mu f(x)=
\begin{cases}
\text{das kleinste }y \in \mathbb{N}_0 \text{, mit }y^2 \dot{-} x = 0 & \text{, wenn}\\
& \text{(1) so ein y existiert und}\\
& \text{(2) }i^2 \dot{-} x = 0 \text{ f\"ur alle }i \leq y \text{ definiert ist;}\\
undefiniert & \text{, sonst}
\end{cases}</math>

== Lösung ==
# <math>h_1=\mu f(x)=
\begin{cases}
0, & \text{wenn } x mod 2 = 0 \text{ (gerade)}\\
1, & \text{wenn } x mod 2 = 1 \text{ (ungerade)}
\end{cases}</math>
# <math>h_2=\mu f(x)= x^2</math>
# <math>h_3=\mu f=
\begin{cases}
1, & \text{wenn }x=1\\
n.d., & sonst
\end{cases}</math>

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

== Lösung ==
# gegeben: <math>prim(y)=\begin{cases}
1, & \text{wenn y Primzahl}\\
0, & \text{sonst}
\end{cases}</math><math>p(x, y)=
\begin{cases}
\text{das kleinste }n \in \mathbb{N}_0 \text{, mit }prim(y) - (x \dot{-} y) * n = 0 & \text{, wenn}\\
& \text{(1) so ein y existiert und}\\
& \text{(2) }prim(y) - (x \dot{-} y) * i = 0 \text{ f\"ur alle }i \leq n \text{ definiert ist;}\\
undefiniert & \text{, sonst}
\end{cases}</math>
# <math>g(m, n)=
\begin{cases}
\text{das kleinste }y \in \mathbb{N}_0 \text{, mit }m - y * n = 0 & \text{, wenn}\\
& \text{(1) so ein y existiert und}\\
& \text{(2) }m - i * n = 0 \text{ f\"ur alle }i \leq y \text{ definiert ist;}\\
undefiniert & \text{, sonst}
\end{cases}</math>