primitiv rekursive Funktionen |
08.08.2004, 12:04 | Lilly | Auf diesen Beitrag antworten » | ||
primitiv rekursive Funktionen ich habe ein Problem mit primitiv rekursiven Rekursionen. Was genau sind diese? Hat das was mit der möglichen Iteration zu tun? Und stimmt es dass die Fibonacci Zahlen keine primitive Rekursion bilden? Wenn ja, Warum?? Wäre schön wen mir jemand helfen könnte vlg Lilly |
||||
08.08.2004, 12:52 | Mazze | Auf diesen Beitrag antworten » | ||
also ich hab mir gerade die Definition mal angelesen (vorsicht) Eine Funktion heißt primitiv Rekursiv wenn folgendes gilt f(0,.....) = g(....) f(n+1, .....) = h(f(n),.....) Ich greife direkt das Beispiel aus der Erklärung auf add(0,x) = x (identische Abbildung) add(n+1,x) = s(add(n,x)) (s ist nachfolger) Ach, schau dir am besten den link an ^^ |
||||
08.08.2004, 13:00 | Lilly | Auf diesen Beitrag antworten » | ||
hmm versteh ich immer noch nicht so ganz. Wo genau liegt denn der Unterschied zwischen primitive Rekursiv und nicht primitiv Rekuriv und was wäre dann ein *einfaches* Beispiel für eine nicht primitiv rekursive Funktion? |
||||
08.08.2004, 13:21 | Mazze | Auf diesen Beitrag antworten » | ||
also die Fibunaccizahlen erfüllen das Gleichungssystem nicht es gilt: f(0) = 1 f(n+1)= +(f(n),f(n-1)) das Gleichungssystem beschreibt die Fibunaccifolge allerdings in keinster weise, womit die Folge nicht primitiv rekursiv ist. So wie ich das sehe ist eine primtiv rekursive Funktion eine, die selbst nur aus primitivrekursiven Funktionen besteht. Insgesammt muss das gleichungsystem (wie oben genannt) erfüllt sein und g,h müssen primitiv rekursiv sein. |
||||
08.08.2004, 18:49 | SirJective | Auf diesen Beitrag antworten » | ||
Hallo, ich hab mich bisher noch nicht mit primitiv rekursiven Funktionen beschäftigt, aber ich verstehe die Definition so: Wir setzen f(0) = 1 und müssen primitiv rekursive Funktionen g: N^2 -> N und h: N -> N finden, so dass f(n+1) = g( h(n), n ) erfüllt ist. Ich denk drüber nach, wie diese zwei Funktionen aussehen könnten. Die erste bekannte nicht primitiv rekursive Funktion, die trotzdem rekursiv ist, ist die Ackermann-Funktion. Ob sie dir einfach genug ist, weiß ich nicht. Gruss, SirJective |
||||
08.08.2004, 21:28 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Was heisst denn hier "die erste"? Gruß vom Ben |
||||
Anzeige | ||||
|
||||
09.08.2004, 11:04 | SirJective | Auf diesen Beitrag antworten » | ||
Hallo Ben, ob sie tatsächlich die erste ist, die von irgendjemandem gefunden wurde, kann ich nicht sagen, aber sie ist anscheinend die erste, die es in die Literatur geschafft hat. Ich zitiere aus http://de.wikipedia.org/wiki/Ackermannfunktion
Diese von Péter beschriebene Funktion (oder eine weitere Variante) wird heute als Ackermann-Funktion bezeichnet. Gruss, SirJective |
||||
09.08.2004, 12:20 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Aha, "die erste" war also historisch gemeint. Das war mir nicht klar. Danke SirJective. Gruß vom Ben |
||||
23.09.2004, 11:34 | StS | Auf diesen Beitrag antworten » | ||
HI @all ich werd mich auch mal daran versuchen, zum besseren Verständnis beizutragen: Basisfunktionen: 1. Alle konstanten Funktionen sind primitiv rekursiv. Beispiel: c = 3 2. Alle Projektionen und die identische Abbildung sind primitiv rekursiv. Beispiel: id(x) = x id(x) ist die Identitätsfunktion, die für eine Eingabe x einfach x als Ergbegnis liefert 3. Die Nachfolgerfunktion succ(n) = n + 1 ist primitiv rekursiv Dazu kommen noch: 4. Jede Komposition von primitiv rekursiven Funktionen ist primitiv rekursiv f(x1, ..., xn) = g(h1(x1, ..., xn), ..., hm(x1, ..., xn)) Sind die Funktionen g sowie h1 bis hm primitiv rekursiv, dann gehört auch die Funktion f, die durch Komposition entsteht, wieder der Klasse primitiv rekursiver Funktionen an. Man sagt hierzu, dass f aus g durch Einsetzung von h1,..., hm entsteht. 5. Jede Funktion, die durch primitive Rekursion aus primitiv rekursiven Funktionen entsteht, ist primitiv rekursiv. Primitive Rekursion bedeutet, dass die Definition einer Funktion f darauf basiert, dass ein Wert f(..., y + 1) auf einen Wert f(..., y) zurückgeführt wird. Dies geschieht solange, bis die Auswertung eines Wertes f(..., 0) erfolgt, für den es einen separaten Ausdruck gibt. 4 und 5 zusammengefasst: Alles, was aus primitiv-rekursiven Funktionen zusammengebastelt wird, ist ebenfalls primitiv-rekursiv. So kann man Additionen, Multiplikationen, sogar Polynome oder Fakultäten usw. aus primitiv-rekursiven Funktionen kreieren. Satz 1: Alle primitiv-rekursiven Funktionen sind LOOP-berechenbar Satz 2: Die Ackermann-Funktion ist nicht LOOP-berechenbar Eben aus Satz 1 und 2 folgt, dass die Ackermann-Funktion nicht primitiv-rekursiv ist. StS |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|