Aus ProgrammingWiki

Inhaltsverzeichnis

1 µ-rekursive zahlentheoretische Funktionen

µ-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}$

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

Lösung

$h_1 = \begin{cases} 1, &\text{wenn }x\text{ ungerade};\\ 0, &\text{sonst} \end{cases}$
$h_2 = x^2$
$h_3 = 0$

Aufgabe

Ermitteln Sie für die im Folgenden gegebenen Funktionen gleichwertige Vorschriften nach dem Deﬁnitionsschema 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$

BuK-Übung11 G2

Aus ProgrammingWiki

Inhaltsverzeichnis

µ-rekursive zahlentheoretische Funktionen

Aufgabe

Lösung

Aufgabe

Lösung

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge