\mu-rekursive zahlentheoretische Funktionen

Aufgabenstellung

Ermitteln Sie für die im Folgenden gegebenen Funktionen h_i = \mu f:\mathbb{N}_0 \mapsto \mathbb{N}_0 gleichwertige explizite Vorschriften.

1. 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}
2. 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}
3. 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}

Lösung

Aufgabenstellung

Ermitteln Sie für die im Folgenden gegebenen Funktionen gleichwertige Vorschriften nach dem Definitionsschema für \mu-rekursive Funktionen.

1. p(x,y)= \begin{cases} 1 & \text{, wenn y ein Primzahl gr\"o\ss er als x ist.}\\ n.d. & \text{, sonst} \end{cases}
2. g(m,n)= \begin{cases} \frac{m}{n} & \text{, wenn }m \neq 0 \text{ und m teilt n}\\ n.d. & \text{, sonst} \end{cases}

Lösung