Lambda Kalkül Normalform?
Ich brauch wirklich Hilfe hierbei, ich versteh nicht wie ich das am Ende in Normalform umwandeln kann.
(λabc.a(bb)c)(λxy.xya)(λa.a)
Bei jedem Versuch bekomm ich immer ein anderes Ergebnis.
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik
Gegeben:
(λa b c. a (b b) c) (λx y. x y a) (λa. a)
Schritt 1: Verstehe die StrukturWir haben:
λa b c. a (b b) c
Das ist eine Funktion mit drei Parametern:
a
,
b
,
c
.
Der Funktionskörper ist:
a (b b) c
→ Bedeutet:
b
wird auf sich selbst angewendet, dann wird
a
auf das Ergebnis und auf
c
angewendet.
Wir wenden diese Funktion auf zwei Argumente an:
λx y. x y a
λa. a
Wir ersetzen:
a
- durch
λx y. x y a
b
- durch
λa. a
Der Körper war:
a (b b) c
Daraus wird:
(λx y. x y a) ((λa. a) (λa. a)) c
Jetzt definieren wir eine neue Funktion über
c
:
λc. (λx y. x y a) ((λa. a) (λa. a)) c
Schritt 3: Reduziere(λa. a)(λa. a)
Das ist die Identitätsfunktion auf sich selbst angewendet:
Ergibt einfach:
λa. a
Also:
λc. (λx y. x y a) (λa. a) c
Schritt 4: Wende(λx y. x y a)
auf(λa. a)
anJetzt wenden wir:
(λx y. x y a)
auf:
λa. a
an.
Ergebnis: Ersetze
x
durch
λa. a
.
Dann bleibt:
λy. (λa. a) y a
Nun:
(λa. a) y
ergibt
y
, also bleibt:
λy. y a
Schritt 5: Wende das aufc
anJetzt haben wir:
λc. (λy. y a) c
Wende
(λy. y a)
auf
c
an:
→ ergibt:
c a
Fertig! Das ist die Normalform:λc. c a