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: | 18:22 Sa 21.11.2009 | | Autor: | stefan00 |
Sei [mm] $g(x,0):=1=c_1^{(2)}(x,y)$
[/mm]
$g(x,y+1):=g(x,y) [mm] \cdot x^2=m(g(x,y),x^2)$
[/mm]
Da die Funktion $g$ sich auf (1) und (5) zurückführen lassen kann, ist $g(x,y)$ auch primitiv-rekursiv, also $g [mm] \in [/mm] PRK$.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 So 22.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
