Beweis primitiver Rekursion < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Die Geradefunktion evn : N → N
evn(n)=1 falls n gerade
evn(n)=0 falls n ungerade
Dazu benutzt werden dürfen:
Addition, Multiplikation, modifizierte Subtraktion, absolute Differenz, Signum, Kosignum (sind alle primitiv rekursiv) |
Hallo,
Ich verstehe einfach diese primitive Rekursion nicht.
Bei einer vermeintlich einfachen Aufgabe wie der oben angegebenen hänge ich schon.
Wie weise ich das nach?
Ich will es mal methodisch angehen:
Es gibt drei "Standardfunktionen" die primitiv rekursiv sind:
1.) Konstante funktionen: f(a,b) = K (k ist aus N)
2.) Projektionsfunktionen: f(a,b) = a
3.) Die Nachfolgerfunktion s: s(a) = a+1
(in meiner Aufgabe habe ich noch weitere Funktionen gegeben, die als primitiv rekursiv benutzt werden dürfen)
Dann gibt es zwei Methoden
1.) Einsetzungs-/Kompositionsschema
2.) Primitive Rekursionsschema
mit denen neue Funktionen aus den Standardfunktionen "gebaut" werden können...Richtig so weit?
Also wie das primitive Rekursionsschema funktioniert meine ich zu verstehen.
Wenn man zwei Funktionen hat:
g: [mm] N^k [/mm] -> N und h: [mm] N^k+2 [/mm] -> N, dann ist die folgende Funktion auch primtiv rekursiv:
f: [mm] N^k+1
[/mm]
f(0, x) = g(x)
f(n+1, x) = h( f(n, x), n, x)
Wenn ich bei meiner Aufgabe nun dieses Schema nehmen und zwei Funktionen g und h finde, die die Funktion berechnen, dann ist das bereits der Beweis, oder?
Ein Beispiel hatte ich mit der Additions-Funktion:
Da nehmen wir zuerst das Schema:
add(0, x) = g(x)
add(n+1, x) = h(add(n, x), n, x)
g(x) ist eine Projektion, nämlich: g(x) = x. Die Projektion gehört zu den Stammfunktionen also ist g(x) primitiv rekursiv.
h ist eine Komposition aus einer Projektion und der Nachfolgerfunktion, nämlich:
h(a, b, c) = [mm] s(\pi^{3}_{1}(a, [/mm] b, c)
im Beispiel:
h( add(n, x), n, x) = s( [mm] \pi^{3}_{1} [/mm] ( add(n, x), n, x) )
Man kann h dann auch kürzer schreiben als:
s(a), im Beispiel also: s(add(n,x).
Also ist die Addition:
add(0, x) = x
add(n+1, x) = s(add(n, x))
Ich habe für den Beweis nun das primitive Rekurssionsschema, und das Kompositionsschema benutzt.
Gibt es auch Beweise in denen nur das Kompositionsschema benutzt wird, oder gehören die beiden Schemata immer zusammen?
Mein Ansatz für die Aufgabe (Gerade-funktion):
env(n) = 1 falls n gerade
env(n) = 0 falls n ungerade
Primitives Rekursionsschema (ich wähle k = 0, das ist ein Spezialfall):
env(0) = konstante
env(n+1) = h(env(n), x)
Naja, und jetzt weiß ich halt nicht wie man mittels Rekursion herausfinden kann ob eine Zahl gerade ist oder nicht. Zumindest nicht wenn ich nur so wenig Möglichkeiten habe.
Ich hab mir überlegt es evt. so zu machen:
env(0) = 1
env(1) = 0
env(2) = 1
env(n+1) = sub(env(n), 2)
h wäre dann sub.
Mal ungeachtet dessen dass dies nicht funktioniert für die Geradefunktion: Wäre das theoretisch richtig? Also vom Anwenden der Regeln für primitive Rekursion? Ich habe halt mehr als einen konstanten Fall.
Naja, ich mach dann mal Schluß an dem Punkt.
Danke schonmal an alle die bis hier unten gelesen haben... ;)
|
|
| |
|
| Aufgabe | Die Potenzierfunktion hoch : N × N → N
(x, n) → [mm] x^n
[/mm]
Hinweis: das Rekursionsschema verlangt die Rekursion im ersten Argument. Zeigen Sie
zunächst, dass die Funktion mit dem Kompositionsschema auf eine Hilfsfunktion mit
vertauschten Argumenten zurückgeführt werden kann: hoch(x, n) = potenz (n, x). Definieren Sie dann diese Hilfsfunktion. |
Hallo,
Die zweite Aufgabenstellung. Ich denke den ersten Teil habe ich.
Ich soll zunächst mal zeigen, dass ich mit dem Kompositionsschema von hoch(x, n) auf potenz(n, x) komme. Das mache ich mal so:
hoch(x, n) = potenz( [mm] \pi_{2}^{2}(x, [/mm] n), [mm] \pi_{2}^{1})
[/mm]
Das sollte korrekt sein, da ich die Projektionsfunktion ja nutzen darf. Potenz ist also hoch o [mm] \pi [/mm] (?) oder ist das dann hoch o [mm] \pi_{2}^{2} [/mm] o [mm] \pi_{2}^{1} [/mm] ?
Auf jeden Fall muss ich dann zeigen, dann potenz(n, x) mit potenz(n,x) = [mm] x^{n} [/mm] primitiv rekursiv ist.
Das Rekursionsschema:
potenz(0, x) = g(x) = 1 = const.
potenz(n+1, x) = h( potenz(n, x), n, x )
Die Frage ist nun was h ist...?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Do 01.10.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:20 Do 01.10.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
