primitiv rekursive Funktionen

Neue Frage »

Lilly Auf diesen Beitrag antworten »
primitiv rekursive Funktionen
Hallo,

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
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 ^^
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?
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.
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
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von SirJective
Die erste bekannte nicht primitiv rekursive Funktion, die trotzdem rekursiv ist, ist die Ackermann-Funktion.


Was heisst denn hier "die erste"?

Gruß vom Ben
 
 
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

Zitat:
1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv ist. [...] Im gleichen Jahr konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928. Diese Funktion wird heute ihm zu Ehren Ackermannfunktion genannt. Die Ackermannfunktion kann also von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv.

1955 konstruierte Rózsa Péter eine vereinfachte Version, die den gleichen Dienst erweist. Diese Funktion, gelegentlich auch als Ackermann-Péter-Funktion bezeichnet, wird heute vorwiegend benutzt.


Diese von Péter beschriebene Funktion (oder eine weitere Variante) wird heute als Ackermann-Funktion bezeichnet.

Gruss,
SirJective
Ben Sisko Auf diesen Beitrag antworten »

Aha, "die erste" war also historisch gemeint. Das war mir nicht klar.
Danke SirJective.

Gruß vom Ben
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
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »