Hallo,
könnte vielleicht jemand so lieb sein und mir erklären, wie ich das Gewicht eines Terms berechnen kann? Vielleicht an einem Beispiel? Das was im Skript dazu steht hilft mir grad nich weiter. Danke
es gilt ja gew(v) = 2 für ein atomares v
und gew(x+y) = gew(x) + gew(y)
und gew(x*y) = gew(x)^2 * gew(y) für komplexe x, y
Wenn du nun einen Term
t = (a+b)*c + a*b*(d+e)
hast.
dann hast du
gew(t) = gew((a+b)*c) + gew(a*(b*(d+e)))
= gew(a+b)^2 * gew( c) + gew(a)^2 * gew(b*(d+e))
= gew(a+b)^2 * gew( c) + gew(a)^2 * gew(b)^2 * gew(d+e)
= gew(a+b)^2 * gew( c) + gew(a)^2 * gew(b)^2 * (gew(d) + gew(e))
und wenn du davon ausgehst, dass a..e atomar sind kannst du das ganz normal ausrechnen.
Und nun mal als Beispiel (ab)c und a(bc)
gew((ab)c) = gew(ab)^2 * gew(c ) = (gew(a)^2*gew(b))^2 * gew( c) = gew(a)^4 * gew(b)^2 * gew(c )
gew(a(bc)) = gew(a)^2 * gew(bc) = gew(a)^2 * gew(b)^2 * gew( c)
Da sieht man, dass das gewicht anders ist, wenn unterschiedlich geklammert wird
Diese Gewichtsunterschiede von z. B. (ab)c und a(bc)
Danke schomal für die gute Erklärung.
Und was ist jetzt das Gewicht im allgemeinen? Je höher das Gewicht, desto mehr Schritte braucht man um zur Normalform zu kommen?
Die Gewichtsfunktion ist ein Hilfsmittel im Beweis der Vollständigkeit
des BPA-Kalküls (siehe S.147 und 148). Sie wird benutzt um zu zeigen,
dass man immer zu einer Normalform kommen kann (d.h. hier insb.
dass das im Beweis skizzierte Verfahren abbricht).
Je höher das Gewicht, desto mehr Schritte braucht man um zur Normalform zu kommen?
Das gilt nicht, wie du dir an
abcdefghijk
und
a+a
klar machen kannst.
(Ersteres ist übertrieben formuliert, du kannst auch einfach abc nehmen oder sogar nur ab,
aber überleg dir einmal, was bei abcde usw. passiert.)
Frank :)
In Aufgabe 1.4 sollen wir ja die Gewichte der drei Terme ausrechnen. Was genau sagt uns dann das Ergebnis? Was ist das Gewicht? Und müssen wir um das Gewicht zu berechnen die Normalform bilden?
Was genau sagt uns dann das Ergebnis?
So fuer sich gesehen? Nix. Das Gewicht ist nur dann interessant, wenn man verschiedene Gewichte vergleicht. Auf dem Weg zur Normalform nimmt das Gewicht naemlich mit jedem Schritt ab (siehe Aufgabe 6.2.5)
Was ist das Gewicht?
Eine natuerliche Zahl.
Und müssen wir um das Gewicht zu berechnen die Normalform bilden?
Nein.
also ist der betrag des gewichts von keiner bedeutung? obwohl wir ja sehen, das er durch reduktionen im ersetzungskalkül verringert wird.
Genau, die Gewichtsfunktion ist nur ein Hilfskonstrukt innerhalb des Beweises. Der konkrete Wert hat keinerlei Bedeutung.
Genau, die Gewichtsfunktion ist nur ein Hilfskonstrukt innerhalb des Beweises. Der konkrete Wert hat keinerlei Bedeutung.
ok danke, genau das hab ich mich gefragt.
also ist der betrag des gewichts von keiner bedeutung? obwohl wir ja sehen, das er durch reduktionen im ersetzungskalkül verringert wird.
Na ja, die Bedeutung liegt darin, dass dadurch die Reduktionsketten terminieren müssen, denn negative Gewichte werden (wohl) nicht erlaubt!
Wurde vorher von UncleOwen auch schon gepostet.
Was mich wundert - die Leute haben Fragen zu FGI-2, aber die Besucheranzahl beim Tutorium ist niedrig. Das Tutorium ist wirklich hilfreich! Also, kommt alle hin!
Es gibt so einige Leute, die parallel Veranstaltungen haben. Ich habe keine Möglichkeit zum Tutorium zu gehen…
Das nenne ich: "Wie sehr man etwas erreichen will, so klappt das auch". Wenn genug Leute da sind, kann ein anderer Termin besprochen werden. Ich kann z.B. auch nicht immer kommen wegen SE-3-Üebung. Und abends habe ich jede zweilte Woche AD-Übung. Aber wenn ich kann, komme ich auch. Z.B. wird manchmal die SE-Übung früher abgeschlossen, weil wir schnell alles besprochen haben, dann beeile ich morgens zum Termin. Wie gesagt - es wurde intern besprochen, ob wir am Montag von 8 bis 10 machen könnten oder am Donnerstag nach der FGI Vorlesung mal nach Stellingen fahren… Ist genug Spielraum, nur wenig Leute. Wenn ihr so etwa 8 Leute organisiert - könnt ihr mit Michael den Termin besprechen, er besprächt das dann mit den schon existierenden Grüppchen…
