µ-rekursive zahlentheoretische Funktionen

Aufgabe

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

Lösung

1. h_1 = \begin{cases} 1, &\text{wenn }x\text{ ungerade};\\ \text{n.\,d.}, &\text{sonst} \end{cases}

2. h_2 = x^2

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

Aufgabe

Ermitteln Sie für die im Folgenden gegebenen Funktionen gleichwertige Vorschriften nach dem Definitionsschema für µ-rekursive Funktionen.
1. 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}
2. 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}

Lösung