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 ==
== 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 ein 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 ==