Der Beweis, warum das funktioniert, haben wir in der Vorlesung gesehen.

Ich kann ihn nochmal wiederholen.

Die Intuition dahinter ist, dass mi von f in ganz vielen Schritten zu f von f von f von und so weiter reduziert wird.

Das ist so die Idee dahinter.

Man kann sich überlegen, dass das klappt.

Um aus der Vorlesung zu kopieren, war das wie folgt.

Wenn ich die Definition einsetze, dann ist das eben lambda x, f, x, x und irgendwie das identische nochmal.

Wenn ich jetzt für dieses x diesen Term einsetze, dann kommt der erste Schritt heraus.

Wir setzen uns ein, dann haben wir f von lambda x, f, x, x, lambda x, also dieses Ding nochmal kopiert.

Jetzt noch diese Klammer zu.

Das ist eben genau das, was der Y-Combinator mit dem F macht.

Das ist mehr oder weniger Modulo-Ether-Transformation.

Um genau zu sein, f von y, f.

Deswegen kann man eine rekursive Definition schreiben, indem man das einfach blind anwendet.

Also zum Beispiel, wir haben dieses F im Fakultätsbeispiel, das ist so definiert, wir haben uns selbst und die Fakultätsfunktion.

Was bekommt die? Die Pol kommt ein n, die bekommt so ein n und wenn n gleich 0, dann evaluiert das zu 1.

Und sonst evaluiert das zu n, mal und jetzt ihr selbst zu von n minus 1.

Was macht dieses F jetzt? F bekommt irgendeine Funktion und es geht davon aus, dass die Funktion sich richtig verhält,

genauso eben verhält wie die Fakultätsfunktion für alle Zahlen kleiner gleich n minus 1.

Und das setzt quasi nur so den obersten Schritt drauf.

Also irgendwie, F kommt irgendeine Funktion selbst übergeben, die sich richtig

für kleinere Werte verhält.

Also warum richtig ist immer so ein schwammiges Wort, ebenso wie wir es durch die Rekursion definieren.

Und kleinere Werte, kleiner bedeutet, dass mit dem wir die Funktion eben aufrufen.

Also das klingt so ein bisschen nach Induktionsannahme, also self ist so ein bisschen unsere Induktionsannahme.

Und wir lösen mit der Induktionsannahme irgendwie das für n minus 1 und berechnen dann, also nach Induktionsannahme berechnet uns self das richtige für n minus 1.

Und mit Fallunterscheidungen berechnen wir dann die richtige Fakultät für so ein n.

Das ist so ein bisschen so, das ist so ein bisschen ein Induktionsschritt.

Und egal wo man hinschaut, immer wenn irgendwo Induktion auftaucht, kommt gleichzeitig auch Rekursion.

Also Induktion, Rekursion, das nächste Kapitel ist dann Coinduktion und Co-Rekursion.

Und da gibt es noch jede Menge andere Beispiele.

Okay, wie es sich richtig für erhält.

Also so ein bisschen, ja das kann man jetzt schwer ausdrücken, aber die Idee ist, wenn ich jetzt definiere die Fakultät Strich als den Fixpunkt.

Fixpunkt von F, also zum Beispiel den Y-Kombinator auf F.

Dann berechnet uns das die Fakultätfunktion.

Was sollen wir zeigen für 3 bis 6?

3 nach 6.

Probieren oder wollen wir lieber mal, ja machen wir 3, okay.

Also YF von 3.

Was macht das, das müssen wir mal schauen, ist F von Y von F von 3, den ich eben das vordere reduziere.

Und das, ja, wenn ich jetzt mir diese Definition hier angucke, dann ist das wie folgt aus, dann ist das YF das Save und N die 3.

Wir reduzieren das mal, also vielleicht sollte ich da kein ist gleich machen, sondern ein reduziertes, denn wir machen hier ja einen solchen Reduktionsschritt.

Ja, setzen wir es mal ein, if N ist gleich 0, äh Quatsch, if 3 ist gleich 0, wenn 1 sonst 3 mal self.

Self war das ja dieses YF von 2.

Ich habe jetzt schon zu gemein und habe schon mal ein bisschen reduziert.

Ja, wozu reduziert das?

Na, 3 ist nicht gleich 0, also reduziert das zu 3 mal YF.

Ist das so ein 2F nicht ein Klammer?

Äh, bin ich jetzt nicht, machen wir es sicherheitshalber, YF, so.

Wenn wir ABC im Lambda-Kühlschreitband, ist das äquivalent zu so.