Voraussetzungen zum Erlernen des Lambda-Kalküls

Question

Kann mir jemand sagen, was die Voraussetzungen für das Erlernen von Lambda Calculus sind (falls vorhanden)?

Answer 1

Das hängt wirklich davon ab, was Sie mit dem Lambda -Kalkül machen möchten. Wenn Sie es lernen möchten, nur um zu sehen, wie es funktioniert, gibt es wirklich keine Voraussetzungen. Es ist ziemlich in sich geschlossen. Wenn Sie jedoch einen der Beweise dafür verstehen möchten (Turing-Completness, Church-Ziffern, Normalisierung usw.), benötigen Sie möglicherweise mehr mathematische Voraussetzungen. Insbesondere würde ich einen Hintergrund in induktiven Beweistechniken vorschlagen, insbesondere in der strukturellen Induktion. Es mag auch schön sein, ein wenig über das Anstiegsproblem oder eine Art Unvollständigkeitssatz zu wissen, da einige der lustigen Ergebnisse mit Lambda Calculus Nichtvorbereitung beinhalten.

Answer 2

Es gibt keine Voraussetzungen für das Verständnis des Lambda -Kalküls selbst. Wenn Sie kein Informatiker sind und nicht einmal die Rekursion kennen, können Sie die Grundlagen von (Untyped) Lambda Calculus in etwa 30 Minuten hier informell lernen: http://palmstroem.blogspot.de/2012/05/lambda-calculus-for-absolute-dummies.html Dies sollte Ihnen eine funktionierende Intuition darüber geben, was es tut und wie es funktioniert.

Wenn Sie mit grundlegenden mathematischen Notationen und rekursiven Definitionen vertraut sind, können Sie sich für eine Standardeinführung entscheiden. Insbesondere wenn Sie die Lambda -Kalkül als Grundlage für Haskell kennenlernen möchten, sollten Sie sich mit den Tiefen des typisierten Lambda -Kalküls befassen: http://www.cse.chalmers.se/research/group/logic/typesss05/extra/geuvers.pdf