Can anyone tell me what are the pre-requisites to learning lambda calculus (if any)?
- This question is not programming-related. Try asking on math.stackexchange.com instead.Cody Gray– Cody Gray ♦2010-12-27 10:33:26 +00:00Commented Dec 27, 2010 at 10:33
- @Cody: How is the lambda calculus not programming related? It's like the mother of all functional programming languages.sepp2k– sepp2k2010-12-27 12:52:24 +00:00Commented Dec 27, 2010 at 12:52
- @sepp2k: As far as I'm concerned, math is the mother of everything in [computer] science. I still don't think that questions about learning lambda calculus qualify as strictly programming-related. It seems we have a site for that. I don't think it belongs on SO given that no language is mentioned, the question doesn't involve specific algorithms, there is no code posted, etc.Cody Gray– Cody Gray ♦2010-12-27 12:53:45 +00:00Commented Dec 27, 2010 at 12:53
- Lambda calculus is much more "computer science" than it is "math".Eli Barzilay– Eli Barzilay2010-12-27 14:59:19 +00:00Commented Dec 27, 2010 at 14:59
Add a comment |
2 Answers
That really depends on what you want to do with the lambda calculus. If you want to learn it just to see how it works there really aren't any prerequisites; it's pretty self-contained. However, if you want to understand any of the proofs about it (Turing-completeness, Church numerals, normalization, etc.) you might need more math prereqs. In particular, I'd suggest a background in inductive proof techniques, especially structural induction. It also might be nice to know a little about either the halting problem or some sort of incompleteness theorem, since some of the fun results with lambda calculus involve non-computability.
answered Dec 27, 2010 at 7:26
templatetypedef
376k112 gold badges954 silver badges1.1k bronze badges
1 Comment
MasterMastic
Could you offer the field(s) to study for the ones who indeed wanna go hardcore on lambda calculus? (after all, how else will we get all the ladies).
There are no prerequisites for understanding the Lambda Calculus itself. If you are not a computer scientist and don't even know recursion, you can learn the basics of (untyped) Lambda Calculus informally in about 30 minutes here: http://palmstroem.blogspot.de/2012/05/lambda-calculus-for-absolute-dummies.html This should give you a working intuition about what it does and how it works.
If you are familiar with basic mathematical notations and recursive definitions, you can go for a standard introduction. Especially, if you want to learn about the Lambda Calculus as a basis for Haskell, you should delve into the depths of the typed Lambda Calculus: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf
