µ-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.

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;}\\ undefiniert & \text{, sonst} \end{cases}

1. h_1: f_1(n,x) = x\ mod\ 2 - n
2. h_2: f_2(n,x) = x^2 - n
3. h_3: f_3(n,x) = n^2 - x

Lösung

1. h_1 = \begin{cases} 1, &\text{wenn }x\text{ ungerade};\\ 0, &\text{sonst} \end{cases}
2. h_2 = x^2
3. h_3 = \begin{cases} 0, &\text{wenn }x=0;\\ \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

1. f(i,x,y) = signum(y-x)*prime(y)-i
mit prime(p)=\begin{cases} 1, &\text{wenn p eine Primzahl ist};\\ \text{n.\,d.}, &\text{sonst} \end{cases}