Title: What is the Lambda Calculus?
Speaker: Vilas Winstein (Ohio State University)
Abstract: The λ-calculus is a formal system modeling computation created by Alonzo Church, and its most prominent feature is function application via variable binding and substitution. It is equivalent to any other universal model of computation (most notably it is equivalent to the Turing machine which modern computers are based on), which means any algorithmically-solvable problem can be solved via a λ-expression. In this talk we will discuss the rules of constructing λ-expressions and performing operations on them. We will also discuss representation of data in the λ-calculus and introduce a few special λ-expressions which perform common algorithms. Finally, we will use the λ-calculus to give a concise proof of the undecidability of the Halting problem, showing a less-traveled-by route to answering a pivotal question of the early 20th century posed by David Hilbert: the Entscheidungsproblem.
- Church, A. (1932). ”A set of postulates for the foundation of logic”. Annals of Mathematics. Series 2. 33 (2): 346–366. JSTOR 1968337. doi:10.2307/1968337.
- Rojas, R. (2015). A tutorial introduction to the lambda calculus. arXiv preprint arXiv:1503.09060.
- Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.
- Turing, A. M. (December 1937). ”Computability and λ-Deﬁnability”. The Journal of Symbolic Logic. 2 (4): 153–163. JSTOR 2268280. doi:10.2307/2268280.
The What is ...? seminar's main goal is to expose culturally ambitious participants to some mathematical notions not taught in standard courses. These topics form an important part of mathematical folklore, and may prove useful for doing research and enhancing teaching. Lectures will be given mostly by graduate and undergraduate student participants. Professors Vitaly Bergelson and Daniel Shapiro serve as coordinators/mediators.
The What is ...? Seminar is an event organized by the Mathematics Department, independent of SAMMS, but participants are encouraged to attend any meeting that seems intriguing! Let the attending mediator know you are a SAMMS participant.