Pre-requisites for learning lambda calculus

Question

Can anyone tell me what are the pre-requisites to learning lambda calculus (if any)?

Answer 1

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.

Answer 2

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