Are Two Recipes That Always Bake the Same Cake Really the Same Recipe?
A Strange Kind of Recipe
Imagine you’re baking a cake. One recipe says “add 1 cup of sugar”, another says “add 2 cups of sugar, then remove 1 cup”. Both produce the exact same cake, every time. Are they the same recipe? Most chefs would say no — the steps feel different, even if the outcome is identical.
Mathematicians in the 1930s faced a similar puzzle about functions. A function is a rule that takes an input and produces an output — like “double the number” or “find the length of a triangle’s hypotenuse”. But what is that rule, really? Is it just a list of which input leads to which output? Or is it the actual steps you follow inside?
To capture the idea of a function as a step‑by‑step recipe, the logician Alonzo Church (1903–1995) invented the λ‑calculus. The Greek letter λ (lambda) lets you write a function as a pattern with a blank: λx[x+1] means “the function that, given any number x, gives you x plus one”. When you feed it a number — writing something like (λx[x+1])3 — you perform β‑reduction: you plug 3 into every spot where x appears, getting 3+1, and then you compute. That single rule, β‑reduction, is the beating heart of the λ‑calculus.
Church’s notation wasn’t just a tidy way to write math. It was a whole language for thinking about what a function really is. And it forced philosophers and computer scientists to ask a surprisingly tricky question: if two recipes always give the same result, are they allowed to be different recipes?
The Birth of a Pure Idea
The roots of the λ‑calculus stretch back to Gottlob Frege (1848–1925), who noticed that functions that take multiple inputs can be broken down into a chain of one‑input functions. Instead of a single function that takes two numbers and finds the hypotenuse, you have a function that takes the first number and returns a new function that is “waiting” for the second number. This trick — called currying — is like a factory machine that loads one bolt at a time, leaving the rest of the work to the next machine in line.
In the 1920s, Moses Schönfinkel (1889–1942?) pushed this idea further by studying combinators — special function‑objects that can be combined without ever naming variables. He discovered that two combinators, S and K, could build any possible function. Church, inspired by this, designed the λ‑calculus in 1932 as a way to actually write those functions. His student Haskell Curry (1900–1982) and others then probed the system’s power, hoping to build a foundation for all of logic and mathematics.
But the early attempts ran into trouble. Curry uncovered a paradox — a term that, if you used it freely, would make every statement provable, collapsing the whole system. Later, Church showed that the simple question “are these two λ‑recipes equal?” has no mechanical method that always works — it’s undecidable. That result was the first ever undecidability proof, and it shook the mathematical world. Yet the λ‑calculus didn’t crumble. A deep result called the Church‑Rosser theorem proved that the system is consistent: not every equation is forced to be true. Two obviously different combinators, like K (which discards its second argument) and I (the identity function), really are different. The calculus had survived its early crisis.
What Counts as the Same Function?
Now we can sharpen the cake‑recipe question using the λ‑calculus. Look at these two terms:
- add‑one: λx[x+1]
- add‑two‑subtract‑one: λx[x+2−1]
They are extensionally equivalent: for every actual input, they spit out the same number. In a math class that treats a function as a set of input‑output pairs, they are just the same set; you’d call them the same function. This is the functions‑as‑sets view, and it’s extensional.
But we can push further. Suppose the facts of arithmetic are the same in every possible universe. Then add‑one and add‑two‑subtract‑one give the same output for the same input in every possible world. They are then intensionally equivalent. An intensional function concept would still identify them.
The λ‑calculus, however, doesn’t automatically identify them. The two λ‑terms are made of different building blocks, and without an extra rule, you can’t prove they’re equal. This makes the λ‑calculus hyperintensional: it allows two recipes that behave identically in all possible circumstances to still count as different functions. The internal rule matters.
Why does this matter? Because if you think of a function as a rule — a concrete set of instructions — then the way something works can be just as important as what it produces. A robot that sorts blocks by color using a camera and one that does it by weight might end up with the same sorted piles, but you’d hardly say they’re running the same program.
Can a Function Eat Itself?
One of the oddest things about the pure λ‑calculus is that it lets a function feed itself as its own input. The term ω is λx[xx] — a function that applies x to itself. Its self‑application, Ω, reduces to itself in one step: Ω → Ω → Ω forever. That looks like a logical mobius strip, and you might worry it could lead to contradictions.
But the Church‑Rosser theorem guarantees that this circling never forces you to say that every term equals every other term. Think of it like a maze: no matter which turns you take, any two paths that diverge from the same starting point can always be merged again later. So the λ‑calculus is safe for reasoning — it’s a consistent playground for functions as rules, even when those rules are allowed to twist back onto themselves.
From Recipes to Computers
Church’s notation turned out to be not just a philosopher’s toy but a genuine model of computing. You can represent numbers inside the λ‑calculus (for instance, 1 is a function that applies its first input once, 2 applies it twice, and so on). With clever combinators, you can build “if‑then‑else” logic, loop forever, and even simulate any procedure a modern computer can execute. This discovery forms part of the Church‑Turing thesis: anything that is computable at all can be done in the λ‑calculus.
When programmers later designed languages like Lisp, Haskell, and parts of JavaScript, they borrowed directly from Church’s ideas. Even the concept of types — labeling functions with what kind of input they expect — grew out of the λ‑calculus. And a famous link called the Curry‑Howard correspondence shows that writing a well‑typed program is exactly the same as proving a logical statement. In other words, computing and reasoning are two sides of the same coin, just as Church and Curry suspected.
Why This Still Matters Today
The λ‑calculus sits quietly inside your phone, your web browser, and the servers that stream your favorite shows. But its philosophical heartbeat is even louder now. When a search engine ranks pages, it runs a recipe. When an AI suggests the next word in your message, it follows a different recipe. If two AI systems behave perfectly alike, can we call them the same mind? The λ‑calculus doesn’t answer that question for you — but it gives you a language to notice when you’re mistaking same‑output for same‑process.
Philosophers today also use λ‑terms to talk about properties and relations. A property like “being loved by Mary” can be written as a λ‑abstraction, and theories of hyperintensional properties (properties that care about how they are described) lean directly on Church’s invention. The next time you wonder whether two things that act the same really are the same, you’re wading into a debate that started with a scribbled Greek letter in a Princeton notebook nearly a century ago.
Think about it
- If a robot chef follows a slightly different recipe but always makes the exact same cake, should we say it’s making the same cake recipe? Why or why not?
- Can a computer program be called “creative” if it produces a beautiful poem by recombining old lines according to fixed rules, or does the internal process change what we should call the result?
- If two people solve a math problem using different mental steps but arrive at the same answer, are they thinking the same thought?
