Aus ProgrammingWiki

Inhaltsverzeichnis

1 -rekursive zahlentheoretische Funktionen

$\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.

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

$h_1=\mu f(x)= \begin{cases} 0, & \text{wenn } x mod 2 = 0 \text{ (gerade)}\\ 1, & \text{wenn } x mod 2 = 1 \text{ (ungerade)} \end{cases}$
$h_2=\mu f(x)= x^2$
$h_3=\mu f=0$

Aufgabenstellung

Ermitteln Sie für die im Folgenden gegebenen Funktionen gleichwertige Vorschriften nach dem Deﬁnitionsschema für $\mu$ -rekursive Funktionen.

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

Lösung

1. gegeben: $prim(y)=\begin{cases} 0, & \text{wenn y Primzahl}\\ 1, & \text{sonst} \end{cases}$

$x<y(x, y)=\begin{cases} 1, & \text{ wenn } x < y\\ 0, & sonst \end{cases}$

$p(x, y)= \begin{cases} \text{das kleinste }n \in \mathbb{N}_0 \text{, mit }prim(y) * x<y(x, y)+ n = 0 & \text{, wenn}\\ & \text{(1) so ein y existiert und}\\ & \text{(2) }prim(y) * x<y(x, y)+ i = 0 \text{ f\"ur alle }i \leq n \text{ definiert ist;}\\ undefiniert & \text{, sonst} \end{cases}$

2. $g(m, n)= \begin{cases} \text{das kleinste }k \in \mathbb{N}_0 \text{, mit }|k*m-n|^{signum(n)} = 0 & \text{, wenn}\\ & \text{(1) so ein y existiert und}\\ & \text{(2) }|i*m-n|^{signum(n)} = 0 \text{ f\"ur alle }i \leq y \text{ definiert ist;}\\ undefiniert & \text{, sonst} \end{cases}$

BuK-Übung11 G1

Aus ProgrammingWiki

Inhaltsverzeichnis

$\mu$ -rekursive zahlentheoretische Funktionen

Aufgabenstellung

Lösung

Aufgabenstellung

Lösung

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge