Probeklausur Aufgabe 2.1

Bachelor Theorie der Programmierung
1

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.

2

Probeklausur Aufgabe 2.1
In der Probeklausur SoSe16 in Aufgabe 2.1 müssen 4 beta-delta-Reduktionen durchgeführt werden. Wird damit (beta-delta-Reduktion gleichzeitig) oder (beta- oder delta-Reduktion) gemeint?
wird also pow2 three (normal)-> zu
three (mult two) one
oder zu
(λn.n (mult two) one) three
?

Vielen lieben Dank
Euer ThProgFanClub

3

Ersteres, also “three (mult two) one”. Es geht darum, in jedem Schritt entweder eine β- oder eine δ-Reduktion durchzuführen. Die zweite Variante wäre allerdings auch keine gleichzeitige Durchführung von β- und δ-Reduktion. Wo findet da denn eine β-Reduktion statt? Um diese Variante zu erhalten, müsste ‘pow2’ ohne Argument definiert sein.

4

[quote=quaestor]
Ersteres, also „three (mult two) one“. Es geht darum, in jedem Schritt entweder eine β- oder eine δ-Reduktion durchzuführen. [/quote]
Wäre Ersteres denn nicht sowohl eine β- als auch eine δ-Reduktion?
Zum Einen löst man ja pow2 auf (δ-Reduktion) und setzt three dann in λn ein ( β-Reduktion).
Dann würde man aber auch β-Reduktion und δ-Reduktion gleichzeitig durchführen und das wäre laut deiner Aussage falsch.
Oder ist Ersteres nur als β-Reduktion anzusehen?

Die zweite Variante wäre aus unserer Sicht auch nur eine δ-Reduktion gewesen, weil wir nur pow2 aufgelöst haben.

Wie würde denn der zweite Schritt nach three (mult two) one dann lauten? Wäre es dann (mult two) ((mult two)((mult two)one))?

Vielen lieben Dank
Euer ThProgFanClub

5

Ich verstehe nicht, wo die β-Reduktion herkommen soll. „pow2“ ist definiert als:

pow2 n = n (mult two) one

Ich verweise wieder auf Übungsblatt 4 Aufgabe 2.2. Da sieht man eindeutig, wie die δ-Reduktion von einem so definierten Term abläuft, nämlich durch simultane Substitution mehrere Parameter in einem Reduktionsschritt.

Nein. „three (mult two)“ ist eine Applikation. Die Regeln für normale Reduktion besagen nun, dass man zuerst den Funktionsterm reduziert, also „three“. Hier gibt es nun nur eine Möglichkeit der Reduktion, nämlich δ, also Substitution mit der Definition von „three“.

6

Hallo, ich hätte ebenfalls ein paar Fragen zu dieser Aufgabe.

  1. Aufgabenstellung
    Soll gelten
    (a) Anzahl(beta) + Anzahl(delta) = 4, oder
    (b) Anzahl(beta) = Anzahl(delta) = 4
    ?
    Ich tendiere sinnhalber ja zu (a), aber das ist nicht eindeutig meiner Meinung nach.

  2. Reduktion
    Wenn ich bei der applikativen Reduktion etwas in der Form func a b habe, dann muss ich mich, wenn es sich delta reduzieren lässt, zuerst um b kümmern , oder? Weil es gilt ja ((func) a) b, daher ist b am weitesten außen. Hab ich das richtig verstanden?

Liebe Grüße!