Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
primitive rekursion - min(x,y)
hi,
habe mich etwas mit der primrek befasst und hoffentlich einiges richtig verstanden. trotzdem kann ich die aufgabe 5)b)ii) aus der klausur vom 7.10.98 nicht loesen:
“zeigen sie, dass die funktion min(x,y), die das minimum von x und y zurueckliefert, berechenbar ist.”
das ginge ja noch irgendwie, wenn auch ziemlich kompliziert! dann kommt aber noch der zusatz:
“verwenden sie dafuer NUR die eingeschraenkte subtraktion sub.”
und das gibt mir den rest! k. a., wie man das so schaffen soll. any suggestions?
versuchs mal mit
sub(x,sub(x y))
und dann halt h(x,y,z) = sub(p31(x,y,z),p33(x,y,z))
verdammt…
WIE zum teufel kommt man auf sowas Geniales?! Ich sollte vielleicht auch öfter im Rommel essen… :bounce:
@eem:
Bist du echt selber draufgekommen? Da überlegt man doch ne halbe Stunde und ob sich des in der Klausur lohnt…
wow, echt krass! ist ja nur ein kleiner ausdruck, aber der hat’s in sich.
grossen respekt @ eem!
Sorry Leute, ich check dieses Zeuch net !
Was ist SUB ? Was ist SUCC ?? :wand:
succ ist die successor-funktion (eine der primrek. grundfkt.), die den nachfolger von ihrem parameter berechnet
sub ist die eingeschraenkte subtraktion, die bei positivem ergebnis eben das ergebnis ausgibt und bei negativem ergebnis die 0 ausgibt, weil alle primrek. funktionen nur auf den natuerlichen zahlen mit 0 definiert sind.
soweit die erklaerung zu den funktionen. allerdings glaube ich nicht, dass dir das viel zum verstaendnis der prim. rek. generell bringt. les am besten nochmal das kapitel im skript durch und die entsprechenden uebungen mit den loesungen. bei speziellen fragen kannst du das aber natuerlich gerne hier tun :).
Ahja, SUB is die Subtraktion x-y, die für x>y x-y liefert und für x<=y isses 0.
SUCC is die wichtigste PrimRek Funktion überhaupt, des is der Nachfolger der “Zahl”, die in Klammer dahinter steht, also SUCC (c0) is 1, SUCC (x) is x+1.
Bei PrimRek gehst du anscheinend so vor:
Erst nimmst die Funktion, die du als prim-rek beweisen sollst und setzt c0 ein. Falls die Funktion 2 Parameter hat, setzt du c0 fürs y ein, ich glaub des geht pauschal.
ZB bei MULT setzt du ein MULT (x,c0) und schaust was rauskommt, des is in dem Fall c0. Bei ADD (x,c0) wärs x, was du als Projektionsfunktion darstellen musst, weil x nicht prim-rek ist, also p11(x).
Dann schreibst du die Funktion nochmal hin, mit SUCC(y) statt y. Bei MULT isses MULT (x,SUCC(y)), bildest die h-Funktion, müsste h(x,y,MULT(x,y)) sein, schaust, was du rumbasteln kannst, damit du der Lösung näher kommst (is jetzt nicht so toll formuliert…), in dem Fall wärs ADD(x,MULT(x,y)), d.h. du stellst x*(y+1) als x+(x*y) dar.
Dann noch mit Projektionsfunktion: ADD(x,p33(x,y,MULT(x,y)))
Scho bist fertig.
Man kann glaub ich noch
h(x,y,z)=ADD(x,p33(x,y,z)) hinschreiben, des war aber bei manchen Beispielen net dabei.
Etz müsstest nur noch beweisen, dass ADD prim-rek is…
Ich schreibs nochmal gescheit hin:
MULT(x,c0)=c0
MULT(x,SUCC(y))=h(x,y,MULT(x,y))=ADD(x,MULT(x,y))=ADD(x,p33(x,y,MULT(x,y)))
h(x,y,z)=ADD(x,p33(x,y,z))
muss das nicht
MULT(x,SUCC(y))=ADD(x,MULT(x,y))=ADD(p31(x,y,MULT(x,y)),p33(x,y,MULT(x,y)))
h(x,y,z)=ADD(p31(x,y,z),p33(x,y,z))
heissen?
ich hab allerdings wirklich keine grosse ahnung, ich haette es halt nur so aus meinem bisherigen wissen erstellt …
Doch, ja, kann sein. Hab auch schon Lösungen gesehen, wo es wieder anders geschrieben wird, aber in der einen Musterlösung vom 9. Übungsblatt stehts so drin, wies du gemeint hast.
hm. jo das is so ne sache
bei prim rek ist das problem teilweise das man einen geistesblitz braucht der eher ein mathematisches problem lösen soll. wie bei min(x,y).
entweder man kommt in 2-3 minuten auf ein ergebniss, oder nach 30mins immernoch nicht…
kA.
Wers uebrigens immer noch nich verstanden hat… (ich hatte ziemliche Probleme damit :wand: ) hier Adressen:
[URL]http://www.wikipedia.org/wiki/Primitive_recursive_function[/URL]
[URL]http://www.cs.nott.ac.uk/~txa/g51mcs/notes-4x.pdf[/URL]
Die sind zwar in Englisch - aber irgendwie hab ich das Gefühl, dass die das da wesentlich besser erklären als in der Vorlesung oder Übung.
Ging mir schon mit OTRS-I so - das Buch von Mano is super! 
Viel Erfolg allerseits :]
Also, durch die Prim.Rek steig ich ned so durch, aber anhand des .pdf’s trau ich mich jetzt zu folgender Behauptung:
fak (n) = n!
→ fak (c0) = 1 = succ(c0)
→ fak (succ(y)) = mult (succ(y); fak (y))
→ h(x,y)= mult(p2,1(x,y);p2,2(x,y))<-----hier bin ich mir nicht ganz sicher!
→ mult(x,y) zu beweisen:
→ mult(x, c0) = 0 = c0
→ mult(x, succ(y)) = add(x, mult(x,y))
—> add(x,y) zu beweisen:
—> add(x, c0) = x = p1,1(x)
—> add(x, succ(y)) = succ(add(x,y))
q.e.d.
Geht es besser, schneller, verständlicher??? :wand:
Es darf jetzt diskutiert werden :bounce:
bei der fak würde ich :
h(x,y) = mult(succ(p21(x,y)),p22(x,y))
aber ansonsten. jo
bei h stell ich mir immer vor:
- h muss eine var mehr haben als die funktion die wir darstellen wollen.
- die zusätzliche variable ist f(n) (bzw. halt mehr vars je nach typ)
- die zu beweisende funktion (also hier f(n)) ist das letzte (formale)argument.
falsch/richtig?
kA
eins versteh ich bei eurem ansatz aber nicht:
ihr wollt (succ(y)) als projektion schreiben und gebt dannn ausgerechnet succ(p21(x,y)) an , was bedeuten wuerde dass ihr aber den 1sten von 2parametern also x auswaehlt und dann davon den nachfolger bildet … das is aber dann also succ(x) != succ(y), oder ?
Also du musst aufpassen, von in welchen Funktionen wir uns bewegen, denn fak hat nur einen Parameter, mult aber 2. Und in fak benutze ich halt y als Platzhalter.
Und es gibt keinen eleganteren Weg, denke ich. Es soll ja nur dastehen: mult(x,y) und dass halt in Projektionen, also mult(p21(x,y);p22(x,y)) :bounce:
ich weiss aber nicht ob das so geht: du hast succ(y) also genau genommen von der identitaet von y bildest du den nachfolger oder ? dann hast du aber auch nur einen parameter weshalb es dann aber heisst succ(p11(x))