µ-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;}\\ \text{n.\,d.} & \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 = 0
   

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

h_i=\mu f_i(x,y)= \begin{cases} \text{das kleinste }k \in \mathbb{N}_0 \text{, mit }f_i(k,x,y) = 0 & \text{, wenn}\\ & \text{(1) so ein k existiert und}\\ & \text{(2) }f_i(l,x,y) \text{ f\"ur alle }l \leq k \text{ definiert ist;}\\ \text{n.\,d.} & \text{, sonst} \end{cases}

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

2. f_2(k,m,n) = (n - k * m + 1) * (2 * signum(m) - 1) - 1