Primitiv-rekursiv < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Es sei [mm] $g:\IN \times \IN \to \IN$ [/mm] definiert durch [mm] $g(x,y):=x^{2 \cdot y}$ [/mm] für alle $x,y [mm] \in \IN$. [/mm] Zeigen Sie, dass f primitiv-rekursiv ist. |
Hallo,
ich darf auf folgende primitiv-rekursive Funktionen zurückgreifen:
1.) [mm] $c_n^{(k)}:\IN^k \to \IN, c_n^{(k)}(x_1,...,x_k):=n$ [/mm] für alle $k,n [mm] \in \IN$ [/mm] (konstante Funktionen).
2.) [mm] $s:\IN^2 \to \IN, [/mm] s(x,y):=x+y$ (Summe).
3.) [mm] $V:\IN \to \IN, [/mm] V(x):=x-1$ (Vorgängerfunktion).
4.) [mm] $d:\IN^2 \to \IN, [/mm] d(x,y):=x-y$ (arithmetische Differenz).
5.) [mm] $m:\IN^2 \to \IN, [/mm] m(x,y):=x [mm] \cdot [/mm] y$ (Multiplikation).
Ich würde in diesem Fall auf die Funktion 5.) und 3.) zurückgreifen, ich kann ja im Prinzip m solange mit sich selbst aufrufen bis y=1 ist, in einem Pascal-Programm kann ich das auch noch gut formulieren, aber wie mache ich das hier, also rein formal?
Vielen Dank für die Hilfe.
Gruß, Stefan.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Do 19.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:37 Fr 20.11.2009 | | Autor: | stefan00 |
$f$ erfüllt die Gleichung $d(x,y)=0$, wenn $y [mm] \geq [/mm] x$ (sonst-Fall) und $d(x,y)>0$, also auch $d(x,y) [mm] \geq [/mm] 1$ und [mm] $d(x,y)\dot{-}(d(x,y)\dot{-}1)=(x\dot{-}y)\dot{-}((x\dot{-}y)\dot{-}1)=1$, [/mm] wenn $x>y$. Sei [mm] $a:=x\dot{-}y\dot{-}1$, [/mm] dann erfüllt $f$ die Gleichungen $d(d(x,y),a)$, für $x>y$, dann ist $f(x,y)=1$ und für $y [mm] \geq [/mm] x$, dann ist $f(x,y)=0$. Wegen Satz 6.2.2 (4) ist somit $f [mm] \in [/mm] PRK$, weil sich $f$ auf $d$ zurückführen lässt.
|
|
|
|
