Primitiv rekursive Funktionen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:42 Do 23.04.2015 | | Autor: | mariem |
Hallo,
die Menge der primitiv rekursiven Funktionen erhält folgende Funktionen:
1) f(x)=c (Konstante)
2) S(x)=x+1 (Nachfolger)
3) [mm] P_n^m(x_1, \dots [/mm] , [mm] x_m)=x_n, [/mm] m [mm] \geq [/mm] n (Projektion)
Wenn die h, [mm] g_1, \dots [/mm] , [mm] g_n: \mathbb{N}_0^m \rightarrow \mathbb{N}_0 [/mm] pimitiv rekursiv sind, dann ist auch die [mm] f(\overline{x})=h(g_1(\overline{x}), \dots [/mm] , [mm] g_n(\overline{x})): \mathbb{N}_0^m \rightarrow \mathbb{N} [/mm] primitiv rekursiv.
Wenn die g: [mm] \mathbb{N}_0^{k-1} \rightarrow \mathbb{N}_0 [/mm] und [mm] h:\mathbb{N}_0^{k+1} \rightarrow \mathbb{N}_0 [/mm] primitiv rekursiv sind, dann ist auch die f: [mm] \mathbb{N}_0^k \rightarrow \mathbb{N}_0
[/mm]
[mm] f(0,\overline{y})=g(\overline{y}) f(x+1,\overline{y})=h(x,f(x,\overline{y}), \overline{y}) [/mm]
primitiv rekursiv.
Eine Menge A [mm] \subseteq \mathbb{N}_0^k [/mm] ist primitiv rekursiv wenn die charkteristische Funktion primitiv rekursiv ist.
Ich soll zeigen dass die folgenden Funktionen und Mengen primitiv rekursiv sind:
- f(x,y)=x+y
- f(x,y)=x [mm] \cdot [/mm] y
- sign [mm] (x)=\left\{\begin{matrix}
1 &\text{ if } x=0\\
0 &\text{ if } x>0
\end{matrix}\right. [/mm]
- x [mm] \dot [/mm] - [mm] y=\left\{\begin{matrix}
x-y &\text{ if } x \geq y\\
0 &\text{ else }
\end{matrix}\right. [/mm]
- [mm] f(x)=\left\{\begin{matrix}
1 & \text{ if } g(x)=0 \\
0 & \text{ if } h(x)=0
\end{matrix}\right. \\ [/mm] g,h: [mm] \mathbb{N}_0\rightarrow \mathbb{N}_0 \text{ primitive recursive and } \forall [/mm] x: g(x) [mm] \cdot [/mm] h(x)=0, g(x)+h(x)>0
- [mm] f(y)=\sum_{x=0}^y [/mm] g(x) [mm] \text{ if } [/mm] g [mm] \text{ is primitive recursive } [/mm]
- [mm] f(y)=\prod_{x=0}^y [/mm] g(x) [mm] \text{ if } [/mm] g [mm] \text{ is primitive recursive } [/mm]
- [mm] \{y \mid \exists x \leq y : x \in A\}, \{y \mid \forall x \leq y : x \in A\} \text{ if } [/mm] A [mm] \text{ is primitive recursive}
[/mm]
Ich habe folgendes gemacht :
- [mm] f(0,y)=P_1^1(y) [/mm]
[mm] f(x+1,y)=S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y)
[/mm]
f(0,y)=0 [mm] (\text{ constant } [/mm] )
f(x+1, [mm] y)=(x+1)\cdot [/mm] y=x [mm] \cdot [/mm] y +1 [mm] =S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y)
[/mm]
- sign(0)=1 ( [mm] \text{ constant } [/mm] )
sign(x+1)=0 [mm] (\text{ constant } [/mm] )
- f(x,y)=x [mm] \dot [/mm] - y [mm] \\ [/mm] f(0,y)=0 [mm] (\text{ constant } [/mm] )
[mm] f(x+1,y)=\left\{\begin{matrix}
x+1-y=(x-y)+1=S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y) &\text{ if } x+1 \geq y\\
0 &\text{ else }
\end{matrix}\right. [/mm]
- [mm] f(0)=\left\{\begin{matrix}
1 & \text{ if } g(0)=0 \\
0 & \text{ if } h(0)=0
\end{matrix}\right. [/mm]
[mm] \Rightarrow [/mm] f(0) [mm] \text{ constant } [/mm]
[mm] f(x+1)=\left\{\begin{matrix}
1 & \text{ if } g(x+1)=0 \\
0 & \text{ if } h(x+1)=0
\end{matrix}\right. [/mm]
[mm] \Rightarrow [/mm] f(x+1) [mm] \text{ constant } [/mm]
- [mm] f(0)=\sum_{x=0}^0 [/mm] g(x)=g(0) primitiv rekursiv
[mm] f(y+1)=\sum_{x=0}^{y+1} g(x)=\sum_{x=0}^y [/mm] g(x) + g(y+1)=f(y)+g(y+1)=sum(f(y),g(y+1))
wobei sum(x,y)x+y
Das ist aber nicht in der Form h(y,f(y)).
[mm] f(0)=\prod_{x=0}^0 [/mm] g(x)=g(0) primitiv rekursiv
[mm] f(y+1)=\prod_{x=0}^{y+1} g(x)=\left (\prod_{x=0}^y g(x) \right [/mm] ) [mm] \cdot [/mm] g(y+1)= f(y) [mm] \cdot [/mm] g(y+1)=prod(f(y), g(y+1))
wobei prod(x,y)=x [mm] \cdot [/mm] y.
Es ist aber nicht in der Form h(y,f(y))
Ist es richtig? Wie zeigt man dass die letzten zwei Mengen primitiv rekursiv sind?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Sa 25.04.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
