primitiv rekursive funktionen

Neue Frage »

marin21 Auf diesen Beitrag antworten »
primitiv rekursive funktionen
hallo,
also ich muss erstmal sagen das ich diese frage auch schon auf dem informatik board gestellt habe,wo ich jedoch bisher keine antwort erhalten hab und da sie auch was mit mathe zu tun hat stell ich sie hier einfach nochmal.
wenn das so nicht erlaubt ist tuts mir leid,und ihr koennt es dann ja löschen...

meine frage ist jetzt folgende:
ich soll die ganzzahlige wurzel y=[wurzel(x)] mittels µ-Operator beschreiben,wobei [x]
die größte ganze zahl kleiner gleich x ist.
danach soll ich den µ-Operator beschränken um nachzuweisen das es sich um eine primitiv rekursive Funktion handelt.

mein ansatz war jetzt folgender:[wurzel(x)]=µy{y=wurzel(x) + y=U(x) }
wobei U die Funktion ist welche immer die ziffer vor der kommastelle auswählt.

hab wirklich keine ahnung ob das so richtig ist und wie ich das mache.
wuerd mich ueber hilfe sehr freuen.

danke!
Abakus Auf diesen Beitrag antworten »
RE: primitiv rekursive funktionen
Du verwendest die Wurzelfunktion ja bereits in der Eigenschaft für den -Operator. Da beisst sich also was.

Die Bedeutung deiner Schreibweise in der Menge ist mir nicht genau klar, da können so keine 2 Gleichheitszeichen stehen.

Helfen kann dir hier, dass die Multiplikation h(x, y) := x * y eine primitiv-rekursive Funktion ist. Was du genau mit Beschränken des -Operators meinst, müsstest du mir erklären.

Grüße Abakus smile
martin21 Auf diesen Beitrag antworten »

hallo,
erstmal danke das du mir hilfst.
Ist es den möglich die wurzel nur mittels einer multiplikation darzustellen?
ich hab mal geschaut und definiert ist die wurzel:

das setzt aber doch immer vorraus das ich das ergebnis der wurzel schon kenne ,nämlich die 4 oder nicht?

Wie man das beschränkt ist mir eben auch nicht ganz klar.In meinen Aufzeichnungen haben wir das mittels einer Schranke z gemacht welche wir suchen und die von x abhaengt,es waere also die funktion f(z,x) primitiv rekursiv da ja die µ-rekursiven Fkt. eine Erweiterung der primitiv rekursiven Fkt. sind, und durch die Beschraenkung eben eine primitiv rek. Fkt entsteht.
Wär aber schon erstmal zufrieden wenn ich die ueberhaupt mittels µ-Operator beschrieben bekomme...

mfg
Abakus Auf diesen Beitrag antworten »

Betrachte einmal . Das Minus mit dem Punkt bedeutet dabei die positive Differenz (also die normale Differenz, wenn größer Null; und Null sonst). Diese ist primitiv-rekursiv.

Für welche k wird der obige Ausdruck gleich 0? Das liefert dir dann die Idee für deine Eigenschaft im -Operator bzw. für eine -Rekursion (vielleicht schreibst du dazu mal die ersten Funktionswerte der Funktion auf, die du darstellen sollst).

Danach kannst du überlegen, wie du es primitiv-rekursiv ohne -Operator formulierst (das soll das Beschränken demnach bedeuten).

Grüße Abakus smile
AD Auf diesen Beitrag antworten »

@Abakus

Wenn ich mich nicht täusche, muss es aber ein klein wenig verschoben werden:



Was meinst du?
Abakus Auf diesen Beitrag antworten »

Ja, das passt besser und ist direkt die Bedingung:

.

Mit der Multiplikation h und der Nachfolgerfunktion S wäre das:

.

Grüße Abakus smile
 
 
AD Auf diesen Beitrag antworten »

@Abakus

Wenn du sowas magst, dann ist vielleicht Problem 8 was für dich. smile
Abakus Auf diesen Beitrag antworten »

@ Arthur, marin: Interessant ist, dass in diesem Problem 8 eine Funktion E(x) vorkommt, die tatsächlich Parallelen zum Problem hier durchblicken lässt. Die Sache hat also sogar ihre Anwendungen Big Laugh .

zum 2-ten Teil hier: eine Idee, wie diese Funktion nun ohne unbeschränkte Minimierung mit einer Rekursion hinzukriegen ist, sollte diese Konstruktion (oben mit der Bedingung) auch liefern. Zweckmäßig zur Ideenfindung ist, eine Wertetabelle aufzustellen und sich das Verhalten am Beispiel anzuschauen.

Grüße Abakus smile

EDIT: Text
martin21 Auf diesen Beitrag antworten »

hallo,
ich versteh nicht ganz wieso ihr immer den nachfolger nehmt.
muesste folgendes nicht auch gehen?


macht doch das selbe oder nicht?

schonmal vielen dank fuer die hilfe!
mfg
PS:wie mach ich ein µ in latex?






edit Jochen: hab mal aus mue \mu gemacht smile
martin21 Auf diesen Beitrag antworten »

achja meine wertetabelle sieht folgendermassen aus:

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...25....
y 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4... 5.....
Abakus Auf diesen Beitrag antworten »

Nach deiner Formel wäre:

,

,

.

Deine Wertetabelle nach vorgeschlagener Formel ist ok.

Grüße Abakus smile

PS: das ist ein \mu; wenn du auf den Zitat-Button drückst, kannst du den Code eines Beitrags auch sehen. Als angemeldeter User kannst du deine Beiträge editieren.
Neue Frage »
Antworten »



Verwandte Themen

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