Olivetti Club

Mark SchachnerCornell University
The birdwatcher's guide to combinatory logic

Tuesday, September 13, 2022 - 4:35pm
Malott 406

"A certain enchanted forest is inhabited by talking birds. Given any birds A and B, if you call out the name of B to A, then A will respond by calling out the name of some bird to you; this bird we call AB."

So begins To Mock a Mockingbird, logician Raymond Smullyan's whimsical 1985 journey through the world of combinatory logic. The story of combinators began much earlier, though, in 1921 with Moses Schönfinkel's "On the building blocks of mathematical logic." Schönfinkel introduced combinatory logic as a point-free calculus for first-order logic, but as the theory was developed further by Haskell Curry, Alonzo Church, and others, it was found to have deep connections to computer science, and many principles of combinatory logic form the basis for functional programming languages like Lisp and Haskell today. In this talk, we follow Smullyan's lead and exposit combinatory logic via the metaphor of a diverse forest of birds. We'll see birds that can do arithmetic, model propositional logic, and even implement universal computation. No experience in mathematical logic is assumed, but some birdwatching experience is beneficial.