Season 1, Act III: Church’s Functions & The Lambda Magic

Introduction

After Kurt Gödel showed that math had built-in limits, the big question became: “Okay, so what can we solve?” If we can’t create a perfect system to prove everything, maybe we can define exactly what is possible to compute.

Enter Alonzo Church, an American mathematician and logician. He wasn’t thinking about physical machines or gears. He was thinking about the purest, most fundamental building block of mathematics: the function.

What’s a Function, Anyway?

Forget your high school algebra class for a moment. Think of a function as a simple machine or a rule.

• You put something in.
• It does something specific to it.
• It spits something out.

For example, a function called add_five could be a machine that takes any number you give it and adds five to it.

• Input: 3 → add_five → Output: 8
• Input: 10 → add_five → Output: 15

Simple, right? Church believed that all of computation, from simple arithmetic to complex logic, could be described using only these simple input-output rules.

The Magic of Lambda (λ)

To explore this idea, Church invented a tiny, powerful language to describe functions. He called it the Lambda Calculus. It’s not a programming language you’d use to build an app, but it’s the ancestor of many modern ones.

The core idea is the “lambda expression,” which is a way to write a function without even giving it a name. It’s a pure, anonymous rule.

In mathematics, you might write the add_five function as $f(x) = x + 5$.

In Lambda Calculus, Church wrote it like this:

$$λx.x + 5$$

Let’s break that down:

• $λ$ (lambda): This is just a symbol that says, “Hey, I’m defining a function right here!”
• $x$: This is the name of the input (the argument).
• $.$ (dot): This separates the input from the rule.
• $x + 5$: This is the rule itself - what to do with the input.

This little piece of notation says: “Here is a function that takes an input, which we’ll call ‘x’, and returns that ‘x’ with 5 added to it.”

Building a Universe from Functions

Here’s where it gets wild. Church showed that you don’t need anything else. You don’t even need numbers like 1, 2, 3, or operators like +. You can build the entire concept of numbers and arithmetic using only these tiny lambda functions.

For example, he defined the number “zero” as a function, “one” as a different function that applies another function once, “two” as a function that applies another function twice, and so on. He then created functions that could take these “number-functions” and perform addition and multiplication on them.

It was a complete, self-contained system for computation built from a single, elegant idea.

The Foundation of Programming Logic

Alonzo Church had created the first universal model of computation. He proposed that any problem that could be solved by an algorithm - any “effectively calculable” function - could be expressed in the Lambda Calculus. This is known as the Church-Turing thesis (we’ll meet Turing next!).

While you might not see $λ$ symbols everywhere, the ghost of Lambda Calculus is in almost every major programming language today:

• It’s the foundation of functional programming languages like Lisp, Haskell, and F#.
• When programmers in Python, JavaScript, or C# use “lambda functions” or “anonymous functions,” they are using a direct descendant of Church’s 1930s invention.

Church gave us a powerful new way to think about problems: not as a sequence of steps, but as a series of transformations. You take an input, apply a function to transform it, take that output, and feed it into another function.

At the very same time, across the Atlantic, a young British mathematician named Alan Turing was attacking the exact same problem from a completely different angle. He wasn’t thinking about pure logic; he was imagining a machine…